[JOISC2020] 掃除的题解

Seauy · 2022-12-24 22:57:35 · 题解

题目链接

题目大意

一开始所有 m 个点都在 x=0,y=0,x+y=n 围成的三角形内。
支持四种操作：

查询某个点的位置。
把 y\leq l 的点的 x 与 n-l 取最大值。
把 x\leq l 的点的 y 与 n-l 取最大值。
插入一个在三角形内的点。

题面里 H 和 V 的含义反了，底下的样例解释是对的。

Solution

给个 CDQ分治的做法。

一般的 CDQ 是通过时间上的分治做到计算每对修改-查询的影响，在这题里类似，可以计算每对插入-若干修改-查询。

类似于猫树，每个插入-查询在中点分割他们的分治区域内处理好。比如现在 CDQ 的左区间为 [L,mid]，右区间为 (mid,R]，首先所有在左区间插入的点都得处于完成了 [L,mid] 所有修改后的状态，这个注意一下 CDQ 的顺序即可，可以先递归 [L,mid] 再递归 (mid,R]，然后处理跨过 mid 的插入-查询，最后想办法把左区间插入的点都改成经过 (mid,R] 所有修改后的状态。

每个分治区域内都是一组静态问题，即没有插入只有修改和查询。可以发现所有修改的矩形的并的轮廓线上的点很好维护，因为如果把他们先按 x 后按 y 坐标排好序，每次修改相当于区间 x/y 赋值。所以可以先扫描线求出每个点移动到轮廓线上的时间，用平衡树维护即可。

时间 O((m+q)\log^2 (m+q))，空间 O(m+q)。

所以其实去掉修改全在斜边上的限制也能这样做。

Code

#include<bits/stdc++.h>
#define Lson(x) node[x].Son[0]
#define Rson(x) node[x].Son[1]
#define fa(x) node[x].father
using namespace std;

typedef long long ll;

const int MAXN=1e9,MAXM=5e5,MAXQ=1e6,MAXT=MAXM+MAXQ;

inline int Read()
{
    int res;char c;
    while(1) {c=getchar();if('0'<=c && c<='9') {res=c-'0';break;}}
    while(1) {c=getchar();if('0'<=c && c<='9') res=res*10+c-'0';else break;}
    return res;
}

int n,m,q;

struct Query
{
    int opt,x,ID;
    inline int X()
    {
        if(opt==2) return n-x;
        return x;
    }
}ope[MAXT+5];int T;

struct Point
{
    int x,y;
    inline void Scan() {x=Read(),y=Read();}
    inline void Print() {printf("%d %d\n",x,y);}
}ver[MAXT+5];

Point ans[MAXQ+5];int anum;
int Tim[MAXT+5];//每个点出现的时间

struct fhqTreap
{
    int Son[2],tag1,tag2,KEY;
    //对于操作：最小时间戳，操作 x 坐标
    //对于灰尘：x 懒标记，y 懒标记
    int father;
}node[MAXT+5];int root;

inline void PushUp(int now)
{
    node[now].tag1=now;
    if(Lson(now)) node[now].tag1=min(node[now].tag1,node[Lson(now)].tag1);
    if(Rson(now)) node[now].tag1=min(node[now].tag1,node[Rson(now)].tag1);
}
void SplitOpe(int now,int &a,int &b,int x)
{
    if(!now) {a=b=0;return;}
    if(node[now].tag2<=x) a=now,SplitOpe(Rson(now),Rson(a),b,x);
    else b=now,SplitOpe(Lson(now),a,Lson(b),x);
    PushUp(now);
}
int MergeOpe(int a,int b)
{
    if(!a || !b) return a^b;
    if(node[a].KEY>node[b].KEY)
    {
        Rson(a)=MergeOpe(Rson(a),b);
        PushUp(a);
        return a;
    }
    Lson(b)=MergeOpe(a,Lson(b));
    PushUp(b);
    return b;
}
inline int GetMin(int L,int R)
{
    int a,b,c;
    SplitOpe(root,a,b,L-1);
    SplitOpe(b,b,c,R);
    int res=node[b].tag1;
    root=MergeOpe(MergeOpe(a,b),c);
    return res;
}
inline void InsertOpe(int x)
{
    Lson(x)=Rson(x)=0;
    node[x].tag1=x;
    node[x].tag2=ope[x].X();
    node[x].KEY=rand();
    int a,b;
    SplitOpe(root,a,b,node[x].tag2);
    root=MergeOpe(MergeOpe(a,x),b);
}

