[省选集训2022] 模拟赛9

货币

题目描述

\(n\) 个国家按照顺序排成一行，有 \(m\) 次事件，第 \(i\) 次事件代表国家 \((u,v)\) 的货币可以流通。

请选择一个连续区间 \([l,r]\)，使得按照顺序访问 \([l,r]\) 的国家之后可以搜集所有种类的货币。

\(1\leq n\leq 10^5,1\leq m\leq 2\cdot 10^5\)，强制在线。

解法

设 \(f_l\) 表示以 \(l\) 为左端点的最小右端点，那么可以很容易地用后继来描述，特别地，如果某个点是这种颜色的最后一个点，那么 \(nxt_i=+\infty\)，并且 \(nxt_0=\) 每种颜色第一个位置的最大值：

但是动态维护 \(f\) 十分麻烦，所以我们考虑切换贡献的主体，因为只有单调栈中的元素才可能有贡献，我们设 \(p_i\) 是单调栈的第 \(i\) 个节点，那么答案可以写成：

\(\min\{nxt_{p_{i-1}}-p_i+1\}\)

那么我们维护一个从前往后的极长上升子序列即可，把 \(nxt_0\) 传进我们的计算函数中，然后在每个 \(p_i\) 的位置计算贡献即可，对于修改可以启发式合并，那么只会有 \(O(n\log n)\) 次 \(nxt\) 的修改

时间复杂度 \(O(n\log^3n)\)，常数和代码量都十分优秀，实现的时候注意到处剪枝。

#include 
#include 
#include 
using namespace std;
const int M = 100005;
const int inf = 0x3f3f3f3f;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
void write(int x)
{
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
int n,m,k,ans,c[M],nxt[M],tr[M<<2],mx[M<<2];
set s[M];
int ask(int i,int l,int r,int c)
{
	if(l==r) return mx[i]>c?c-l+1:inf;
	int mid=(l+r)>>1;
	return mx[i<<1]>c?min(tr[i],ask(i<<1,l,mid,c))
	:ask(i<<1|1,mid+1,r,c); 
}
void upd(int i,int l,int r,int id)
{
	if(l==r) {mx[i]=nxt[id];return ;}
	int mid=(l+r)>>1;
	if(mid>=id) upd(i<<1,l,mid,id);
	else upd(i<<1|1,mid+1,r,id);
	mx[i]=max(mx[i<<1],mx[i<<1|1]);
	tr[i]=ask(i<<1|1,mid+1,r,mx[i<<1]);
}
signed main()
{
	freopen("currency.in","r",stdin);
	freopen("currency.out","w",stdout);
	n=read();m=read();k=read();
	for(int i=1;i<=n;i++)
	{
		s[0].insert(i),s[i].insert(i),c[i]=i;
		nxt[i]=inf;upd(1,1,n,i);
	}
	for(int i=1;i<=m;i++)
	{
		int u=(read()+k*ans-1)%n+1;
		int v=(read()+k*ans-1)%n+1;
		u=c[u];v=c[v];
		if(i==1) ans=n;
		if(u==v) {write(ans),puts("");continue;}
		if(s[u].size()