1452: [JSOI2009]Count

Time Limit: 10 Sec  

Memory Limit: 64 MB

Submit: 2693  

Solved: 1574

[ ][ ][ ]

Description

Input

Output

Sample Input

Sample Output

1
2

HINT

开心~自己写出了树套树【蒟蒻的欢愉】

颜色很少，区间也很小，对每种颜色开一个二维树状数组就好了

第一维表示x，对应x行的第二维树状数组

复杂度O(Qlog^2n)

#include
    
     #include
     
      #include
      
       #include
       
        #define LL long long int#define REP(i,n) for (int i = 1; i <= (n); i++)#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)#define lbt(x) (x & -x)using namespace std;const int maxn = 305,maxm = 105,INF = 1000000000;inline int RD(){	int out = 0,flag = 1; char c = getchar();	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}	while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}	return out * flag;}int A[maxm][maxn][maxn],s[maxn][maxn],n,m,Q;inline void add(int c,int p,int u,int v){while (u <= m) A[c][p][u] += v,u += lbt(u);}inline int query(int c,int p,int u){int ans = 0; while (u) ans += A[c][p][u],u -= lbt(u); return ans;}inline int sum(int c,int p,int l,int r){return query(c,p,r) - query(c,p,l - 1);}inline void modify(int c,int x,int y,int v){while (x <= n) add(c,x,y,v),x += lbt(x);}inline int Query(int c,int x,int l,int r){int ans = 0; while (x) ans += sum(c,x,l,r),x -= lbt(x); return ans;}inline int Sum(int c,int xl,int xr,int yl,int yr){return Query(c,xr,yl,yr) - Query(c,xl - 1,yl,yr);}int main(){	n = RD(); m = RD(); int x,y,x1,y1,c,cmd;	REP(i,n) REP(j,m) s[i][j] = RD(),modify(s[i][j],i,j,1);	Q = RD();	while (Q--){		cmd = RD();		if (cmd & 1){			x = RD(); y = RD(); c = RD();			modify(s[x][y],x,y,-1); modify(c,x,y,1); s[x][y] = c;		}else {			x = RD(); x1 = RD(); y = RD(); y1 = RD(); c = RD();			printf("%d\n",Sum(c,x,x1,y,y1));		}	}	return 0;}