【题目链接】
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=96974
【题意】
定义查询操作与修改操作:1 x y z 为将格子(x,y)修改为z；2 x1 y1 x2 y2为查询以(x1,y1)为左上(x2,y2)为右下的子矩阵之和。
【思路】
cdq分治。
矩阵初始值都为s，所以先不考虑。
首先明确每一个修改操作都互不影响。然后把每一个对子矩阵的询问操作差分为对四个点的“前缀和”操作。
先把所有的操作按照x升序排列。进行cdq分治。
定义solve(l,r)为解决查询顺序在l,r区间内的操作，且在solve结束后保证区间按照x的递增排列。
1） 将区间按照查询先后顺序重排
2） Solve(l,mid)
3） 计算左区间对右区间的贡献。这时候左区间是按照x升序排列的，右区间是按照查询先后排列的，这样正好既可以保证求贡献时左区间x的单调与递归右区间时右区间内所有的查询都在。对于右区间的i，将左区间内x所有小于它的加入BIT，维护区间和，如果i是询问则查询BIT中所有y小于它的z之和。
4） Solve(mid+1,r)
5） 恢复区间，按照x升序排列
最后答案加上矩阵的s即可。
BIT的清理也可通过加时间戳的方式做到。
【代码】
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std; const int N = *1e6+;
const int inf = 1e9+; int n,sz,s,w;
int C[N],flag[N],T,tmp[N]; struct Node {
int x,y,z,pos,ans;
bool operator<(const Node& rhs) const{
return x<rhs.x;
}
Node(int x=,int y=,int z=) {
this->x=x,this->y=y,this->z=z;
pos=sz; ans=;
}
}q[N],t[N];
bool cmp(const Node& x,const Node& y)
{
return x.pos<y.pos;
} void add(int x,int v)
{
for(;x<=w;x+=x&-x)
if(flag[x]!=T) flag[x]=T,C[x]=v;
else C[x]+=v;
}
int query(int x)
{
int res=;
for(;x;x-=x&-x)
if(flag[x]==T) res+=C[x];
return res;
} void solve(int l,int r)
{
if(l==r) return ;
int mid=(l+r)>>;
int l1=l,l2=mid+,i,j;
for(i=l;i<=r;i++) {
if(q[i].pos<=mid) t[l1++]=q[i];
else t[l2++]=q[i];
}
memcpy(q+l,t+l,sizeof(q[])*(r-l+));
solve(l,mid);
j=l; T++;
for(i=mid+;i<=r;i++) {
for(;j<=mid&&q[j].x<=q[i].x;j++)
if(q[j].z!=-inf) add(q[j].y,q[j].z);
if(q[i].z==-inf) q[i].ans+=query(q[i].y);
}
solve(mid+,r);
l1=l,l2=mid+; int now=l;
while(l1<=mid||l2<=r) {
if(l2>r||l1<=mid&&q[l1]<q[l2]) t[now++]=q[l1++];
else t[now++]=q[l2++];
}
memcpy(q+l,t+l,sizeof(q[])*(r-l+));
} void read(int &x)
{
char c=getchar(); x=;int f=;
while(!isdigit(c)){ if(c=='-')f=-; c=getchar(); }
while(isdigit(c)) x=x*+c-'' , c=getchar();
x*=f;
} int main()
{
read(s),read(w);
int op,x1,y1,x2,y2,z;
while(read(op),op!=)
{
if(op==) {
read(x1),read(y1),read(z);
q[++sz]=(Node){x1,y1,z};
} else {
read(x1),read(y1),read(x2),read(y2);
q[++sz]=Node(x1-,y1-,-inf);
tmp[sz]=abs(x1-x2+)*abs(y1-y2+)*s;
q[++sz]=Node(x1-,y2,-inf);
q[++sz]=Node(x2,y1-,-inf);
q[++sz]=Node(x2,y2,-inf);
}
}
sort(q+,q+sz+);
solve(,sz);
sort(q+,q+sz+,cmp);
for(int i=;i<=sz;i++) if(q[i].z==-inf) {
int ans=tmp[i];
ans+=q[i++].ans;
ans-=q[i++].ans;
ans-=q[i++].ans;
ans+=q[i++].ans;
i--;
printf("%d\n",ans);
}
return ;
}
ps：鄙人并非权限汪，如代码不能AC概不负责 :)