2022.8 模拟赛 Solution Set()

8.4

三个紫题的模拟赛,我得到了 0 昏的好成绩。我破防了!

COCI Svjetlo

思路比较清奇,像我还是很难想到按端点的个数做 DP 的。

定义 \(dp_{u,0/1/2,0/1}\) 表示,\(u\) 的子树内除 \(u\) 全部点亮,\(u\) 子树内存在路径的 \(0/1/2\) 个端点,\(u\) 是否被点亮。

转移比较愚蠢,相当于对端点个数这一位做背包,代价可以到时候讨论一下,不是很难。考场上我想出来了会不会去写也很难说啊。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
char s[500005];
vector<LL> V[500005];
bool del[500005];
LL a[500005];
void idfs(LL u,LL f)
{
	del[u]=(s[u]=='1');
	for(auto v:V[u])
	{
		if(v==f)	continue;
		idfs(v,u);
		del[u]&=del[v];
	}
}
LL dp[500005][3][2];
void dfs(LL u,LL fa)
{
	for(auto v:V[u])	if(v!=fa && !del[v])	dfs(v,u);
	LL *F=dp[u][0],*G=dp[u][1],*H=dp[u][2];
	F[a[u]]=0;
	for(auto v:V[u])
	{
		if(v==fa || del[v])	continue;
		LL *f=dp[v][0],*g=dp[v][1],*h=dp[v][2];
		LL f0=F[0],f1=F[1],g0=G[0],g1=G[1],h0=H[0],h1=H[1];
		F[0]=min(f1+f[0]+2,f0+f[1]+4),F[1]=min(f0+f[0]+2,f1+f[1]+4);
		G[0]=min({g1+f[0]+2,g0+f[1]+4,f0+g[0]+3,f1+g[1]+1});
		G[1]=min({g0+f[0]+2,g1+f[1]+4,f1+g[0]+3,f0+g[1]+1});
		H[0]=min({f0+h[1]+4,f1+h[0]+2,g0+g[1],g1+g[0]+2,h0+f[1]+4,h1+f[0]+2});
		H[1]=min({f0+h[0]+2,f1+h[1]+4,g0+g[0]+2,g1+g[1],h0+f[0]+2,h1+f[1]+4});
	}
	G[0]=min(G[0],F[1]+1),G[1]=min(G[1],F[0]+1);
	H[0]=min(G[0],H[0]),H[1]=min(G[1],H[1]);
}
int main(){
	scanf("%lld",&n);
	scanf("%s",s+1);
	for(LL i=1,u,v;i<n;++i)	scanf("%lld %lld",&u,&v),V[u].push_back(v),V[v].push_back(u);
	LL rt=0;
	for(LL i=1;i<=n;++i)	if(s[i]=='0')	rt=i;
	for(LL i=1;i<=n;++i)	a[i]=s[i]^'0';
	idfs(rt,0);
	memset(dp,63,sizeof dp);
	dfs(rt,0);
	printf("%lld",dp[rt][2][1]),puts("");
	return 0;
}

COCI 3D Histogram

相当于问最大的区间权值。一个区间 \([l,r]\) 的权值为 \((r-l+1)\min\{a_{l\cdots r}\}\min\{b_{l\cdots r}\}\)。

考虑分治区间 \([l,r]\) 中点为 \(c\),然后枚举左端点 \(L\),双指针确定右端点 \(p,q\) 满足 \(\min\{a_{i\cdots c}\} > \min\{a_{c+1\cdots p}\}\),\(\min\{b_{i\cdots c}\} > \min\{b_{c+1\cdots q}\}\)。然后对于每一个左端点算答案。边界比较显然。

