1452: [JSOI2009]Count

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 2693  Solved: 1574

[Submit][Status][Discuss]

Description

Input

Output

Sample Input

Sample Output

HINT

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

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

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

复杂度O(Qlog^2n)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#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;

}