[JSOI2009]Count

Time Limit:10000MS  Memory Limit:65536K
Total Submit:16 Accepted:15
Case Time Limit:1000MS

Description

Input

Output

Sample Input

Sample Output

1
2

Hint

Source

JSOI2009Day1
61.187.179.132:8080/JudgeOnline/showproblem

我已经菜到只会做水题了。。又看了两道题。。都不会囧。。只好把题目按通过人数排序了一下囧。。
这道题不知道有没有什么更好的办法。我不管三七二十一直接上二维树状数组了。二维树状数组本质上跟一维的也差不多。。就是对每个颜色都维护一个树状数组，然后其他就好说了。。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=301,maxc=100;
int n,m;
struct Board
{
int C[maxn][maxn];
Board(){memset(C,0,sizeof(C));}
void change(int i,int j,int d)
{
for(int x=i;x<=n;x+=x&-x)
for(int y=j;y<=n;y+=y&-y)
C[x][y]+=d;
}
int sum(int i,int j)
{
int Ans=0;
for(int x=i;x>0;x-=x&-x)
for(int y=j;y>0;y-=y&-y)
Ans+=C[x][y];
return Ans;
}
int sum(int x0,int y0,int x1,int y1)
{
return sum(x1,y1)-sum(x1,y0-1)-sum(x0-1,y1)+sum(x0-1,y0-1);
}
}C[maxc];
int M[maxn][maxn];
void Change(int x,int y,int c)
{
int o=M[x][y];
C[o].change(x,y,-1);
C.change(x,y,1);
M[x][y]=c;
}
int main()
{
//freopen("in","r",stdin);
cin>>n>>m;int c;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&c);–c;
C.change(i,j,1);
M[i][j]=c;
}
int p,t,x,y,x0,y0,x1,y1;cin>>p;
while(p–)
{
scanf("%d",&t);
if(t==1)
scanf("%d %d %d",&x,&y,&c),Change(x,y,c-1);
else
scanf("%d %d %d %d %d",&x0,&x1,&y0,&y1,&c),printf("%dn",C[c-1].sum(x0,y0,x1,y1));
}
}