分情况讨论右端点 \(R\) 的位置。先假设 \(p<q\),\(q>p\) 的情况可以类似处理:

  • \(R \leq p\):这个时候只跟左边有关,贡献很显然;
  • \(p < R \leq q\):这个时候贡献类似于 \(\min\{b_{i\cdots c}\} \cdot (R-L+1) \min\{a_{c+1\cdots p}\}\),前面只跟前半部分有关的部分先遮住不看,后面的部分写成 \((R+1)\min\{a_{c+1\cdots p}\} - L\min\{a_{c+1\cdots p}\}\),这个部分前半只跟 \(R\) 有关,后半部分自变量为 \(L\),可以看成一个函数的形式:\(y_R = -Lk_R + b_R\)(或者点的形式),现在要找最优的 \(R\)。结论是维护凸包,然后找到与直线相切的点就好。
  • \(q < R \leq r\):和上面类似的。

这样的话我们要在一个区间内找到最优的点。暴力的想法是线段树套李超树,其实不需要,因为每次查询的斜率是单增的,我们只要从凸包后面删除即可。这样可以做到 \(O(n \log^2 n)\)。

#include<bits/stdc++.h>
using namespace std;
typedef __int128 LL;
char buf[1<<18],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
LL read()
{
	LL x=0;
	char c=getchar();
	while(c<'0' || c>'9')	c=getchar();
	while(c>='0' && c<='9')	x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x;
}
void write(LL x)
{
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
struct Point{
	LL x,y;
	Point(LL X=0,LL Y=0){x=X,y=Y;}
	Point operator + (Point ano) const {return Point(x+ano.x,y+ano.y);}
	Point operator - (Point ano) const {return Point(x-ano.x,y-ano.y);}
	LL operator * (Point ano) const {return x*ano.y-y*ano.x;}
};
LL n,ans;
LL a[200005],b[200005];
LL pa[200005],pb[200005];
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define Mm LL mid=(l+r)>>1
vector<Point> tr[800005][3];
#define len(x) (LL(x.size()))
void push(LL id,LL op,Point p)
{
	while(len(tr[id][op])>=2)
	{
		LL N=len(tr[id][op]);
		if((tr[id][op][N-1]-tr[id][op][N-2])*(p-tr[id][op][N-1])<0)	break;
		tr[id][op].pop_back();
	}
	tr[id][op].push_back(p);
}
LL query(LL id,LL op,LL k)
{
	Point slope=Point(1,k);
	while(len(tr[id][op])>=2)
	{
		LL N=len(tr[id][op]);
		if((tr[id][op][N-1]-tr[id][op][N-2])*slope<0)	break;
		tr[id][op].pop_back();
	}
	return tr[id][op].back().y-tr[id][op].back().x*k;
}
void build(LL l,LL r,LL now)
{
	tr[now][0].clear(),tr[now][1].clear(),tr[now][2].clear();
	for(LL i=r;i>=l;--i)
	{
		push(now,0,Point(pa[i],pa[i]*(i+1)));
		push(now,1,Point(pb[i],pb[i]*(i+1)));
		push(now,2,Point(pa[i]*pb[i],pa[i]*pb[i]*(i+1)));
	}
	if(l==r)	return ;
	Mm;
	build(l,mid,lc(now)),build(mid+1,r,rc(now));
}
LL query(LL l,LL r,LL now,LL x,LL y,LL op,LL k)
{
	if(x<=l && r<=y)	return query(now,op,k);
	Mm,ret=0;
	if(x<=mid)	ret=max(ret,query(l,mid,lc(now),x,y,op,k));
	if(mid<y)	ret=max(ret,query(mid+1,r,rc(now),x,y,op,k));
	return ret;
}
void Solve(LL L,LL R)
{
	if(L==R)
	{
		ans=max(ans,a[L]*b[L]);
		return ;
	}
	LL mid=(L+R)>>1;
	Solve(L,mid),Solve(mid+1,R);
	pa[mid]=a[mid],pa[mid+1]=a[mid+1],pb[mid]=b[mid],pb[mid+1]=b[mid+1];
	for(LL i=mid-1;i>=L;--i)	pa[i]=min(pa[i+1],a[i]),pb[i]=min(pb[i+1],b[i]);
	for(LL i=mid+2;i<=R;++i)	pa[i]=min(pa[i-1],a[i]),pb[i]=min(pb[i-1],b[i]);
	build(mid+1,R,1);
	LL p=R+1,q=R+1;
	for(LL i=L;i<=mid;++i)
	{
		while(p-1>=mid+1 && pa[i]>pa[p-1])	--p;
		while(q-1>=mid+1 && pb[i]>pb[q-1])	--q;
		if(p>mid+1 && q>mid+1)	ans=max(ans,(min(p,q)-i)*pa[i]*pb[i]);
		if(p<q)	ans=max(ans,pb[i]*query(mid+1,R,1,p,q-1,0,i));
		if(q<p)	ans=max(ans,pa[i]*query(mid+1,R,1,q,p-1,1,i));
		if(p<=R && q<=R)	ans=max(ans,query(mid+1,R,1,max(p,q),R,2,i));
	}
}
int main(){
	n=read();
	for(LL i=1;i<=n;++i)	a[i]=read(),b[i]=read();
	Solve(1,n);
	write(ans);
	return 0;
}

COCI Specijacija

更是一个没啥技术含量的题目。

如果两个点没有祖孙关系,那么最近公共祖先一定是给出的 \(n\) 个分叉点里。你可以把直链(没有分叉的)看成一个点,这样的话就只有 \(O(n)\) 个点。

模拟这个操作,可以用线段树删除结点,更改一个点对应的标号。注意到我们要查询一个点在某一层的哪个位置,因此我们要用主席树。

代码比讲得清楚。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
char buf[1<<18],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
LL read()
{
	LL x=0;
	char c=getchar();
	while(c<'0' || c>'9')	c=getchar();
	while(c>='0' && c<='9')	x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x;
}
void write(LL x)
{
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
vector<LL> G[400005];
LL fa[20][400005],N,dep[400005],id[400005];
LL lgs[400005];
LL LCA(LL u,LL v)
{
	if(dep[u]>dep[v])	swap(u,v);
	while(dep[u]<dep[v])	v=fa[lgs[dep[v]-dep[u]]][v];
	if(u==v)	return u;
	for(LL i=19;~i;--i)	if(fa[i][u]^fa[i][v])	u=fa[i][u],v=fa[i][v];
	return fa[0][u];
}
LL n,q;
LL a[200005],siz[200005];
#define Mm LL mid=(l+r)>>1
LL cnt,rt[200005];
LL lc[8000005],rc[8000005],sum[8000005],tid[8000005];
inline void push_up(LL now){sum[now]=sum[lc[now]]+sum[rc[now]];}
void build(LL l,LL r,LL &now)
{
	now=++cnt;
	if(l==r)
	{
		tid[now]=++N;
		sum[now]=1;
		return ;
	}
	Mm;
	build(l,mid,lc[now]),build(mid+1,r,rc[now]);
	push_up(now);
}
void modify(LL &now,LL lst,LL l,LL r,LL p)
{
	now=++cnt;
	sum[now]=sum[lst],lc[now]=lc[lst],rc[now]=rc[lst];
	if(l==r)
	{
		sum[now]=0;
		return ;
	}
	Mm;
	if(p<=sum[lc[now]])	modify(lc[now],lc[lst],l,mid,p);
	else	modify(rc[now],rc[lst],mid+1,r,p-sum[lc[now]]);
	push_up(now);
}
void modifyId(LL &now,LL lst,LL l,LL r,LL p,LL w)
{
	now=++cnt;
	sum[now]=sum[lst],lc[now]=lc[lst],rc[now]=rc[lst],tid[now]=tid[lst];
	if(l==r)
	{
		tid[now]=w;
		return ;
	}
	Mm;
	if(p<=sum[lc[now]])	modifyId(lc[now],lc[lst],l,mid,p,w);
	else	modifyId(rc[now],rc[lst],mid+1,r,p-sum[lc[now]],w);
	push_up(now);
}
LL query(LL now,LL l,LL r,LL p)
{
	if(l==r)	return tid[now];
	Mm;
	if(p<=sum[lc[now]])	return query(lc[now],l,mid,p);
	return query(rc[now],mid+1,r,p-sum[lc[now]]);
}
void dfs(LL u,LL f)
{
	fa[0][u]=f;
	dep[u]=dep[f]+1;
	for(auto v:G[u])	dfs(v,u);
}
int main(){
	n=read(),q=read();
	LL T=read();
	for(LL i=1;i<=n;++i)	a[i]=read();
	for(LL i=1;i<=n;++i)	siz[i]=i*(i+1)/2;
	for(LL i=1;i<=n+1;++i)	id[i]=n*(n+1)/2+i;
	build(1,n+1,rt[n+1]);
	for(LL i=n;i;--i)
	{
		LL p=a[i]-siz[i-1];
		id[++N]=a[i];
		rt[i]=rt[i+1];
		modify(rt[i],rt[i],1,n+1,p+1);
		modifyId(rt[i],rt[i],1,n+1,p,N);
		LL u=query(rt[i+1],1,n+1,p),
		v=query(rt[i+1],1,n+1,p+1);
		G[N].push_back(u),G[N].push_back(v);
	}
	dfs(N,0);
	for(LL i=2;i<=N;++i)	lgs[i]=lgs[i>>1]+1;
	for(LL i=1;i<=19;++i)	for(LL j=1;j<=N;++j)	fa[i][j]=fa[i-1][fa[i-1][j]];
	LL lst=0;
	LL mod=(n+1)*(n+2)/2;
	while(q-->0)
	{
		LL u=read(),v=read();
		u=(u-1+lst*T)%mod+1,v=(v-1+lst*T)%mod+1;
		LL du=lower_bound(siz,siz+1+n,u)-siz,dv=lower_bound(siz,siz+1+n,v)-siz;
		LL pu=query(rt[du],1,n+1,u-siz[du-1]),pv=query(rt[dv],1,n+1,v-siz[dv-1]);
		LL lca=LCA(pu,pv);
		write(lst=min({u,v,id[lca]})),puts("");
	}
	return 0;
}
————————

8.4

三个紫题的模拟赛,我得到了 0 昏的好成绩。我破防了!

COCI Svjetlo

思路比较清奇,像我还是很难想到按端点的个数做 DP 的。

定义 \(dp_{u,0/1/2,0/1}\) 表示,\(u\) 的子树内除 \(u\) 全部点亮,\(u\) 子树内存在路径的 \(0/1/2\) 个端点,\(u\) 是否被点亮。

转移比较愚蠢,相当于对端点个数这一位做背包,代价可以到时候讨论一下,不是很难。考场上我想出来了会不会去写也很难说啊。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
char s[500005];
vector<LL> V[500005];
bool del[500005];
LL a[500005];
void idfs(LL u,LL f)
{
	del[u]=(s[u]=='1');
	for(auto v:V[u])
	{
		if(v==f)	continue;
		idfs(v,u);
		del[u]&=del[v];
	}
}
LL dp[500005][3][2];
void dfs(LL u,LL fa)
{
	for(auto v:V[u])	if(v!=fa && !del[v])	dfs(v,u);
	LL *F=dp[u][0],*G=dp[u][1],*H=dp[u][2];
	F[a[u]]=0;
	for(auto v:V[u])
	{
		if(v==fa || del[v])	continue;
		LL *f=dp[v][0],*g=dp[v][1],*h=dp[v][2];
		LL f0=F[0],f1=F[1],g0=G[0],g1=G[1],h0=H[0],h1=H[1];
		F[0]=min(f1+f[0]+2,f0+f[1]+4),F[1]=min(f0+f[0]+2,f1+f[1]+4);
		G[0]=min({g1+f[0]+2,g0+f[1]+4,f0+g[0]+3,f1+g[1]+1});
		G[1]=min({g0+f[0]+2,g1+f[1]+4,f1+g[0]+3,f0+g[1]+1});
		H[0]=min({f0+h[1]+4,f1+h[0]+2,g0+g[1],g1+g[0]+2,h0+f[1]+4,h1+f[0]+2});
		H[1]=min({f0+h[0]+2,f1+h[1]+4,g0+g[0]+2,g1+g[1],h0+f[0]+2,h1+f[1]+4});
	}
	G[0]=min(G[0],F[1]+1),G[1]=min(G[1],F[0]+1);
	H[0]=min(G[0],H[0]),H[1]=min(G[1],H[1]);
}
int main(){
	scanf("%lld",&n);
	scanf("%s",s+1);
	for(LL i=1,u,v;i<n;++i)	scanf("%lld %lld",&u,&v),V[u].push_back(v),V[v].push_back(u);
	LL rt=0;
	for(LL i=1;i<=n;++i)	if(s[i]=='0')	rt=i;
	for(LL i=1;i<=n;++i)	a[i]=s[i]^'0';
	idfs(rt,0);
	memset(dp,63,sizeof dp);
	dfs(rt,0);
	printf("%lld",dp[rt][2][1]),puts("");
	return 0;
}

COCI 3D Histogram

相当于问最大的区间权值。一个区间 \([l,r]\) 的权值为 \((r-l+1)\min\{a_{l\cdots r}\}\min\{b_{l\cdots r}\}\)。

考虑分治区间 \([l,r]\) 中点为 \(c\),然后枚举左端点 \(L\),双指针确定右端点 \(p,q\) 满足 \(\min\{a_{i\cdots c}\} > \min\{a_{c+1\cdots p}\}\),\(\min\{b_{i\cdots c}\} > \min\{b_{c+1\cdots q}\}\)。然后对于每一个左端点算答案。边界比较显然。

分情况讨论右端点 \(R\) 的位置。先假设 \(p<q\),\(q>p\) 的情况可以类似处理:

  • \(R \leq p\):这个时候只跟左边有关,贡献很显然;
  • \(p < R \leq q\):这个时候贡献类似于 \(\min\{b_{i\cdots c}\} \cdot (R-L+1) \min\{a_{c+1\cdots p}\}\),前面只跟前半部分有关的部分先遮住不看,后面的部分写成 \((R+1)\min\{a_{c+1\cdots p}\} - L\min\{a_{c+1\cdots p}\}\),这个部分前半只跟 \(R\) 有关,后半部分自变量为 \(L\),可以看成一个函数的形式:\(y_R = -Lk_R + b_R\)(或者点的形式),现在要找最优的 \(R\)。结论是维护凸包,然后找到与直线相切的点就好。
  • \(q < R \leq r\):和上面类似的。

这样的话我们要在一个区间内找到最优的点。暴力的想法是线段树套李超树,其实不需要,因为每次查询的斜率是单增的,我们只要从凸包后面删除即可。这样可以做到 \(O(n \log^2 n)\)。

#include<bits/stdc++.h>
using namespace std;
typedef __int128 LL;
char buf[1<<18],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
LL read()
{
	LL x=0;
	char c=getchar();
	while(c<'0' || c>'9')	c=getchar();
	while(c>='0' && c<='9')	x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x;
}
void write(LL x)
{
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
struct Point{
	LL x,y;
	Point(LL X=0,LL Y=0){x=X,y=Y;}
	Point operator + (Point ano) const {return Point(x+ano.x,y+ano.y);}
	Point operator - (Point ano) const {return Point(x-ano.x,y-ano.y);}
	LL operator * (Point ano) const {return x*ano.y-y*ano.x;}
};
LL n,ans;
LL a[200005],b[200005];
LL pa[200005],pb[200005];
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define Mm LL mid=(l+r)>>1
vector<Point> tr[800005][3];
#define len(x) (LL(x.size()))
void push(LL id,LL op,Point p)
{
	while(len(tr[id][op])>=2)
	{
		LL N=len(tr[id][op]);
		if((tr[id][op][N-1]-tr[id][op][N-2])*(p-tr[id][op][N-1])<0)	break;
		tr[id][op].pop_back();
	}
	tr[id][op].push_back(p);
}
LL query(LL id,LL op,LL k)
{
	Point slope=Point(1,k);
	while(len(tr[id][op])>=2)
	{
		LL N=len(tr[id][op]);
		if((tr[id][op][N-1]-tr[id][op][N-2])*slope<0)	break;
		tr[id][op].pop_back();
	}
	return tr[id][op].back().y-tr[id][op].back().x*k;
}
void build(LL l,LL r,LL now)
{
	tr[now][0].clear(),tr[now][1].clear(),tr[now][2].clear();
	for(LL i=r;i>=l;--i)
	{
		push(now,0,Point(pa[i],pa[i]*(i+1)));
		push(now,1,Point(pb[i],pb[i]*(i+1)));
		push(now,2,Point(pa[i]*pb[i],pa[i]*pb[i]*(i+1)));
	}
	if(l==r)	return ;
	Mm;
	build(l,mid,lc(now)),build(mid+1,r,rc(now));
}
LL query(LL l,LL r,LL now,LL x,LL y,LL op,LL k)
{
	if(x<=l && r<=y)	return query(now,op,k);
	Mm,ret=0;
	if(x<=mid)	ret=max(ret,query(l,mid,lc(now),x,y,op,k));
	if(mid<y)	ret=max(ret,query(mid+1,r,rc(now),x,y,op,k));
	return ret;
}
void Solve(LL L,LL R)
{
	if(L==R)
	{
		ans=max(ans,a[L]*b[L]);
		return ;
	}
	LL mid=(L+R)>>1;
	Solve(L,mid),Solve(mid+1,R);
	pa[mid]=a[mid],pa[mid+1]=a[mid+1],pb[mid]=b[mid],pb[mid+1]=b[mid+1];
	for(LL i=mid-1;i>=L;--i)	pa[i]=min(pa[i+1],a[i]),pb[i]=min(pb[i+1],b[i]);
	for(LL i=mid+2;i<=R;++i)	pa[i]=min(pa[i-1],a[i]),pb[i]=min(pb[i-1],b[i]);
	build(mid+1,R,1);
	LL p=R+1,q=R+1;
	for(LL i=L;i<=mid;++i)
	{
		while(p-1>=mid+1 && pa[i]>pa[p-1])	--p;
		while(q-1>=mid+1 && pb[i]>pb[q-1])	--q;
		if(p>mid+1 && q>mid+1)	ans=max(ans,(min(p,q)-i)*pa[i]*pb[i]);
		if(p<q)	ans=max(ans,pb[i]*query(mid+1,R,1,p,q-1,0,i));
		if(q<p)	ans=max(ans,pa[i]*query(mid+1,R,1,q,p-1,1,i));
		if(p<=R && q<=R)	ans=max(ans,query(mid+1,R,1,max(p,q),R,2,i));
	}
}
int main(){
	n=read();
	for(LL i=1;i<=n;++i)	a[i]=read(),b[i]=read();
	Solve(1,n);
	write(ans);
	return 0;
}

COCI Specijacija

更是一个没啥技术含量的题目。

如果两个点没有祖孙关系,那么最近公共祖先一定是给出的 \(n\) 个分叉点里。你可以把直链(没有分叉的)看成一个点,这样的话就只有 \(O(n)\) 个点。

模拟这个操作,可以用线段树删除结点,更改一个点对应的标号。注意到我们要查询一个点在某一层的哪个位置,因此我们要用主席树。

代码比讲得清楚。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
char buf[1<<18],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
LL read()
{
	LL x=0;
	char c=getchar();
	while(c<'0' || c>'9')	c=getchar();
	while(c>='0' && c<='9')	x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x;
}
void write(LL x)
{
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
vector<LL> G[400005];
LL fa[20][400005],N,dep[400005],id[400005];
LL lgs[400005];
LL LCA(LL u,LL v)
{
	if(dep[u]>dep[v])	swap(u,v);
	while(dep[u]<dep[v])	v=fa[lgs[dep[v]-dep[u]]][v];
	if(u==v)	return u;
	for(LL i=19;~i;--i)	if(fa[i][u]^fa[i][v])	u=fa[i][u],v=fa[i][v];
	return fa[0][u];
}
LL n,q;
LL a[200005],siz[200005];
#define Mm LL mid=(l+r)>>1
LL cnt,rt[200005];
LL lc[8000005],rc[8000005],sum[8000005],tid[8000005];
inline void push_up(LL now){sum[now]=sum[lc[now]]+sum[rc[now]];}
void build(LL l,LL r,LL &now)
{
	now=++cnt;
	if(l==r)
	{
		tid[now]=++N;
		sum[now]=1;
		return ;
	}
	Mm;
	build(l,mid,lc[now]),build(mid+1,r,rc[now]);
	push_up(now);
}
void modify(LL &now,LL lst,LL l,LL r,LL p)
{
	now=++cnt;
	sum[now]=sum[lst],lc[now]=lc[lst],rc[now]=rc[lst];
	if(l==r)
	{
		sum[now]=0;
		return ;
	}
	Mm;
	if(p<=sum[lc[now]])	modify(lc[now],lc[lst],l,mid,p);
	else	modify(rc[now],rc[lst],mid+1,r,p-sum[lc[now]]);
	push_up(now);
}
void modifyId(LL &now,LL lst,LL l,LL r,LL p,LL w)
{
	now=++cnt;
	sum[now]=sum[lst],lc[now]=lc[lst],rc[now]=rc[lst],tid[now]=tid[lst];
	if(l==r)
	{
		tid[now]=w;
		return ;
	}
	Mm;
	if(p<=sum[lc[now]])	modifyId(lc[now],lc[lst],l,mid,p,w);
	else	modifyId(rc[now],rc[lst],mid+1,r,p-sum[lc[now]],w);
	push_up(now);
}
LL query(LL now,LL l,LL r,LL p)
{
	if(l==r)	return tid[now];
	Mm;
	if(p<=sum[lc[now]])	return query(lc[now],l,mid,p);
	return query(rc[now],mid+1,r,p-sum[lc[now]]);
}
void dfs(LL u,LL f)
{
	fa[0][u]=f;
	dep[u]=dep[f]+1;
	for(auto v:G[u])	dfs(v,u);
}
int main(){
	n=read(),q=read();
	LL T=read();
	for(LL i=1;i<=n;++i)	a[i]=read();
	for(LL i=1;i<=n;++i)	siz[i]=i*(i+1)/2;
	for(LL i=1;i<=n+1;++i)	id[i]=n*(n+1)/2+i;
	build(1,n+1,rt[n+1]);
	for(LL i=n;i;--i)
	{
		LL p=a[i]-siz[i-1];
		id[++N]=a[i];
		rt[i]=rt[i+1];
		modify(rt[i],rt[i],1,n+1,p+1);
		modifyId(rt[i],rt[i],1,n+1,p,N);
		LL u=query(rt[i+1],1,n+1,p),
		v=query(rt[i+1],1,n+1,p+1);
		G[N].push_back(u),G[N].push_back(v);
	}
	dfs(N,0);
	for(LL i=2;i<=N;++i)	lgs[i]=lgs[i>>1]+1;
	for(LL i=1;i<=19;++i)	for(LL j=1;j<=N;++j)	fa[i][j]=fa[i-1][fa[i-1][j]];
	LL lst=0;
	LL mod=(n+1)*(n+2)/2;
	while(q-->0)
	{
		LL u=read(),v=read();
		u=(u-1+lst*T)%mod+1,v=(v-1+lst*T)%mod+1;
		LL du=lower_bound(siz,siz+1+n,u)-siz,dv=lower_bound(siz,siz+1+n,v)-siz;
		LL pu=query(rt[du],1,n+1,u-siz[du-1]),pv=query(rt[dv],1,n+1,v-siz[dv-1]);
		LL lca=LCA(pu,pv);
		write(lst=min({u,v,id[lca]})),puts("");
	}
	return 0;
}