自动搬运

查看原文

来自洛谷，原作者为

	jun头吉吉 alive

搬运于2025-08-24 22:24:57，当前版本为作者最后更新于2020-11-12 19:31:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

一开始将一列人按编号从$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;
}