danihao123's Blog

CDQ分治第一题……同时也是CDQ分治模板提。

感觉CDQ分治思路好秒啊……似乎在分治过程中做了个归并排序……

代码：

/**************************************************************
    Problem: 1176
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4364 ms
    Memory:17228 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxw=2000005;
const int maxq=10005;
const int maxn=160001+4*maxq;
int cnt=0;
struct Query{
  int ans_id;
  int x,y,d,v;
  Query(){}
  Query(int a,int b,int di,int ap){
    x=a;y=b;
    d=di;
    ans_id=ap;
  }
  Query(int a,int b,int value){
    x=a;y=b;
    v=value;
    d=0;
  }
  inline bool isQuery(){
    return d!=0;
  }
};
 
int w;
int T[maxw];
inline int lowbit(int x){
  return x&(-x);
}
inline void add(int p,int v){
  while(p<=w){
    T[p]+=v;
    p+=lowbit(p);
  }
}
inline int sum(int p){
  register int x=0;
  while(p>0){
    x+=T[p];
    p-=lowbit(p);
  }
  return x;
}
inline void clear(int p){
  while(p<=w && T[p]!=0){
    T[p]=0;
    p+=lowbit(p);
  }
}
 
Query Q[maxn],tmp[maxn];
int ans[maxn];
void CDQ(int L,int R){
  if(L==R){
    return;
  }
  int M=L+(R-L)/2;
  CDQ(L,M);
  CDQ(M+1,R);
  int p,p1,p2;
  for(p=1,p1=L,p2=M+1;p<=(R-L+1);p++){
    if((Q[p1].x<=Q[p2].x && p1<=M) || p2>R){
      tmp[p]=Q[p1];
      if(!Q[p1].isQuery()){
        add(Q[p1].y,Q[p1].v);
      }
      p1++;
    }else{
      tmp[p]=Q[p2];
      if(Q[p2].isQuery()){
        ans[Q[p2].ans_id]+=sum(Q[p2].y)*Q[p2].d;
      }
      p2++;
    }
  }
  for(p=1,p1=L;p<=(R-L+1);p++,p1++){
    if(!Q[p1].isQuery()){
      clear(Q[p1].y);
    }
    Q[p1]=tmp[p];
  }
}
 
int main(){
  int S,t,x,y,a,b;
  register int ans_cnt=0;
  scanf("%d%d",&S,&w);
  while(true){
    scanf("%d",&t);
    if(t==3){
      break;
    }
    scanf("%d%d%d",&x,&y,&a);
    // x++;y++;
    if(t==1){
      Q[++cnt]=Query(x,y,a);
    }else{
      scanf("%d",&b);
      // a++;b++;
      ans_cnt++;
      ans[ans_cnt]=(a-x+1)*(b-y+1)*S;
      Q[++cnt]=Query(a,b,1,ans_cnt);
      Q[++cnt]=Query(x-1,b,-1,ans_cnt);
      Q[++cnt]=Query(a,y-1,-1,ans_cnt);
      Q[++cnt]=Query(x-1,y-1,1,ans_cnt);
    }
  }
  CDQ(1,cnt);
  for(register int i=1;i<=ans_cnt;i++){
    printf("%d\n",ans[i]);
  }
  return 0;
}