题目链接：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这一维直接就可以用树状数组乱搞了。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxb = 2e6+;
struct Node
{
int x,y,delt;
int flag,idx;
Node(){}
Node(int _x,int _y,int _delt,int _flag,int _idx):
x(_x),y(_y),delt(_delt),flag(_flag),idx(_idx){};
bool operator < (const Node &rhs)const
{
return x < rhs.x || (x == rhs.x && y < rhs.y);
}
}a[];
struct BIT
{
int c[maxb],MAX;
inline int lowbit(int x)
{
return x & -x;
}
void add(int x,int val)
{
while (x <= MAX)
{
c[x] += val;
x += lowbit(x);
}
}
int sum(int x)
{
int res = ;
while (x > )
{
res += c[x];
x -= lowbit(x);
}
return res;
}
}arr; //---------------------------------------------
int ans[];
void CDQ(int l,int r)
{
if (l == r)
return;
int mid = (l + r) >> ;
CDQ(l,mid);
CDQ(mid+,r);
int j = l;
for (int i = mid + ; i <= r; i++)
{
if (a[i].flag == )
{
for ( ; j <= mid && a[j].x <= a[i].x; j++)
{
if (a[j].flag == )
{
arr.add(a[j].y,a[j].delt);
}
}
ans[a[i].idx] += arr.sum(a[i].y) * a[i].delt;
}
}
for (int i = l; i < j; i++)
if (a[i].flag == )
arr.add (a[i].y,-a[i].delt);
inplace_merge (a+l,a+mid+,a+r+); // 合并区间 [l,mid+1) [mid+1,r+1)
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
int s,w;
while (~scanf ("%d%d",&s,&w))
{
int op;
int tot = ,totq = ;
arr.MAX = w;
memset(ans,,sizeof(ans));
while (scanf ("%d",&op), op != )
{
if (op == )
{
int x,y,delt;
scanf ("%d%d%d",&x,&y,&delt);
a[tot] = Node(x,y,delt,,tot);
tot++;
}
if (op == )
{
int x1,y1,x2,y2;
scanf ("%d%d%d%d",&x1,&y1,&x2,&y2);
a[tot] = Node(x1-, y1-, , , totq); tot++;
a[tot] = Node(x2, y1-, -, , totq); tot++;
a[tot] = Node(x1-, y2, -, , totq); tot++;
a[tot] = Node(x2, y2, , , totq); tot++;
totq++;
}
}
CDQ (,tot-);
for (int i = ; i < totq; i++)
printf("%d\n",ans[i]);
}
return ;
}