CF1142B Lynyrd Skynyrd 倍增+可持久化線段樹

Description

給一個n排列p，一個長為m的序列a，q次詢問[l,r]求l到r是否存在長度為n的子序列恰好與p循環同構

n , m , q ≤ 2 ∗ 1 0 5 n,m,q\le 2*10^5 n,m,q≤2∗105

Solution

用圖表示這個東西就是a按照p中的順序向後連邊，題目就等價于問l到r能不能走完n-1步了

考慮倍增這個東西，那麼我們就能求出以x為起點向後n-1步最前到哪裡，然後可持久化線段樹二維數點就完事了

一開始沒考慮不能往後連邊也就是走到0的情況wa了一發，血虧.jpg

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define drp(i,st,ed) for (int i=st;i>=ed;--i)

const int N=400005;

struct treeNode {int l,r,sum;} t[N*25];

std:: map <int,int> wjp,rec;

int a[N],b[N],nxt[21][N];
int rt[N],lg[N],tot,n,m,k;

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):v,ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

void modify(int &now,int pre,int tl,int tr,int x) {
	t[now=++tot]=t[pre]; t[now].sum++;
	if (tl==tr) return ;
	int mid=(tl+tr)>>1;
	if (x<=mid) modify(t[now].l,t[pre].l,tl,mid,x);
	else modify(t[now].r,t[pre].r,mid+1,tr,x);
}

int query(int now,int pre,int tl,int tr,int l,int r) {
	if (r<l||!now) return 0;
	if (tl>=l&&tr<=r) return t[now].sum-t[pre].sum;
	int mid=(tl+tr)>>1,res=0;
	if (l<=mid) res+=query(t[now].l,t[pre].l,tl,mid,l,r);
	if (mid+1<=r) res+=query(t[now].r,t[pre].r,mid+1,tr,l,r);
	return res;
}

void pre() {
	rep(i,2,m) lg[i]=lg[i>>1]+1;
	rep(j,1,lg[m]) rep(i,1,m-(1<<j)+1) {
		nxt[j][i]=nxt[j-1][nxt[j-1][i]];
	}
	n--;
	rep(i,1,m) {
		int x=i;
		drp(j,lg[n],0) if ((n>>j)&1) {
			x=nxt[j][x];
		}
		modify(rt[i],rt[i-1],0,m+1,x);
	}
	n++;
}

int main(void) {
	// freopen("data.in","r",stdin);
	n=read(),m=read(),k=read();
	rep(i,1,n) a[i]=read();
	rep(i,1,n) wjp[a[i]]=a[i+1];
	wjp[a[n]]=a[1];
	rep(i,1,m) b[i]=read();
	drp(i,m,1) {
		if (rec[wjp[b[i]]]) {
			nxt[0][i]=rec[wjp[b[i]]];
		} else nxt[0][i]=m+1;
		rec[b[i]]=i;
	}
	pre();
	for (;k--;) {
		int l=read(),r=read();
		int res=query(rt[r],rt[l-1],0,m+1,l,r);
		putchar(res?'1':'0');
	}
	return 0;
}