bzoj1176 [Balkan2007]Mokia (CDQ 2D plane)

Description

Maintain a matrix of W*W, the initial value is S. each operation can increase the weight of a grid, or inquire the total weight of a sub matrix. Modify the operation number m < = 160000, inquiry number Q < = 10000, w < = 2000000

Input

Two integers in the first row, S,W; where S is the initial value of the matrix; W is the size of the matrix

Next, for each line, enter one of the following three types (without quotes):

"1 x y a"

"2 x1 y1 x2 y2"

"3"

Input 1: you need to increase the lattice weight of (x, y) (row x, column y) by a

Input 2: you need to find the sum of the weights of all the squares in the matrix whose lower left corner is (x1,y1) and upper right corner is (x2,y2), and output

Input 3: end of input

Output

For each input 2, output one line, i.e. the answer to input 2

Sample Input


0 4

1 2 3 3

2 1 1 3 3

1 2 2 2

2 2 2 3 4

3

Sample Output


3

5

[Submit][Status][Discuss]

analysis:
CDQ divide and conquer
Please refer to bzoj2683

The only difference is that there is an initial value
However, the initial value is all oriented, so we can simply add (matrix size * S) to ans

//Write code here
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=2000010;
struct node{
    int type,x,ya,yb,id,z;
};
node po[N<<1];
int tot,totx=0,ans[10010],t[N];
int n,S;

int get(int xa,int ya,int xb,int yb) {return (xb-xa+1)*(yb-ya+1)*S;}

void add(int x,int z){for (int i=x;i<=n;i+=(i&(-i))) t[i]+=z;}
int ask(int x) {int ans=0;for (int i=x;i>0;i-=(i&(-i))) ans+=t[i];return ans;}

int cmp(const node &a,const node &b)
{
    if (a.x!=b.x) return a.x<b.x;
    else return a.type<b.type;
}

void CDQ(int L,int R)
{
    if (L==R) return;
    int M=(L+R)>>1;
    CDQ(L,M); CDQ(M+1,R);

    sort(po+L,po+M+1,cmp);
    sort(po+M+1,po+R+1,cmp);

    int t1=L,t2=M+1,last=0;
    while (t2<=R)
    {
        while (t1<=M&&po[t1].type!=1) t1++;
        while (t2<=R&&po[t2].type==1) t2++;
        if (t1<=M&&po[t1].x<=po[t2].x)
        {
            add(po[t1].ya,po[t1].z);
            last=t1++;
        }
        else if (t2<=R)
        {
            if (po[t2].type==2) ans[po[t2].id]-=ask(po[t2].yb)-ask(po[t2].ya-1),t2++;
            else ans[po[t2].id]+=ask(po[t2].yb)-ask(po[t2].ya-1),t2++;
        }
    }

    for (int i=L;i<=last;i++)
        if (po[i].type==1) add(po[i].ya,-po[i].z);
}

int main()
{
    scanf("%d%d",&S,&n);
    for (;;)
    {
        int opt,xa,ya,xb,yb,z;
        scanf("%d",&opt);
        if (opt==1)
        {
            tot++;
            scanf("%d%d%d",&xa,&ya,&z);
            po[tot].type=1; po[tot].x=xa; po[tot].ya=ya; po[tot].z=z; 
        }
        else if (opt==2)
        {
            scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
            tot++; totx++;
            po[tot].type=2; po[tot].x=xa-1; 
            po[tot].ya=ya; po[tot].yb=yb; po[tot].id=totx;
            tot++;
            po[tot].type=3; po[tot].x=xb; 
            po[tot].ya=ya; po[tot].yb=yb; po[tot].id=totx;
            ans[totx]=get(xa,ya,xb,yb);
        }
        else break;
    }

    CDQ(1,tot);

    for (int i=1;i<=totx;i++) printf("%d\n",ans[i]); 
    return 0;
}

Posted on Wed, 27 May 2020 08:41:52 -0700 by novice_php