记录编号 129634 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 1753.[HZOI 2014] 天使的小纸条 最终得分 100
用户昵称 ztx 是否通过 通过
代码语言 C++ 运行时间 17.389 s
提交时间 2014-10-20 15:35:19 内存使用 14.39 MiB
显示代码纯文本
/*
	Name: 天使的小纸条 
	Author: hzoi_jsx
	Date: 18/10/14 19:50
	Description: 二维树状数组+离线算法
	其实就是把对每种颜色的操作分开,分别对每一种颜色进行统记.
	对于连接的问题,我用的是 图的前向星 存法。 
	感觉就是把操作拆分,对每一种颜色分别处理比较难想到. 
	
	很容易发现各个颜色之间是相互独立的,于是按照颜色分类处
	理,读入时首先按照操作模拟一遍,把修改操作拆成两个操作,
	删除某位置的某颜色和在某位置插入某颜色并存下来,查询操作
	也全部存下来,之后倒序扫描,用一个链表分别把对相同颜色处
	理的操作连接起来。
	之后对于某一颜色,所有的操作可以简化为在平面上某位置插
	入一个点,删除一个点,查询一个矩形内点的个数,用二维树状
	数组维护即可。
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <cctype>
#include <climits>
#include <cstdlib>
using namespace std;

int N=0,M=0,Q=0,tot=0,res=0;
int T [310][310]={0};
int Map[310][310]={0};

class node{
	public:
		int l1,r1,l2,r2;
		int color,ans;
		int flag;
}Op[500010];

map<int,int >to;
map<int,int >Next;
map<int,int >line;
map<int,bool>flag;

/*class Edge{//模拟链表...... 
	public:
		int to,next;
}Link[400010];
int line[400010]={0};*/

inline int Lowbit(int x){
	return x&(-x);
}

inline void Insert(int x,int y,int v){
	for(int i=x;i<=N;i+=Lowbit(i)){
		for(int j=y;j<=M;j+=Lowbit(j)){
			T[i][j]+=v;
		}
	}
}

inline int Sum(int x,int y){
	int Ans=0;
	for(int i=x;i>0;i-=Lowbit(i)){
		for(int j=y;j>0;j-=Lowbit(j)){
			Ans+=T[i][j];
		}
	}
	return Ans;
}

inline void Add_Op_1(int l,int r,int color,int flag){
	tot++;
	Op[tot].color=color;
	Op[tot].flag=flag;
	Op[tot].l1=l;	Op[tot].r1=r;
}

inline void Add_Op_2(int l1,int r1,int l2,int r2,int color,int flag){
	tot++;
	Op[tot].color=color;
	Op[tot].flag=flag;
	Op[tot].l1=l1;	Op[tot].r1=r1;
	Op[tot].l2=l2;	Op[tot].r2=r2;
}

inline void Add_Op_3(int x,int y){
	res++;
	to[res]=y;
	Next[res]=line[x];
	line[x]=res;
	/*Link[res].to=y;
	Link[res].next=line[x];
	line[x]=res;*/
}

inline void Deal_Color(int color){
	memset(T,0,sizeof(T));
	for(int i=line[color];i!=0;i=Next[i]){
		int p=to[i];
		if(Op[p].flag==1){
			Insert(Op[p].l1,Op[p].r1, 1);//插入颜色 
		}
		else{
			if(Op[p].flag==-1){
				Insert(Op[p].l1,Op[p].r1,-1);//删除颜色
			}
			else{
				if(Op[p].flag==2){
					Op[p].ans=Sum(Op[p].l2,Op[p].r2)-Sum(Op[p].l1-1,Op[p].r2)-Sum(Op[p].l2,Op[p].r1-1)+Sum(Op[p].l1-1,Op[p].r1-1);
				}
			}
		}
	}
}

int main(){
	freopen("luvletter.in","r",stdin);
	freopen("luvletter.out","w",stdout);
	
	scanf("%d%d",&M,&N);
	for(int i=1;i<=N;++i){
		for(int j=1;j<=M;++j){
			scanf("%d",&Map[i][j]);
			Add_Op_1(i,j,Map[i][j],1);//添加1种颜色
		}
	}
	
	scanf("%d",&Q);
	int Key=0;
	int l1,l2,r1,r2,c;
	for(int i=1;i<=Q;++i){
		scanf("%d",&Key);
		if(Key==1){//分解为两个操作 
			scanf("%d%d%d",&l1,&r1,&c);
			Add_Op_1(l1,r1,Map[l1][r1],-1);//删除1种颜色 
			Map[l1][r1]=c;
			Add_Op_1(l1,r1,Map[l1][r1], 1);//添加1种颜色 
		}
		else{
			scanf("%d%d%d%d%d",&l1,&l2,&r1,&r2,&c);//2 X1 X2 Y1 Y2 C
			if(l1>l2)	swap(l1,l2);
			if(r1>r2)	swap(r1,r2);
			Add_Op_2(l1,r1,l2,r2,c,2);//操作2查询 
		}
	}
	
	for(int i=tot;i>=1;--i){
		Add_Op_3(Op[i].color,i);
		flag[Op[i].color]=true;
	}
	
	for(int i=-66536;i<=100;++i){
		if(flag[i]==true)	Deal_Color(i);
		else continue;
	}
	
	for(int i=1;i<=tot;++i){
		if(Op[i].flag==2)	printf("%d\n",Op[i].ans);
	}
	
	fclose(stdin);
	fclose(stdout);
}