判断一个序列是不是另一个序列的子序列。
本题有两种解法:
①、直接用vector二分O(n + m logn)。
②、用主席树维护序列自动机(n logn + m logn)。
①、
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
#define pb push_back
using namespace std;
const int maxn=1001000;
int n,q,m,x;
vector<int>vc[maxn];
int main(void)
{
scanf("%*d%d%d%d",&n,&q,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
vc[x].pb(i);
}
for(int i=1;i<=q;i++)
{
int k,pos=0;
bool flag=false;
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
scanf("%d",&x);
if(!flag)
{
auto it=upper_bound(vc[x].begin(),vc[x].end(),pos);
if(it==vc[x].end()) flag=true;
else pos=*it;
}
}
if(!flag) printf("Yes\n");
else printf("No\n");
}
return 0;
}
②、
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define ll long long
#define llu unsigned ll
#define pb push_back
using namespace std;
const int maxn=1001000;
int a[maxn],rt[maxn],n,q,m,x,cnt=0;
struct node
{
int lc,rc,val;
}t[maxn*22];
void init(void)
{
t[0].lc=t[0].rc=t[0].val=0;
}
int change(int pre,int l,int r,int pos,int val)
{
int p=++cnt;
t[p]=t[pre];
if(l==r)
{
t[p].val=val;
return p;
}
int mid=(l+r)>>1;
if(pos<=mid) t[p].lc=change(t[pre].lc,l,mid,pos,val);
else t[p].rc=change(t[pre].rc,mid+1,r,pos,val);
return p;
}
int ask(int p,int l,int r,int pos)
{
if(l==r) return t[p].val;
int mid=(l+r)>>1;
if(pos<=mid) return ask(t[p].lc,l,mid,pos);
else return ask(t[p].rc,mid+1,r,pos);
}
int main(void)
{
scanf("%*d%d%d%d",&n,&q,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=n-1;i>=0;i--)
rt[i]=change(rt[i+1],1,m,a[i+1],i+1);
for(int i=1;i<=q;i++)
{
int k,pos=0;
bool flag=false;
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
scanf("%d",&x);
if(!flag)
{
pos=ask(rt[pos],1,m,x);
if(pos==0) flag=true;
}
}
if(!flag) printf("Yes\n");
else printf("No\n");
}
return 0;
}