题目描述

https://www.luogu.org/problemnew/show/P3960

 

分析

这道题我们可以发现，当我们对一个人(x,y)进行操作后，有影响的值有：

1、x,y从第x行消失

2、最后一列的第x个元素加入x行

3、消失的元素加入最后一列的最末端

那么我们建n+1棵树，n棵表示每行除去最后一列的所有元素，剩下一棵是最后一列的元素

那么我们每次操作时，删除x行的元素并加入最后一列的x号元素，输出，然后再加入x行的元素即可

但是我们发现数据是10^5级的，n^2空间复杂度不够，那么我们采用将连续的节点合并成区间，每次删除就把这个区间断成三个区间，删除中间区间即可

记住从尾部插入时要看看根是否为0，有时候分裂节点会导致根变为0（卡了我两天，噗）

 

#include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N=3e7+10;int n,m,q;struct Node {    int f,c[2];    ll l,r,sz;}t[N];int tcnt;struct Splay_Tree {    int rt;        inline int New(ll l,ll r) {        t[++tcnt].l=l;t[tcnt].r=r;        t[tcnt].sz=r-l;        return tcnt;    }        inline void Update(int x) {        t[x].sz=t[x].r-t[x].l+t[t[x].c[0]].sz+t[t[x].c[1]].sz;    }        inline int Witch(int x) {        return t[t[x].f].c[1]==x;    }        inline void Rotate(int x) {        int f=t[x].f,gf=t[f].f,lr=Witch(x);        t[x].f=gf;        if (gf) t[gf].c[Witch(f)]=x;        t[t[f].c[lr]=t[x].c[lr^1]].f=f;        t[t[x].c[lr^1]=f].f=x;        Update(f);Update(x);    }        inline void Splay(int x) {        for (;t[x].f;Rotate(x))            if (t[t[x].f].f) Rotate(Witch(x)==Witch(t[x].f)?t[x].f:x);        rt=x;    }        inline int Split(int x,ll mid) {        mid=mid+t[x].l;        int nw=New(mid,t[x].r);        t[x].r=mid;        if (!t[x].c[1]) t[t[x].c[1]=nw].f=x;        else {            int s=t[x].c[1];            while (t[s].c[0]) s=t[s].c[0];            t[t[s].c[0]=nw].f=s;            while (s!=x) Update(s),s=t[s].f;        }        Splay(nw);        return nw;    }        inline ll DelKth(ll k) {        int x=rt;        while (x) {            if (t[t[x].c[0]].sz>=k) x=t[x].c[0];            else {                k-=t[t[x].c[0]].sz;                if (k<=t[x].r-t[x].l) {                    if (k!=t[x].r-t[x].l) Split(x,k);                    if (k!=1) x=Split(x,k-1);                    break;                }                k-=t[x].r-t[x].l,x=t[x].c[1];            }        }        Splay(x);        t[t[x].c[0]].f=t[t[x].c[1]].f=0;        if (!t[x].c[0]) rt=t[x].c[1];        else {            int s=t[x].c[0];            while (t[s].c[1]) s=t[s].c[1];            Splay(s);            Update(rt=t[t[s].c[1]=t[x].c[1]].f=s);        }        return t[x].l;    }        inline void PushInBack(ll dat) {        int x=rt,nw=New(dat,dat+1);        if (!rt) {            rt=nw;            return;        }        while (t[x].c[1]) x=t[x].c[1];        Splay(x);        Update(t[t[x].c[1]=nw].f=x);    }    }s[N];int main() {    scanf("%d%d%d",&n,&m,&q);    for (int i=1;i<=n;i++) s[i].rt=s[i].New(1ll*(i-1)*m+1,1ll*i*m);    s[0].rt=s[0].New(1ll*m,1ll*m+1);    for (int i=2;i<=n;i++) s[0].PushInBack(1ll*i*m);    for (int i=1;i<=q;i++) {        int x,y;        scanf("%d%d",&x,&y);        s[x].PushInBack(s[0].DelKth(x));        ll hasbeendel;        printf("%lld\n",hasbeendel=s[x].DelKth(y));        s[0].PushInBack(hasbeendel);    }}