bzoj1176

题目描述

维护一个W*W的矩阵，初始值均为S（题目描述有误，这里的S没有任何作用！）.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

输入

第一行两个整数,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:表示输入结束

输出

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

样例输入

0 4

1 2 3 3

2 1 1 3 3

1 2 2 2

2 2 2 3 4

3

样例输出

3

5

---

bzoj2683

题目描述

同上，只是少了一个烦人的S

---

题解

CDQ分治

先读入所有修改和询问操作，将每个修改拆成4个。

然后按照CDQ分治的套路，按x排序，按id比较，按y查询。

（好像这道题我写的和别的CDQ分治题不一样。。。）

代码是1176的，2683直接去掉%*d即可。

（就算S真的有用，可以直接改ans的初始值，也是一样的）

#include 
     
      #include 
      
       using namespace std;struct data{    int x , y , v , p , id , opt;}a[800000] , tmp[800000];int n , tot , cnt , f[2000010] , ans[200000];bool cmp(data a , data b){    return a.x == b.x ? (a.y == b.y ? a.opt < b.opt : a.y < b.y) : a.x < b.x;}void add(int b , int c , int d , int t){    a[++tot].x = b , a[tot].y = c , a[tot].v = d , a[tot].id = tot , a[tot].opt = t;    if(t) a[tot].p = cnt;}void update(int x , int a){    int i;    for(i = x ; i <= n ; i += i & -i) f[i] += a;}int query(int x){    int i , ans = 0;    for(i = x ; i ; i -= i & -i) ans += f[i];    return ans;}void solve(int l , int r){    if(l == r) return;    int mid = (l + r) >> 1 , i , p1 = l , p2 = mid + 1;    for(i = l ; i <= r ; i ++ )    {        if(a[i].id <= mid && !a[i].opt) update(a[i].y , a[i].v);        if(a[i].id > mid && a[i].opt) ans[a[i].p] += a[i].v * query(a[i].y);    }    for(i = l ; i <= r ; i ++ ) if(a[i].id <= mid && !a[i].opt) update(a[i].y , -a[i].v);    for(i = l ; i <= r ; i ++ )    {        if(a[i].id <= mid) tmp[p1 ++ ] = a[i];        else tmp[p2 ++ ] = a[i];    }    for(i = l ; i <= r ; i ++ ) a[i] = tmp[i];    solve(l , mid) , solve(mid + 1 , r);}int main(){    int i , k , b , c , d , e;    scanf("%*d%d" , &n);    while(scanf("%d" , &k) && k != 3)    {        if(k == 1) scanf("%d%d%d" , &b , &c , &d) , add(b , c , d , 0);        else scanf("%d%d%d%d" , &b , &c , &d , &e) , cnt ++ , add(d , e , 1 , 1) , add(b - 1 , e , -1 , 1) , add(d , c - 1 , -1 , 1) , add(b - 1 , c - 1 , 1 , 1);    }    sort(a + 1 , a + tot + 1 , cmp);    solve(1 , tot);    for(i = 1 ; i <= cnt ; i ++ ) printf("%d\n" , ans[i]);    return 0;}