P8996 [CEOI 2022] Abracadabra 題解

知識點

線段樹，平衡樹，樹狀數組。

分析

首先，我們可以分析一下樣例。

分段

我們將第 \(0\) 次與第 \(1\) 次作比較，發現兩次都有幾段連續的數：

我們可以先憑最表面的分段，就會分成上面兩種，發現第 \(1\) 次就是第 \(0\) 次分段后按第一個數排序。

而每段又有什么規律呢？好像有兩段第一個數都是最大的，而另一段是 \(9\ 10\)，似乎不符合規律，但是我們又可以把上面的分成：

這下就符合規律了。

拆段

再考慮 \(1\) 次時到第 \(2\) 次，我們按照上面的方式來分段：

這好像就是把上面橫跨中間的分開就好了，但是我們換一個樣例看一下：

• \(0 \to 1\)：

  洗牌次數	自底向上的牌堆
  \(0\)	$9 \ 7\ 5\ 2\mid 10\mid 8 \ 4\ 3\ 6\ 1\ $
  \(1\)	\(9 \ 7\ 5\ 2\mid 8\ 4\ 3\ 6\ 1\mid 10\)

• \(1 \to 2\)：

  洗牌次數	自底向上的牌堆
  \(1\)	\(9 \ 7\ 5\ 2\mid 8\mid 4\mid 3\ 6\ 1\mid 10\)
  \(2\)	\(3\ 6\ 1\mid 4\mid 8\mid 9 \ 7\ 5\ 2\mid 10\)

除了分開橫跨中間的部分，我們還要把分開的后面那段給按照一開始分段的方法分開，這里我們可以處理出對于每個值下一個大于它的值是多少，然后一路處理過去，均攤次數是線性的。

那么我們就可以動態模擬維護了。

實現

考慮套數據結構進行動態維護。

平衡樹

最簡單的思想，把區間存在平衡樹中，用一些操作解決即可。

這里選用無旋 Treap，那么實現按值分裂、按大小分裂和分裂第一個節點即可。

線段樹 & 樹狀數組

由于對每段排序是按照每段第一個值大小升序排序，而且我們只要求按大小查值，所以我們可以用權值線段樹或樹狀數組代替，只需實現單點修改，線段樹二分或樹狀數組倍增以及前綴和查詢即可。

代碼

平衡樹

//#define Plus_Cat ""
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define Fi first
#define Se second
#define Pii pair<int,int>
#define uint unsigned int
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(2e5+10),Qr(1e6+10);
mt19937 rng(random_device {}());

namespace IOEcat {
    //Fast IO
} using namespace IOEcat;

bool flag;
int n,Q;
int a[N],len[N],nxt[N],pos[N],ans[Qr];
vector<Pii> vec[N];

struct Treap {
	int rt,tot;
	struct node {
		int key,cnt,siz,ls,rs;
		uint blc;
		node(int key=0,int cnt=0,int siz=0,int ls=0,int rs=0,uint blc=rng()):
			key(key),cnt(cnt),siz(siz),ls(ls),rs(rs),blc(blc) {}
	} tr[N];

	node &operator [](int i) { return tr[i]; }

	Treap():rt(0),tot(0) {}
#define ls(p) (tr[p].ls)
#define rs(p) (tr[p].rs)
	void Init() { tr[rt=tot=1]=node(); }

	int New(int key,int cnt) { return tr[++tot]=node(key,cnt,cnt),tot; }

	void Up(int p) { tr[p].siz=tr[ls(p)].siz+tr[p].cnt+tr[rs(p)].siz; }

	int &Merge(int &o,int p,int q) {
		if(!p||!q)return o=p|q;
		return (tr[p].blc<=tr[q].blc?Merge(rs(o=p),rs(p),q):Merge(ls(o=q),p,ls(q))),Up(o),o;
	}

	void Split_key(int &o,int &p,int key) { //[<=key] -> o,[>key] -> p
		if(!p)return o=0,void();
		if(key<tr[p].key)return Split_key(o,ls(p),key),Up(p);
		if(key==tr[p].key)return o=p,p=rs(p),rs(o)=0,Up(o);
		return o=p,Split_key(rs(o),p=rs(o),key),Up(o);
	}

	void Split_siz(int &o,int &p,int siz) { //[<=siz] -> o,[>siz] -> p
		if(!p)return o=0,void();
		if(tr[ls(p)].siz+tr[p].cnt<=siz)
			return o=p,Split_siz(rs(o),p=rs(o),siz-tr[ls(p)].siz-tr[p].cnt),Up(o);
		return Split_siz(o,ls(p),siz),Up(p);
	}

	void Split_begin(int &o,int &p) { //[begin] -> o,[otherwise] -> p
		if(!p)return o=0,void();
		if(ls(p))return Split_begin(o,ls(p)),Up(p);
		return o=p,p=rs(p),rs(o)=0,Up(o),void();
	}

