[BZOJ3489] A simple rmq problem

考虑当没有强制在线时，容易想到一个点 \(i\) 所影响的区间 \([l,r]\) 满足 \(pr_i<l\le i,i\le r<nx_i\)。显然可以转化为矩阵修改，单点求 \(\max\) 的问题。那扫描线 \(+\ set\) 轻松拿下。

强制在线就把线段树换成主席树就可以了。注意这里不能下传标记，所以得用标记永久化。

但是这里有一个小问题：你不能对主席树上每一个点都建立一个 \(set\)，否则时空双炸。考虑到一个节点 \(y\)，假如在后面的过程中出现了一个新的节点 \(x\)，它们两个覆盖的区间相同，那么 \(y\) 的 \(set\) 将不再会被修改，也不再会被用来更新其他的 \(set\)。所以我们可以让 \(x\) 继承 \(y\) 的 \(set\)，这样就是正确的了。至于 \(y\) 点对应的最大值，在计算中维护一下就行。

时间复杂度 \(O(n\log^2n+m\log n)\)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=8e6+5;
int n,m,a[N],rt[N*2],ls[M],rs[M],k,nm[M];
set<int>st[N*4];int pr[N],tot,las,nw[M];
struct que{int x,l,r,o;}g[N*2];int cnt;
inline int cmp(que x,que y){
	return x.x<y.x;
}inline int ass(int x){
	return !st[x].size()?0:(*st[x].rbegin());
}inline void chg(int &x,int y,int l,int r,int L,int R,int id){
	nm[x=++tot]=nm[y];
	if(L<=l&&r<=R){
		if(!nm[x]) nm[x]=++cnt; 
		ls[x]=ls[y],rs[x]=rs[y];
		if(id<0) st[nm[x]].erase(-id);
		else st[nm[x]].insert(id);
		return nw[x]=ass(nm[x]),void();
	}int mid=(l+r)/2;nw[x]=ass(nm[x]);
	if(L<=mid) chg(ls[x],ls[y],l,mid,L,R,id);
	if(R>mid) chg(rs[x],rs[y],mid+1,r,L,R,id);
	if(!ls[x]) ls[x]=ls[y];
	if(!rs[x]) rs[x]=rs[y];
}inline int ans(int x,int l,int r,int k){
	if(!x) return 0;
	if(l==r) return nw[x];
	int mid=(l+r)/2;
	if(k<=mid) return max(ans(ls[x],l,mid,k),nw[x]);
	return max(ans(rs[x],mid+1,r,k),nw[x]);
}int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1,x;i<=n;i++){
		cin>>x,pr[i]=a[x];
		if(!a[x]){a[x]=i;continue;}
		g[++k]={pr[a[x]]+1,a[x],i-1,x};
		g[++k]={a[x]+1,a[x],i-1,-x},a[x]=i;
	}for(int i=1;i<=n;i++){
		if(!a[i]) continue;
		g[++k]={pr[a[i]]+1,a[i],n,i};
		g[++k]={a[i]+1,a[i],n,-i};
	}sort(g+1,g+k+1,cmp),g[k+1].x=1e9;
	for(int i=1;i<=k;i++)
		chg(rt[i],rt[i-1],1,n,g[i].l,g[i].r,g[i].o);
	while(m--){
		int x,y,l,r;cin>>x>>y;
		l=min((x+las)%n,(y+las)%n)+1;
		r=max((x+las)%n,(y+las)%n)+1;
		int lc=1,rc=k+1,as=0;
		while(lc<=rc){
			int mid=(lc+rc)/2;
			if(g[mid].x>l)
				as=mid,rc=mid-1;
			else lc=mid+1;
		}las=ans(rt[as-1],1,n,r);
		cout<<las<<"\n";
	}return 0;
}