BZOJ P1452 count 【树状数组】

xiaoxiao2021-02-28  18

就是一个二维线段树板题:

#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define DB double #define SG string #define LowBit(X) (X&(-X)) #define Fp(A,B,C,D) for(A=B;A<=C;A+=D) #define Fm(A,B,C,D) for(A=B;A>=C;A-=D) #define Clear(A) memset(A,0,sizeof(A)) #define Copy(A,B) memcpy(A,B,sizeof(A)) using namespace std; const int Max=3e2+5; const int Mod=1e9+7; const int Inf=1e18; int N,M,Mat[Max][Max],Sum[Max][Max][105]; inline int Read(){ int X=0;char CH=getchar();bool F=0; while(CH>'9'||CH<'0'){if(CH=='-')F=1;CH=getchar();} while(CH>='0'&&CH<='9'){X=(X<<1)+(X<<3)+CH-'0';CH=getchar();} return F?-X:X; } inline void Write(int X){ if(X<0)X=-X,putchar('-'); if(X>9)Write(X/10); putchar(X+48); } void Update(int X,int Y,int V,int K){ int I,J; for(I=X;I<=N;I+=LowBit(I)){ for(J=Y;J<=M;J+=LowBit(J)){ Sum[I][J][V]+=K; } } } int GetSum(int X,int Y,int V){ int I,J,SUM=0; for(I=X;I;I-=LowBit(I)){ for(J=Y;J;J-=LowBit(J)){ SUM+=Sum[I][J][V]; } } return SUM; } int main(){ int I,J,K; N=Read(),M=Read(); Fp(I,1,N,1){ Fp(J,1,M,1){ Mat[I][J]=Read(); Update(I,J,Mat[I][J],1); } }K=Read(); Fp(I,1,K,1){ int Q=Read(); if(Q==1){ int X=Read(),Y=Read(),Z=Read(); Update(X,Y,Z,1);Update(X,Y,Mat[X][Y],-1);Mat[X][Y]=Z; } else { int X1=Read(),X2=Read(),Y1=Read(),Y2=Read(),V=Read(); Write(GetSum(X2,Y2,V)-GetSum(X1-1,Y2,V)-GetSum(X2,Y1-1,V)+GetSum(X1-1,Y1-1,V));putchar('\n'); } } return 0; }
转载请注明原文地址: https://www.6miu.com/read-1650164.html

最新回复(0)