题解 P6887 【[CEOI2006]Queue】

· · 题解

题意

一开始将一列人按编号从1开始顺序排列，然后进行A次操作，每次将编号为A的人拿出，放在编号为 B 的人前面，所有操作进行完后有Q个问题，询问编号为X的人的位置，或者询问在X号位置上的人的编号。

2≤N≤50000,1≤A,B≤10^9 1≤Q≤50000,1≤X≤10^9

题解

定位：\rm ds简单题假装我没有调两天才调出来

首先我们不去考虑数据范围，假设\max{a_i,b_i}\le 1000000，那么该怎么做呢？

观察操作：拿出一个数，在插到另一个数前面，可以用双向链表轻松解决。

为x记录其前驱pre与后继nxt，那么要求删除可以看做把他的前驱与后继连起来，而插入就相当于在一个数和他的前驱之间加上一个数。十分简单，这里不过多赘述。

最后只要找到前驱为0的数再不断往后找就可以复原这个序列了。

然而CEOI没有这个部分分差评

再考虑上述算法为什么慢¿显然对于1\to 1000000000大部分数字的前驱与后继并没有改变，仍然是x-1与x+1，因此我们把所有的数分成两类：

  1. 前驱或后继更改过的
  2. 前驱与后继不变的

显然，第1类的个数不会超过3n。那么我们可以用\rm map来维护第1类值的前驱与后继，再把所有前驱或后继更改过的数字拿出来变成若干块。

显然，只有红框里的数前驱与后继发生了变化。我们需要一种东西来找到并记录红框。

如果我们用\rm map来维护每一个值的前驱与后继，那么对于每一个块的开始，其前驱必然不在\rm map中出现，我们可以利用这点性质找到每一个起始位置，并把每一段塞进\rm vector里。

然后对于剩下的数，其必然是递增的，且可以看做是[1,100000000]删去第1类数。

由于希望这些块按前后排序，我们对每个块记录整个块的前驱与后继，那么按前驱排序就把这些块前后排序了。

那么对于每个块，我们可以容易地维护他前面的数字总数。两个块之间的数字数为pre_i-nxt_{i-1}+1。那么对于块内的数，其位置与对相应位置的值也呼之欲出了。

接下来就是不在块内的数：

给位置求编号

我们记录所有块结束时的数字总数，那么肯定能找到第一个块，使得sum_i\le x，二分可以轻松解决。

那么x位置上的值，就是第 x-\text{再此之前的1类个数} 个第2类值。在此之前的1类个数可以前缀和维护。

给编号求位置

找到第一个块使得nxt_i\le x，二分一下就好了。

然后x的位置，就是x\text{在第二类中的编号}+\text{再此之前的1类个数}。维护方式类似。

于是最后只剩下一个问题：第2类数最多有1000000000个，如何给数字求编号或给编号求数字。事实上，动态开点线段树可以解决。每个节点记录一个已经删去了多少个，再乱搞一下就好了。

代码

边界需要注意一下，其他也没什么了。