Point Ask(int x)
{
    Point res=ver[x];
    while(1)
    {
        if(node[x].tag1) res.x=node[x].tag1;
        if(node[x].tag2) res.y=node[x].tag2;
        if(fa(x)) x=fa(x);
        else break;
    }
    return res;
}
inline void PushDown(int now)
{
    if(node[now].tag1)
    {
        if(Lson(now)) node[Lson(now)].tag1=ver[Lson(now)].x=node[now].tag1;
        if(Rson(now)) node[Rson(now)].tag1=ver[Rson(now)].x=node[now].tag1;
        node[now].tag1=0;
    }
    if(node[now].tag2)
    {
        if(Lson(now)) node[Lson(now)].tag2=ver[Lson(now)].y=node[now].tag2;
        if(Rson(now)) node[Rson(now)].tag2=ver[Rson(now)].y=node[now].tag2;
        node[now].tag2=0;
    }
}
void SplitX(int now,int &a,int &b,int x)
{
    if(!now) {a=b=0;return;}
    PushDown(now);
    if(ver[now].x<=x)
    {
        a=now;
        if(Rson(a)) fa(Rson(a))=0;
        SplitX(Rson(now),Rson(a),b,x);
        if(Rson(a)) fa(Rson(a))=a; 
    }
    else
    {
        b=now;
        if(Lson(b)) fa(Lson(b))=0;
        SplitX(Lson(now),a,Lson(b),x);
        if(Lson(b)) fa(Lson(b))=b;
    }
}
void SplitY(int now,int &a,int &b,int y)
{
    if(!now) {a=b=0;return;}
    PushDown(now);
    if(ver[now].y<=y)
    {
        b=now;
        if(Lson(b)) fa(Lson(b))=0;
        SplitY(Lson(now),a,Lson(b),y);
        if(Lson(b)) fa(Lson(b))=b;
    }
    else
    {
        a=now;
        if(Rson(a)) fa(Rson(a))=0;
        SplitY(Rson(now),Rson(a),b,y);
        if(Rson(a)) fa(Rson(a))=a;
    }
}
void SplitXY(int now,int &a,int &b,int x,int y)
{
    if(!now) {a=b=0;return;}
    PushDown(now);
    if(ver[now].x<x || (ver[now].x==x && ver[now].y>y))
    {
        a=now;
        if(Rson(a)) fa(Rson(a))=0;
        SplitXY(Rson(now),Rson(a),b,x,y);
        if(Rson(a)) fa(Rson(a))=a; 
    }
    else
    {
        b=now;
        if(Lson(b)) fa(Lson(b))=0;
        SplitXY(Lson(now),a,Lson(b),x,y);
        if(Lson(b)) fa(Lson(b))=b;
    }
}
int MergeAsh(int a,int b,int c)
{
    if(!a || !b) {if(a^b) fa(a^b)=c; return a^b;}
    PushDown(a),PushDown(b);
    if(node[a].KEY>node[b].KEY)
    {
        fa(a)=c;
        Rson(a)=MergeAsh(Rson(a),b,a);
        return a;
    }
    fa(b)=c;
    Lson(b)=MergeAsh(a,Lson(b),b);
    return b;
}
inline void InsertAsh(int x)
{
    Lson(x)=Rson(x)=fa(x)=0;
    node[x].tag1=node[x].tag2=0;
    node[x].KEY=rand();
    int a,b;
    SplitXY(root,a,b,ver[x].x,ver[x].y);
    root=MergeAsh(MergeAsh(a,x,0),b,0);
}
inline void Hmove(int x)
{
    int a,b,c;
    SplitX(root,b,c,n-x);
    SplitY(b,a,b,x);
    if(b) node[b].tag1=ver[b].x=n-x;
    root=MergeAsh(MergeAsh(a,b,0),c,0);
}
inline void Vmove(int x)
{
    int a,b,c;
    SplitX(root,b,c,x);
    SplitY(b,a,b,n-x);
    if(b) node[b].tag2=ver[b].y=n-x;
    root=MergeAsh(MergeAsh(a,b,0),c,0);
}

void AllPushDown(int now)
{
    if(!now) return;
    PushDown(now);
    AllPushDown(Lson(now));
    AllPushDown(Rson(now));
}

int Head[MAXT+5],nxt[MAXT+5];
inline void Push(int x,int v)
{
    if(!x) return;
    nxt[v]=Head[x],Head[x]=v;
}
bool V[MAXT+5];
void CDQ(int L,int R)
{
    if(L==R) return;
    int mid=(L+R)>>1;
    CDQ(L,mid),CDQ(mid+1,R);
    root=0;
    for(int i=mid+1;i<=R;i++)
        if(ope[i].opt==2 || ope[i].opt==3) InsertOpe(i),Head[i]=0;
    for(int i=L,x;i<=mid;i++)
        if(ope[i].opt==4)
        {
            x=ope[i].x;//灰尘编号 
            Push(GetMin(ver[x].x,n-ver[x].y),x);
            V[x]=0;
        }
    root=0;
    for(int i=mid+1;i<=R;i++)
        if(ope[i].opt==1)
        {
            if(L<=Tim[ope[i].x] && Tim[ope[i].x]<=mid)
            {
                if(V[ope[i].x]) ans[ope[i].ID]=Ask(ope[i].x);
                else ans[ope[i].ID]=ver[ope[i].x];
            }
        }
        else if(ope[i].opt==2)
        {
            Hmove(ope[i].x);
            for(int j=Head[i];j;j=nxt[j])
                V[j]=1,ver[j].x=n-ope[i].x,InsertAsh(j);
        }
        else if(ope[i].opt==3)
        {
            Vmove(ope[i].x);
            for(int j=Head[i];j;j=nxt[j])
                V[j]=1,ver[j].y=n-ope[i].x,InsertAsh(j);
        }
    AllPushDown(root);
}

int main()
{
    srand(unsigned(time(0)));
    n=Read(),m=Read(),q=Read();
    for(int i=1;i<=m;i++) ver[i].Scan(),ope[++T]=Query{4,i,0},Tim[i]=T;
    for(int opt,x;q--;)
    {
        opt=Read();
             if(opt==1) x=Read(),ope[++T]=Query{1,x,++anum};
        else if(opt==2) x=Read(),ope[++T]=Query{2,x,0};//向右 
        else if(opt==3) x=Read(),ope[++T]=Query{3,x,0};//向上 
        else ver[++m].Scan(),ope[++T]=Query{4,m,0},Tim[m]=T;
    }
    CDQ(1,T);
    for(int i=1;i<=anum;i++) ans[i].Print();
    return 0;
}

[JOISC2020] 掃除 的题解

题目大意

Solution

Code

[JOISC2020] 掃除的题解