BZOJ1176 Mokia

发表于 2017-11-27 分类于题解

题面

传送门维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000. 操作一为增加，操作二为查询 ### 题解一看\(w\le 2\times 10^6,M\le 1.6\times 10^5,Q \le 1\times 10^4\)就知道不能直接二维线段树或二维数状数组爆搞了。空间\(O(w^2)\)就算离散化也是\(O((M+4Q)^2)\)。

我们把每一个操作二拆成四个查询操作,每个查询操作\((x,y)\)代表查询\(\sum_{i=1}^x\sum_{j=1}^yw_{i,j}\)，其中\(w_{i,j}\)表示\((i,j)\)格子的权值。

设按顺序第i个操作的x坐标为\(X_i\),y坐标为\(Y_i\)(修改的格子位置或查询的(x,y))

发现修改操作a对查询操作b有影响当且仅当\(a<b,X_a \le X_b,Y_a \le Y_b\)全部满足。

这就是个三维偏序啊。

直接来一波CDQ分治

/*
Author: CNYALI_LK
LANG: C++
PROG: 1176.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
    int w=0,base=1;
    char c;
    while(!isdigit(c=getchar())){if(c=='-')base=-base;}
    while(isdigit(c)){w=w*10+c-'0';c=getchar();}
    return w*base;
}
int s,w;
struct cz{
    int a,b,c,d,tim,ans;
    cz (int t=0,int u=0,int o=0,int i=0,int p=0){
        a=u;b=o;c=i;d=p;tim=t;
        ans=0;
    }
};
cz a[233333],b[233333];
int tp[233333];
int cx[2333333];
int c[233333],ans[233333];
#define lowbit(x) (x&(-x))
void add(int x,int y){
    while(x<=w){
        c[x]+=y;
        x+=lowbit(x);
    }
}
int sum(int x){
    int cnt=0;
    while(x){
        cnt+=c[x];
        x^=lowbit(x);
    }
    return cnt;
}
void cdq(int l,int r){
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    int s1=l,s2=mid+1,t=l-1;
    while(s2<=r){
        while(s1<=mid&&a[s1].b<=a[s2].b){
            b[++t]=a[s1];
            if(!tp[a[s1].tim])add(a[s1].c,a[s1].d);
            ++s1;
        }
        if(tp[a[s2].tim])a[s2].ans+=sum(a[s2].c);
        b[++t]=a[s2];
        ++s2;
    }
    for(int i=l;i<s1;++i)if(!tp[a[i].tim])add(a[i].c,-a[i].d);
    while(s1<=mid){b[++t]=a[s1];++s1;}
    for(int i=l;i<=r;++i)a[i]=b[i];
}
int main(){
#ifdef cnyali_lk
    freopen("1176.in","r",stdin);
    freopen("1176.out","w",stdout);
#endif
    int t,al,b,c,d,n=0,m=0,l=0;
    s=read();w=read();
    while((t=read())^3){
        al=read();b=read();c=read();
        if(t==1){
            a[++n]=cz(++m,t,al,b,c);
            cx[b]=1;
            tp[m]=0;
        }
        else{
            d=read();
            a[++n]=cz(++m,t,c,d,1);
            a[++n]=cz(m,t,al-1,b-1,1);
            a[++n]=cz(m,t,c,b-1,-1);
            a[++n]=cz(m,t,al-1,d,-1);
            cx[d]=cx[b-1]=1;
            tp[m]=1;
        }
    }
    for(int i=0;i<=w;++i)if(cx[i])cx[i]=++l;
    w=l;
    for(int i=1;i<=n;++i)a[i].c=cx[a[i].c];
    cdq(1,n);
//  for(int i=1;i<=n;++i)printf("%d(%d,%d,%d,%d) -> %d\n",a[i].tim,a[i].a,a[i].b,a[i].c,a[i].d,a[i].d*a[i].ans);
    for(int i=1;i<=n;++i)ans[a[i].tim]+=a[i].d*(a[i].ans+a[i].b*a[i].c*s);
    for(int i=1;i<=m;++i)if(tp[i])printf("%d\n",ans[i]);
    return 0;
}