[BZOJ1176][Balkan2007]Mokia cdq+树状数组

1176: [Balkan2007]Mokia

Time Limit: 30 Sec Memory Limit: 162 MB
Submit: 3134 Solved: 1395
[Submit][Status][Discuss]

Description

维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

Input

第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小

接下来每行为一下三种输入之一(不包含引号):

"1 x y a"

"2 x1 y1 x2 y2"

"3"

输入1:你需要把(x,y)(第x行第y列)的格子权值增加a

输入2:你需要求出以左下角为(x1,y1),右上角为(x2,y2)的矩阵内所有格子的权值和,并输出

输入3:表示输入结束

Output

对于每个输入2,输出一行,即输入2的答案

Sample Input

0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

Sample Output

3
5

HINT

保证答案不会超过int范围

Source

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #define maxq 800000

 #define ll long long

 using namespace std;

 struct data {ll id,x,y,tp,f,a,p;}t[maxq],tmp[maxq];

 ll s,w;

 ll ans[maxq];

 int cnt;

 bool cmp1(data t1,data t2) {return t1.x==t2.x?t1.id<t2.id:t1.x<t2.x;}

 int ask;

 ll sum[];

 int lowbit(int x) {return x&(-x);}

 bool vis[maxq];

 void insert(int x,ll ad) {for(int i=x;i<=w;i+=lowbit(i)) sum[i]+=ad;}

 ll query(int x) {

     ll re=;

     for(int i=x;i;i-=lowbit(i)) re+=sum[i];

     return re;

 }

 void cdq(int l,int r) {

     if(l==r) return;

     int mid=l+r>>;

     int lp=l,rp=mid+;

     for(int i=l;i<=r;i++) {

         if(t[i].tp==) {

             if(t[i].id>mid){ans[t[i].p]+=t[i].f*query(t[i].y);vis[t[i].p]=;}

          }

         else {if(t[i].id<=mid) insert(t[i].y,t[i].a);}

     }

     for(int i=l;i<=r;i++) if(t[i].tp==&&t[i].id<=mid) insert(t[i].y,-t[i].a);

     for(int i=l;i<=r;i++) {

         if(t[i].id<=mid) tmp[lp++]=t[i];

         else tmp[rp++]=t[i];

     }

     for(int i=l;i<=r;i++) t[i]=tmp[i];

     cdq(l,mid);cdq(mid+,r);

 }

 void add(ll x1,ll y1,ll id,ll tp,ll f) {t[cnt].p=id;t[cnt].f=f;t[cnt].tp=tp;t[cnt].x=x1;t[cnt].y=y1;t[cnt].id=cnt;}

 int main() {

     scanf("%lld%lld",&s,&w);

     int tp;

     while(scanf("%d",&tp)) {

         ask++;

         if(tp==) break;

         if(tp==) {cnt++;scanf("%lld%lld%lld",&t[cnt].x,&t[cnt].y,&t[cnt].a);t[cnt].id=cnt;t[cnt].tp=;}

         else {

             ll x1,y1,x2,y2;

             scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);

             cnt++;add(x1-,y1-,ask,,);cnt++;add(x2,y2,ask,,);

             cnt++;add(x1-,y2,ask,,-);cnt++;add(x2,y1-,ask,,-);

             ans[ask]+=(y2-y1+)*(x2-x1+)*s;

         }

     }

     sort(t+,t+cnt+,cmp1);

     cdq(,cnt);

     for(int i=;i<=ask;i++) if(vis[i]) printf("%lld\n",ans[i]);

 }

巴特西