#C240805B. 比赛

网址（Website）

题目详情 - 比赛 - Super

题解 - 比赛 - Super

题解（Solution）

发现每次重排编号时间复杂度极高，于是考虑当前编号在原序列中的位置，由于每次比赛都会使一段区间 $[l,r]$ 缩成一个点，因此当前比赛后面的点的编号都会减少 $r-l$ ，

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2012345;
struct P{int x,y;};

int n,m;

int L[N],R[N];
P a[N],d[N];

inline P max(P x,P y){return x.x!=y.x?(x.x>y.x?x:y):(x.y<y.y?x:y);}

#define lbt(x) (x&-x)
struct Like_Tree_Add{
	int c[N];
	void init(){For(i,1,n) c[i] = lbt(i);}
	void update(int x,int v){for(int i=x;i<=n;i+=lbt(i)) c[i] += v;}
	inline int ask(int k) {// 倍增查询 x 的位置
		int p=0;
		for(int i=19;~i;--i) if(p+(1<<i)<=n && k>c[p+(1<<i)]) k-=c[p+=1<<i];
		return p+1;
	}
}T1;
struct Like_Tree_Max{
	P c[N];
	void init(){For(i,1,n) c[i].x=-1;}
	void update(int x,P v){for(int i=x;i<=n;i+=lbt(i)) c[i] = max(c[i],v);}
	inline P ask(int x){P res={0,1};for(int i=x;i;i-=lbt(i)) res = max(res,c[i]);return res;}
}T2;

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	freopen("selection.in","r",stdin),
	freopen("selection.out","w",stdout);
	cin>>n>>m;int Tim = clock();
	T1.init();T2.init();
	For(i,1,n-1) a[i].y = rd();
	For(i,1,n) d[i].y = i, L[i] = i-1, R[i] = i+1;
	L[n+1] = n, R[0] = 1;
	while(m--){
		int opt = rd();
		if(opt==1){
			int l = rd(), r = rd()-l+1;// 转换为长度，因为链表不能用左右端点计算
			for(int p=l=T1.ask(l);p=R[p],--r;){// 先在树状数组上找到位置
				a[l].x = max(max(a[l].x,a[l].y),a[p].x);// 将这个点的信息合并到最左边的端点上
				a[l].y = a[p].y;// y 内记录的是当前缩的点的最后一个位置的值
				d[l] = max(d[l],d[p]);// 取两边最大的比赛轮数
				L[R[p]]=L[p],R[L[p]]=R[p];
				T1.update(p,-1);
			}d[l].x++;//记录这次比赛的贡献 
			T2.update(a[l].x,d[l]);
		}else cout<<T2.ask(rd()-1).y<<'\n';//要求严格大于 
	}return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}