首页 > 代码库 > BZOJ1176---[Balkan2007]Mokia （CDQ分治 + 树状数组）
BZOJ1176---[Balkan2007]Mokia （CDQ分治 + 树状数组）
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1176
CDQ第一题，warush了好久。。
CDQ分治推荐论文：
1 《从＜Cash＞谈一类分治算法的应用》 陈丹琦
2 《浅谈数据结构题的几个非经典解法》 许昊然
关于CDQ分治，两种要求：①操作不相互影响 ②可以离线处理
题目描述是有问题的，，初始时 全部为0，不是s
题意：二维平面内，两种操作，1 x y v ，位于（x,y）的值加上v.。。2 x1,y1,x2,y2，，（x1,y1） (x2,y2)分别矩形的左上角右下角，查询矩形内所有元素的和。
大致思路，在x这一维上进行分治，然后y这一维直接就可以用树状数组乱搞了。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int maxb = 2e6+10; 7 struct Node 8 { 9 int x,y,delt; 10 int flag,idx; 11 Node(){} 12 Node(int _x,int _y,int _delt,int _flag,int _idx): 13 x(_x),y(_y),delt(_delt),flag(_flag),idx(_idx){}; 14 bool operator < (const Node &rhs)const 15 { 16 return x < rhs.x || (x == rhs.x && y < rhs.y); 17 } 18 }a[400000]; 19 struct BIT 20 { 21 int c[maxb],MAX; 22 inline int lowbit(int x) 23 { 24 return x & -x; 25 } 26 void add(int x,int val) 27 { 28 while (x <= MAX) 29 { 30 c[x] += val; 31 x += lowbit(x); 32 } 33 } 34 int sum(int x) 35 { 36 int res = 0; 37 while (x > 0) 38 { 39 res += c[x]; 40 x -= lowbit(x); 41 } 42 return res; 43 } 44 }arr; 45 46 //--------------------------------------------- 47 int ans[200000]; 48 void CDQ(int l,int r) 49 { 50 if (l == r) 51 return; 52 int mid = (l + r) >> 1; 53 CDQ(l,mid); 54 CDQ(mid+1,r); 55 int j = l; 56 for (int i = mid + 1; i <= r; i++) 57 { 58 if (a[i].flag == 2) 59 { 60 for ( ; j <= mid && a[j].x <= a[i].x; j++) 61 { 62 if (a[j].flag == 1) 63 { 64 arr.add(a[j].y,a[j].delt); 65 } 66 } 67 ans[a[i].idx] += arr.sum(a[i].y) * a[i].delt; 68 } 69 } 70 for (int i = l; i < j; i++) 71 if (a[i].flag == 1) 72 arr.add (a[i].y,-a[i].delt); 73 inplace_merge (a+l,a+mid+1,a+r+1); // 合并区间 [l,mid+1) [mid+1,r+1) 74 } 75 int main(void) 76 { 77 #ifndef ONLINE_JUDGE 78 freopen("in.txt","r",stdin); 79 #endif // ONLINE_JUDGE 80 int s,w; 81 while (~scanf ("%d%d",&s,&w)) 82 { 83 int op; 84 int tot = 1,totq = 1; 85 arr.MAX = w; 86 memset(ans,0,sizeof(ans)); 87 while (scanf ("%d",&op), op != 3) 88 { 89 if (op == 1) 90 { 91 int x,y,delt; 92 scanf ("%d%d%d",&x,&y,&delt); 93 a[tot] = Node(x,y,delt,1,tot); 94 tot++; 95 } 96 if (op == 2) 97 { 98 int x1,y1,x2,y2; 99 scanf ("%d%d%d%d",&x1,&y1,&x2,&y2);100 a[tot] = Node(x1-1, y1-1, 1, 2, totq); tot++;101 a[tot] = Node(x2, y1-1, -1, 2, totq); tot++;102 a[tot] = Node(x1-1, y2, -1, 2, totq); tot++;103 a[tot] = Node(x2, y2, 1, 2, totq); tot++;104 totq++;105 }106 }107 CDQ (1,tot-1);108 for (int i = 1; i < totq; i++)109 printf("%d\n",ans[i]);110 }111 return 0;112 }
BZOJ1176---[Balkan2007]Mokia （CDQ分治 + 树状数组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。