	int Kth(int p,int k) {
		if(!p)return 0;
		if(ls(p)&&k<=tr[ls(p)].siz)return Kth(ls(p),k);
		if(k<=tr[ls(p)].siz+tr[p].cnt)return a[pos[tr[p].key]+k-tr[ls(p)].siz-1];
		return Kth(rs(p),k-tr[ls(p)].siz-tr[p].cnt);
	}

	void Print(int p,int fa=-1,int sign=-1) {
		if(!p)return;
		Print(ls(p),p,0);
		DE(p,fa,sign,tr[p].key);
		Print(rs(p),p,1);
	}
#undef ls
#undef rs
} trp;

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	/*DE("Input");*/
	I(n,Q);
	FOR(i,1,n)I(a[i]);
	/*DE("Offline");*/
	FOR(i,1,Q) {
		int t,x;
		I(t,x),t?vec[min(n,t)].push_back({x,i}),0:ans[i]=a[x];
	}
	/*DE("Init");*/
	//len
	auto Init_len=[&](int L,int R) {
		int it(L);
		FOR(i,L+1,R)if(a[i]>a[it])len[a[it]]=i-it,it=i;
		len[a[it]]=R-it+1;
	};
	Init_len(1,n>>1),Init_len((n>>1)+1,n);
	//Treap
	trp.Init();
	FOR(i,1,n)if(len[i])trp.Merge(trp.rt,trp.rt,trp.New(i,len[i]));
	//nxt
	set<int> st;
	DOR(i,n,1) {
		auto it(st.upper_bound(a[i]));
		nxt[a[i]]=(it==st.end()?n+1:*it),st.insert(a[i]);
		while(!st.empty()&&*st.begin()<a[i])st.erase(st.begin());
	}
	//pos
	FOR(i,1,n)pos[a[i]]=i;
	pos[n+1]=n+1;
	/*DE("Solve");*/
	FOR(i,1,n) {
		for(const Pii &p:vec[i])ans[p.Se]=trp.Kth(trp.rt,p.Fi);
		if(flag)continue;
		int l(0),mid(0),r(trp.rt);
		trp.Split_siz(l,r,n>>1);
		if(trp[l].siz==(n>>1)&&(trp.Merge(trp.rt,l,r),flag=true))continue;
		int pla(trp[trp.Split_begin(mid,r),mid].key);
		trp[mid].cnt=trp[mid].siz=(n>>1)-trp[l].siz;
		for(int p(a[pos[pla]+(n>>1)-trp[l].siz]); p<=n&&pos[p]<pos[pla]+len[pla]; p=nxt[p]) {
			len[p]=min(pos[pla]+len[pla],pos[nxt[p]])-pos[p];
			int L(0),R(l);
			trp.Split_key(L,R,p),trp.Merge(l,L,trp.Merge(R,trp.New(p,len[p]),R));
		}
		len[pla]=trp[mid].cnt,trp.Merge(trp.rt,l,trp.Merge(r,mid,r));
	}
	/*DE("Output");*/
	FOR(i,1,Q)O(ans[i],'\n');
	return 0;
}

線段樹

//#define Plus_Cat ""
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define Fi first
#define Se second
#define Pii pair<int,int>
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(2e5+10),Qr(1e6+10);

namespace IOEcat {
    //Fast IO
} using namespace IOEcat;

int n,Q;
int a[N],len[N],nxt[N],pos[N],ans[Qr];
vector<Pii> vec[N];

struct SEG {
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
	int tr[N<<2];

	void Up(int p) { tr[p]=tr[ls]+tr[rs]; }

	void Build(int p=1,int l=1,int r=n) {
		if(l==r)return tr[p]=len[l],void();
		Build(ls,l,mid),Build(rs,mid+1,r),Up(p);
	}

	void Change(int x,int d,int p=1,int l=1,int r=n) {
		if(l==r)return tr[p]=d,void();
		return (x<=mid?Change(x,d,ls,l,mid):Change(x,d,rs,mid+1,r)),Up(p);
	}

	int Binary(int k=(n>>1),int p=1,int l=1,int r=n) {
		if(l==r)return l;
		if(tr[rs]>=k)return Binary(k,rs,mid+1,r);
		return Binary(k-tr[rs],ls,l,mid);
	}

