【Codeforces 575I】Robots protection

mrsrz 1月 16, 2020

CDQ 分治。

题目大意：

给定 $n\times n$ 的矩形，有两种操作：

让一个等腰直角三角形的区域的点的值加一。
询问一个点的值。

题解：

如果是矩形区域则很容易使用二维数据结构/CDQ 分治维护。

考虑把三角形看成一个平行四边形的一部分，并且右端点无限延伸。平行四边形区域的加法是可以像矩形一样维护的，分两种不同方向讨论即可。

考虑减去多余的贡献。减去多余的那部分，相当于减去一个矩形区域（都是无限延伸的）。这个也可以维护。

因此对三种四边形使用 CDQ 分治或者树套树维护即可。

时间复杂度 $O(q\log q\log n)$（CDQ 分治）或 $O(q\log^2 n)$（树套树）。

Code：

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+5,M=18888;
int n,m;
struct fwt{
    int b[M];
    inline void add(int i,int x){for(;i<M;i+=i&-i)b[i]+=x;}
    inline int ask(int i){int x=0;for(;i;i&=i-1)x+=b[i];return x;}
    inline void modify(int l,int r,const int&x){add(l,x),add(r+1,-x);}
}B[3];
int ans[N],k;
struct que{
    int op,x,l,r,id;
    inline bool operator<(const que&rhs)const{return x<rhs.x;}
}A[N*4],tmp[N*4];// | 0  / 1  \ 2
void solve(int l,int r){
    if(l>=r)return;
    const int mid=l+r>>1;
    for(int i=l;i<=r;++i)tmp[i]=A[i];
    sort(tmp+l,tmp+mid+1);
    sort(tmp+mid+1,tmp+r+1);
    int L=l,R=mid+1;
    while(L<=mid&&R<=r)
    if(tmp[L].x<=tmp[R].x){
        if(tmp[L].op<3)B[tmp[L].op].modify(tmp[L].l,tmp[L].r,tmp[L].id);
        ++L;
    }else{
        if(tmp[R].op==3){
            int y=tmp[R].r,x=tmp[R].x;
            ans[tmp[R].id]+=B[0].ask(y)+B[1].ask(x+y)+B[2].ask(y-x+n);
        }
        ++R;
    }
    for(;R<=r;++R)
    if(tmp[R].op==3){
        int y=tmp[R].r,x=tmp[R].x;
        ans[tmp[R].id]+=B[0].ask(y)+B[1].ask(x+y)+B[2].ask(y-x+n);
    }
    for(int i=l;i<L;++i)
    if(tmp[i].op<3)B[tmp[i].op].modify(tmp[i].l,tmp[i].r,-tmp[i].id);
    solve(l,mid);
    solve(mid+1,r);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        ans[i]=-1;
        int op;
        scanf("%d",&op);
        if(op==1){
            int dir,x,y,len;
            scanf("%d%d%d%d",&dir,&x,&y,&len);
            switch(dir){
                case 1:{
                    A[++k]=(que){0,x,1,y-1,-1},A[++k]=(que){0,x+len+1,1,y-1,1};
                    A[++k]=(que){1,x,1,x+y+len,1},A[++k]=(que){1,x+len+1,1,x+y+len,-1};
                    break;
                }
                case 2:{
                    A[++k]=(que){0,x,y+1,n,-1},A[++k]=(que){0,x+len+1,y+1,n,1};
                    A[++k]=(que){2,x,y-x+n-len,2*n,1},A[++k]=(que){2,x+len+1,y-x+n-len,2*n,-1};
                    break;
                }
                case 3:{
                    A[++k]=(que){0,x-len,1,y-1,-1},A[++k]=(que){0,x+1,1,y-1,1};
                    A[++k]=(que){2,x-len,1,y-x+n+len,1},A[++k]=(que){2,x+1,1,y-x+n+len,-1};
                    break;
                }
                case 4:{
                    A[++k]=(que){0,x-len,y+1,n,-1},A[++k]=(que){0,x+1,y+1,n,1};
                    A[++k]=(que){1,x-len,x+y-len,2*n,1},A[++k]=(que){1,x+1,x+y-len,2*n,-1};
                    break;
                }
            }
        }else{
            int x,y;
            scanf("%d%d",&x,&y);
            ans[i]=0;
            A[++k]=(que){3,x,y,y,i};
        }
    }
    solve(1,k);
    for(int i=1;i<=m;++i)
    if(ans[i]!=-1)printf("%d\n",ans[i]);
    return 0;
}