#include<bits/stdc++.h>
namespace in{
    char buf[1<<21],*p1=buf,*p2=buf;
    inline int getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    template <typename T>inline void read(T& t){
        t=0;int f=0;char ch=getc();while (!isdigit(ch)){if(ch=='-')f = 1;ch=getc();}
        while(isdigit(ch)){t=t*10+ch-48;ch = getc();}if(f)t=-t;
    }
    template <typename T,typename... Args> inline void read(T& t, Args&... args){read(t);read(args...);}
}
namespace out{
    char buffer[1<<21];int p1=-1;const int p2 = (1<<21)-1;
    inline void flush(){fwrite(buffer,1,p1+1,stdout),p1=-1;}
    inline void putc(const char &x) {if(p1==p2)flush();buffer[++p1]=x;}
    template <typename T>void write(T x) {
        static char buf[15];static int len=-1;if(x>=0){do{buf[++len]=x%10+48,x/=10;}while (x);}else{putc('-');do {buf[++len]=-(x%10)+48,x/=10;}while(x);}
        while (len>=0)putc(buf[len]),--len;
    }
}
using namespace std;
int n,q;
//双向链表部分
struct node{
    int pre,nxt;//记录前驱与后继 
    node(){pre=nxt=0;}
    node(int _pre,int _nxt){pre=_pre,nxt=_nxt;};
}; 
map<int,node>List;
bool has(int x){
    return List.find(x)!=List.end();
}
void chk(int x){
    if(!has(x))
        List[x]=node(x-1,x+1);
}
void connect(int x,int y){
    List[x].nxt=y;
    List[y].pre=x;
}
//维护块
vector<int>num[100000+10];
int cnt=0;
struct node2{
    int pre,nxt,id,sum,lensum;
    node2(){id=cnt++;}
    bool operator<(const node2 b)const{
        return pre<b.pre;
    }
};
vector<node2>block;
//维护块内有关信息
map<int,int>wei;//wei[x] 记录x的位置
map<int,int>val;//val[x] 记录x上的值
//动态开点线段树查询
struct t{
    int lc,rc;
    int sz;
}T[100000*32];
int root,tot;
#define mid (l+r>>1)
void upd(int &x,int l,int r,int pos){
    //把pos改为0
    if(!x)x=++tot,T[x].sz=0;
    if(l==r){T[x].sz=1;return;}
    if(pos<=mid)upd(T[x].lc,l,mid,pos);
    else upd(T[x].rc,mid+1,r,pos);
    T[x].sz=T[T[x].lc].sz+T[T[x].rc].sz;
    //printf("%d [%d,%d] %d\n",x,l,r,t[x].sz); 
}
int qry1(int x,int l,int r,int pos){
    //printf("%d %d %d   sz:%d\n",x,l,r,T[x].sz);
    //查询在小于等于pos的和
    if(!x)return pos-l+1;
    if(l==r)return 1-T[x].sz;
    if(pos<=mid)return qry1(T[x].lc,l,mid,pos);
    return (mid-l+1-T[T[x].lc].sz)+qry1(T[x].rc,mid+1,r,pos);
}
int qry2(int x,int l,int r,int pos){
    //查询第 pos 个未被删除的值
    if(!x){
        //说明l-r都未被删除
        return l+pos-1; 
    }
    int hasl=mid-l+1-T[T[x].lc].sz;
    if(hasl>=pos)return qry2(T[x].lc,l,mid,pos);
    else return qry2(T[x].rc,mid+1,r,pos-hasl);
}
signed main(){
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    in::read(n);
    for(int i=1,a,b;i<=n;i++){
        in::read(a,b);
        chk(a);chk(List[a].pre);chk(List[a].nxt);
        chk(b);chk(List[b].pre);
        connect(List[a].pre,List[a].nxt);
        connect(List[b].pre,a);
        connect(a,b);
    }
    List.erase(0);
    for(auto k:List){
        //printf("%d<- %d ->%d\n",k.second.pre,k.first,k.second.nxt); 
        if(!has(k.second.pre)){
            block.push_back(node2());
            block.back().pre=k.second.pre;
            int now=k.first;
            while(has(now)){
                num[block.back().id].push_back(now);
                now=List[now].nxt;
            }
            block.back().nxt=now;
        }
    }
    block.push_back(node2());
    block.back().pre=-1000;
    block.back().sum=0;
    block.back().lensum=0;

    sort(block.begin(),block.end());
    //for(auto k:block){
    //  printf("%d %d\n",k.pre,k.nxt);
    //  for(auto nn:num[k.id])
    //      printf("%d ",nn);
    //  printf("\n");
    //}

    int lst=1,sum=0,lensum=0;//记录上一个块的后继 ，已经一共有的数
    for(auto &k:block){
        if(k.pre<0)continue;
        sum+=k.pre-lst+1;
        lst=k.nxt;
        for(auto nn:num[k.id])
            sum++,wei[nn]=sum,val[sum]=nn,
            upd(root,1,1000000000,nn);
        k.sum=sum;
        k.lensum=lensum+num[k.id].size();
        lensum=k.lensum;
    } 
    //for(auto k:wei)
    //  printf("%d在%d\n",k.first,k.second);
    in::read(q);
    while(q--){
        char op=in::getc();int x;
        while(!isalpha(op))op=in::getc();
        in::read(x);
        if(op=='P'){
            if(wei[x])
                out::write(wei[x]);
            else{
                int l=0,r=block.size()-1;
                int ans=0;
                while(l<=r){
                    if(block[mid].nxt<=x)
                        ans=mid,l=mid+1;
                    else r=mid-1;
                }
                out::write(block[ans].lensum+qry1(root,1,1000000000,x));
            }
        }else{
            if(val[x])
                out::write(val[x]);
            else{
                int l=0,r=block.size()-1;
                int ans; 
                while(l<=r){
                    if(block[mid].sum<=x)
                        ans=mid,l=mid+1;
                    else r=mid-1;
                }
                out::write(qry2(root,1,1000000000,x-block[ans].lensum));
            }
        }
        out::putc('\n');

    }
    out::flush();
    return 0;
}