	int Sum(int L,int R,int p=1,int l=1,int r=n) {
		if(L<=l&&r<=R)return tr[p];
		if(R<=mid)return Sum(L,R,ls,l,mid);
		if(mid<L)return Sum(L,R,rs,mid+1,r);
		return Sum(L,R,ls,l,mid)+Sum(L,R,rs,mid+1,r);
	}
#undef ls
#undef rs
#undef mid
} seg;

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	/*DE("Input");*/
	I(n,Q);
	FOR(i,1,n)I(a[i]);
	FOR(i,1,Q) {
		int t,x;
		I(t,x),t?vec[min(n,t)].push_back({x,i}),0:ans[i]=a[x];
	}
	/*DE("Init");*/
	//pos
	FOR(i,1,n)pos[a[i]]=i;
	pos[n+1]=n+1;
	//left
	int it(1);
	FOR(i,2,n>>1)if(a[i]>a[it])len[a[it]]=i-it,it=i;
	len[a[it]]=(n>>1)-it+1;
	//right
	it=(n>>1)+1;
	FOR(i,(n>>1)+2,n)if(a[i]>a[it])len[a[it]]=i-it,it=i;
	len[a[it]]=n-it+1;
	//nxt
	set<int> st;
	DOR(i,n,1) {
		nxt[a[i]]=(st.upper_bound(a[i])==st.end()?n+1:*st.upper_bound(a[i])),st.insert(a[i]);
		while(!st.empty()&&*st.begin()<a[i])st.erase(st.begin());
	}
	//seg
	seg.Build();
	/*DE("Solve");*/
	FOR(i,1,n) {
		for(const Pii &p:vec[i]) {
			int x(p.Fi),pla(seg.Binary(n-x+1));
			if(pla>1)x-=seg.Sum(1,pla-1);
			ans[p.Se]=a[pos[pla]+x-1];
		}
		int pla(seg.Binary()),sum(pla>1?seg.Sum(1,pla-1):0);
		if(sum==(n>>1))continue;
		for(int p(a[pos[pla]+(n>>1)-sum]); p&&p<=n&&pos[p]<pos[pla]+len[pla]; p=nxt[p])
			seg.Change(p,len[p]=min(pos[pla]+len[pla],pos[nxt[p]])-pos[p]);
		seg.Change(pla,len[pla]=(n>>1)-sum);
	}
	/*DE("Output");*/
	FOR(i,1,Q)O(ans[i],'\n');
	return 0;
}

樹狀數組

//#define Plus_Cat ""
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define Fi first
#define Se second
#define Pii pair<int,int>
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(2e5+10),Qr(1e6+10);

namespace IOEcat {
    //Fast IO
} using namespace IOEcat;

bool flag;
int n,Q,L;
int a[N],len[N],nxt[N],pos[N],ans[Qr];
vector<Pii> vec[N];

struct BIT {
#define lowbit(i) ((i)&-(i))
	int c[N];

	void Build() {
		FOR(i,1,n) {
			c[i]+=len[i];
			if(i+lowbit(i)<=n)c[i+lowbit(i)]+=c[i];
		}
	}

	void Plus(int x,int d) { if(x>0)for(; x<=n; x+=lowbit(x))c[x]+=d; }

	int Sum(int x) {
		int ans(0);
		if(x>0)for(; x; x&=x-1)ans+=c[x];
		return ans;
	}

	int Binary(int k=(n>>1)+1) {
		int ans(0),sum(0);
		DOR(i,L,0)if((ans|1<<i)<=n&&sum+c[ans|1<<i]<k)sum+=c[ans|=1<<i];
		return ans+(sum<k);
	}
} bit;

namespace Sub {
	int Cmain() {
		/*DE("Init");*/
		//pos
		FOR(i,1,n)pos[a[i]]=i;
		pos[n+1]=n+1;
		//left
		int it(1);
		FOR(i,2,n>>1)if(a[i]>a[it])len[a[it]]=i-it,it=i;
		len[a[it]]=(n>>1)-it+1;
		//right
		it=(n>>1)+1;
		FOR(i,(n>>1)+2,n)if(a[i]>a[it])len[a[it]]=i-it,it=i;
		len[a[it]]=n-it+1;
		//nxt
		set<int> st;
		DOR(i,n,1) {
			nxt[a[i]]=(st.upper_bound(a[i])==st.end()?n+1:*st.upper_bound(a[i])),st.insert(a[i]);
			while(!st.empty()&&*st.begin()<a[i])st.erase(st.begin());
		}
		//bit
		bit.Build();
		/*DE("Solve");*/
		FOR(i,1,n) {
			for(const Pii &p:vec[i]) {
				int x(p.Fi),pla(bit.Binary(x));
				if(pla>1)x-=bit.Sum(pla-1);
				ans[p.Se]=a[pos[pla]+x-1];
			}
			if(flag)continue;
			int pla(bit.Binary()),sum(pla>1?bit.Sum(pla-1):0);
			if(sum==(n>>1)&&(flag==true))continue;
			for(int p(a[pos[pla]+(n>>1)-sum]); p&&p<=n&&pos[p]<pos[pla]+len[pla]; p=nxt[p])
				bit.Plus(p,len[p]=min(pos[pla]+len[pla],pos[nxt[p]])-pos[p]);
			int tmp(len[pla]);
			bit.Plus(pla,(len[pla]=(n>>1)-sum)-tmp);
		}
		/*DE("Output");*/
		FOR(i,1,Q)O(ans[i],'\n');
		return 0;
	}
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	I(n,Q),L=__lg(n);
	FOR(i,1,n)I(a[i]);
	FOR(i,1,Q) {
		int t,x;
		I(t,x),t?vec[min(n,t)].push_back({x,i}),0:ans[i]=a[x];
	}
	return Sub::Cmain();
}