【题解】CF1142B Lynyrd Skynyrd(倍增)

【题解】CF1142B Lynyrd Skynyrd(倍增)

调了一个小时原来是读入读反了....

求子段是否存在一个排列的子序列的套路是把给定排列看做置换，然后让给定的序列乘上这个置换，问题就转化为最长上升序列。这是因为一个数的前驱后继是唯一的。

这一题稍微改变了一下，我们要求的是类似于\(4\quad 5\quad1\quad 2 \quad 3\)的子序列。就相当于给1添了个前驱n，给\(n\)添了个后继\(1\)，本质还是一样的，仍然是一个数的前驱后继是唯一的。

原本1,m没有额外关系时，做法是定位所有\(1\)考虑一步步倍增后继到\(m\)看位置在哪。现在1,m有关系了，就每个点都可以成为起点。现在就是维护一个数据求区间\(\min\)了，随你怎么写，可以询问离线\(O(n)\)但是我直接st表了

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;  typedef long long ll;

inline int qr(){

	register int ret=0,f=0;

	register char c=getchar();

	while(!isdigit(c))f|=c==45,c=getchar();

	while(isdigit(c)) ret=ret*10+c-48,c=getchar();

	return f?-ret:ret;

}

const int maxn=2e5+5;

int p[maxn],data[maxn];

int st[19][maxn],Pair[maxn],Min[19][maxn];

int lg[maxn];

int last[maxn];

int n,m,T;

const int inf=0x3f3f3f3f;

int main(){

	/*

#ifndef ONLINE_JUDGE

	freopen("in.in","r",stdin);

	freopen("out.out","w",stdout);

#endif

	*/

	m=qr(); n=qr();  T=qr();

	for(int t=2;t<=n;++t) lg[t]=lg[t>>1]+1;

	for(int t=1;t<=m;++t) p[qr()]=t;

	for(int t=1;t<=n;++t) data[t]=p[qr()];

	//for(int t=1;t<=n;++t) cerr<<data[t]<<' ';

	//cerr<<('\n');

	for(int t=n;t;--t){

		if(last[data[t]+1]) st[0][t]=last[data[t]+1];

		if(data[t]==m&&last[1]) st[0][t]=last[1];

		last[data[t]]=t;

	}

	//for(int t=1;t<=n;++t) cerr<<st[0][t]<<' ';

	//cerr<<endl;

	for(int t=1;t<=lg[m];++t)

		for(int i=1;i<=n;++i)

			st[t][i]=st[t-1][st[t-1][i]];

	memset(Min,0x3f,sizeof Min);

	for(int t=1;t<=n;++t){

		int k=t;

		for(int i=0;i<=lg[m-1];++i)

			if(((m-1)>>i&1))

				k=st[i][k];

		if(k) Min[0][t]=k;

	}

	for(int t=1;t<=lg[n];++t)

		for(int i=1;i<=n;++i)

			Min[t][i]=min(Min[t-1][i]?Min[t-1][i]:inf,Min[t-1][i+(1<<t>>1)]?Min[t-1][i+(1<<t>>1)]:inf);

	//for(int t=1;t<=n;++t) cerr<<Min[1][t]<<' ';

	//cerr<<endl;

	while(T--){

		int l=qr(),r=qr();

		//cerr<<"min="<<Min[lg[r-l+1]][l]<<' '<<Min[lg[r-l+1]][r-(1<<lg[r-l+1])+1] <<endl;

		if(min(Min[lg[r-l+1]][l],Min[lg[r-l+1]][r-(1<<lg[r-l+1])+1])<=r) putchar(49);

		else putchar(48);

	}

	putchar(10);

	return 0;

}