[BZOJ 1176&COGS 1752][BOI2007]Mokia（CDQ分治+树状数组）

逃离我推掉我的手 2022-01-12 01:17 190阅读 0赞

**Description**

维护一个W\*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

**Solution**

这道在BZOJ上是权限题啊…然而我在cogs上找到了它

依旧是CDQ分治的论文题，CDQ太强辣…

把查询拆成四个前缀和的形式，在CDQ分治中用时间把操作分为两部分，保证两部分的x各自单调（只有x较小的操作才能对较大的操作产生影响），然后用树状数组维护y这一维

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<algorithm>
    #define MAXN 2000005
    using namespace std;
    int s,w,c[MAXN],cnt=0,sign[MAXN],tim=0;
    struct Node
    {
        int opt,x,y,v,id,ans;
        Node(int opt=0,int x=0,int y=0,int v=0,int id=0):opt(opt),x(x),y(y),v(v),id(id),ans(0){}
    }O[200005],t[200005];
    bool cmp1(Node a,Node b){
        return a.x<b.x;}
    bool cmp2(Node a,Node b){
        return a.id<b.id;}
    int read()
    {
        int x=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){
            if(c=='-')f=-1;c=getchar();
        }
        while(c>='0'&&c<='9'){
            x=x*10+c-'0';c=getchar();
        }
        return x*f;
    }
    int lowbit(int x){
        return x&-x;}
    void add(int pos,int x)
    {
        while(pos<=w)
        {
            if(sign[pos]!=tim)c[pos]=0,sign[pos]=tim;
            c[pos]+=x,pos+=lowbit(pos);
        }
    }
    int query(int pos)
    {
        int res=0;
        while(pos>0)
        {
            if(sign[pos]==tim)res+=c[pos];
            pos-=lowbit(pos);
        }
        return res;
    }
    void merge(int l,int r)
    {
        if(l==r)return;
        int mid=(l+r)>>1;
        int i=l,j=mid+1,k=l;
        while(i<=mid&&j<=r)
        {
            if(O[i].x<O[j].x)t[k++]=O[i++];
            else t[k++]=O[j++];
        }
        while(i<=mid)t[k++]=O[i++];
        while(j<=r)t[k++]=O[j++];
        for(int i=l;i<=r;i++)O[i]=t[i];
    }
    void solve(int l,int r)
    {
        if(l==r)return;
        int mid=(l+r)>>1;
        for(int i=l,j=mid+1,k=l;k<=r;k++)
        if(O[k].id<=mid)t[i++]=O[k];
        else t[j++]=O[k];
        for(int i=l;i<=r;i++)O[i]=t[i];
        solve(l,mid);
        int j=l;tim++;
        for(int i=mid+1;i<=r;i++)
        {
            while(O[j].x<=O[i].x&&j<=mid)
            {
                if(O[j].opt==1)add(O[j].y,O[j].v);
                j++;
            }
            if(O[i].opt==2)O[i].ans+=query(O[i].y);
        }
        solve(mid+1,r);
        merge(l,r);
    }
    int main()
    {
        s=read(),w=read();
        while(1)
        {
            int opt=read();
            if(opt==3)break;
            if(opt==1)
            {
                int x=read(),y=read(),a=read();
                O[++cnt]=Node(opt,x,y,a,cnt);
            }
            else
            {
                int x1=read(),y1=read(),x2=read(),y2=read();
                O[++cnt]=Node(opt,x1-1,y1-1,1,cnt);
                O[++cnt]=Node(opt,x1-1,y2,-1,cnt);
                O[++cnt]=Node(opt,x2,y1-1,-1,cnt);
                O[++cnt]=Node(opt,x2,y2,1,cnt);
            }
        }
        sort(O+1,O+1+cnt,cmp1);
        solve(1,cnt);
        sort(O+1,O+1+cnt,cmp2);
        for(int i=1;i<=cnt;i++)
        if(O[i].opt==2)
        {
            int res=0;
            res+=O[i].ans*O[i].v,++i;
            res+=O[i].ans*O[i].v,++i;
            res+=O[i].ans*O[i].v,++i;
            res+=O[i].ans*O[i].v;
            printf("%d\n",res);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Zars19/p/6893697.html