bzoj1176: [Balkan2007]Mokia

bzoj1176: [Balkan2007]Mokia

题目链接

bzoj1176: [Balkan2007]Mokia

题解

cdq分治

代码

 
#include<cstdio> 
#include<algorithm> 
inline int read() { int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} while(c <= '9' &&c >= '0')x = x * 10 + c - '0',c = getchar(); return x * f;   
} 
const int maxw = 2000007;
const int maxn = 160000 + 10000 + 7;  
struct Query {int x,y,type,w,aid; Query(int Type = 0,int X = 0,int Y = 0,int W = 0,int Aid = 0) : type(Type),x(X),y(Y),w(W),aid(Aid){}; bool operator < (const Query & A)const { return x == A.x ? type < A.type : x < A.x; }
} ;
Query query[maxw / 10 + 7];
Query tmp[maxw / 10 + 7]; 
int ans[maxn],maxy;  
namespace BIT {
#define lowbit(x) (x & (-x))int sum[maxw << 1]; void add(int idx,int val) { //puts("1");for(;idx <= maxy; idx += lowbit(idx)) sum[idx] += val; } int query(int idx) { int ret = 0; for(;idx;idx -= lowbit(idx)) ret += sum[idx]; return ret;  } void clear(int idx) { for(;idx <= maxy;idx += lowbit(idx)) { if(sum[idx]) sum[idx] = 0; else break; } } 
} 
void cdq(int l,int r) { if(r - l <= 1) return; int mid = l + r >> 1; cdq(l,mid);cdq(mid,r); int p = l,q = mid,cnt = l; for(;p < mid && q < r;) {if(query[p] < query[q]) {if(query[p].type == 1) BIT::add(query[p].y,query[p].w); tmp[cnt ++] = query[p ++]; }else { if(query[q].type == 2) ans[query[q].aid] += query[q].w * BIT::query(query[q].y); tmp[cnt ++] = query[q ++];  } } while(p < mid) tmp[cnt ++] = query[p ++]; while(q < r)  {if(query[q].type == 2) ans[query[q].aid] += query[q].w * BIT::query(query[q].y); tmp[cnt ++] = query[q ++]; } for(int i = l;i < r;++ i) { BIT::clear(tmp[i].y); query[i] = tmp[i];  } 
} 
int qid = 0,aid = 0;
int main() { int type = read(), n = read(); maxy = n; for(int x,y,x1,y1,val;;) { type = read(); if(type == 3) break;  if(type == 1) {x = read(),y = read(),val = read();query[qid ++] = Query(1,x,y,val,0);  } if(type == 2) { x = read(),y = read(),x1 = read(),y1 = read(); query[qid ++] = Query(2,x - 1,y - 1,1,aid); query[qid ++] = Query(2,x - 1,y1,-1,aid); query[qid ++] = Query(2,x1,y - 1,-1,aid); query[qid ++] = Query(2,x1,y1,1,aid); aid ++; } } cdq(0,qid); for(int i = 0;i < aid;++ i) printf("%dn",ans[i]); return 0; 
} 


转载于:.html