| 记录编号 |
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);
}