题解 P3960 【列队】

· · 题解

一看到这道题就想到了Splay，可惜感觉有点奇怪，搞不出来，肯定是因为我太菜了。

然后听说我的同学用动态开点线段树A了CSP树的重心，我就在思考可不可以使用动态开点A了这道题。

发现可以

思考子问题（O(n^2)太水了，就不说了）：

序列A，每次问一个坐标x，求A_x，然后把这个个数放在最后面。(|A|\le1e5,q\le1e5)

这题可以用Splay翻转区间做，但是如果有n个A数组，这岂不是要MLE？我就思索有没有动态开点Splay，很可惜，我搞不出来。

于是便想到了动态开点线段树，可是如何维护呢？？。

好方法

1 2 3 4 5 序列中询问4次，先把序列变成这样：

1 2 3 4 5 0 0 0 0 -> 0代表未填的坑

同时有一个B数组，由阴阳组成（文言带师，代表这个数有没有

则一开始A，B数组如下

1 2 3 4 5 0 0 0 0

1 1 1 1 1 1 1 1 1

询问x=2，此时在A数组最后加一个2（填一个坑），位置2的B设为0，代表被干掉了

1 2 3 4 5 2 0 0 0

1 0 1 1 1 1 1 1 1

然后询问掉1，4这两个数

1 2 3 4 5 2 1 4 0

0 0 1 0 1 1 1 1 1

注意到每次操作时，询问位置k，只需要找到第k个1代表的位置即可

推广

推广到有n行

对每一行开一珂动态开点线段树，对最后一列开一珂

每次询问x,y，若x=m特别讨论，用上面的特殊情况。

否则，就把x,y加在最后一列的最后一个后面，删掉x,m，加在第x行里，由于不能存整个图，就用vector维护

以上是方法

Trick

动态开点时直接询问+修改即可，目前Rank1（除了之前奇奇怪怪的记录和\color{purple}luogu之外

Code

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<' '<<x<<endl
#ifndef ONLINE_JUDGE
    #define fuck getchar
#else
    #define fuck nc
#endif
char nc(){
    static char buf[1<<25],*p=buf,*q=buf;
    if(p==q&&(q=(p=buf)+fread(buf,1,1<<25,stdin),p==q))return EOF;
    return *p++;
}
template<class T>void read(T&x){
    short f=1;x=0;
    char ch=fuck();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=fuck();
    }while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=fuck();
    }x*=f;
}
template<class T>void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+48);
}

#define maxn 300010
int n,m,q;
int rt[maxn];
struct{
    int lc,rc,sum;
}tree[maxn<<5];
int tot;
int ask(int k,int l,int r,int &x){
    if(!x)x=++tot,tree[x].sum=r-l+1;
//  cout<<k<<' '<<l<<' '<<r<<' '<<x<<endl;
    tree[x].sum--;
    if(l==r)return l;
    int mid=(l+r)>>1;
    int res;
    if(tree[x].lc)res=tree[tree[x].lc].sum;
    else res=mid-l+1;
    if(k<=res)return ask(k,l,mid,tree[x].lc);
    return ask(k-res,mid+1,r,tree[x].rc);
}
vector<long long>g[maxn];
long long num[maxn<<1];
int x,y;
int ans;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("P3960_5.in","r",stdin);
    freopen("Cindy.txt","w",stdout);
#endif
    read(n),read(m),read(q);
    for(int i=1;i<=n;i++)num[i]=(long long)i*m;
    for(int i=1;i<=q;i++){
        read(x),read(y);
        if(y==m)num[n+i]=num[ask(x,1,n+q,rt[0])];
        else{
            ans=ask(x,1,n+q,rt[0]),
            g[x].push_back(num[ans]);
            ans=ask(y,1,m+q,rt[x]);
            if(ans>=m)num[n+i]=g[x][ans-m];//因为y=m的情况已经排除，所以此处ans就是本行以外的了，所以要ans>=m 
            else num[n+i]=ans+m*(x-1ll);
        }write(num[n+i]),putchar('\n');
    }
}
无耻地开了O2