题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=3207
题意:给出一个数列,若干询问。每个询问查询[L,R]区间内是否存在某个长度为K的子数列(连续的)。
思路:将长度为K的每个子数列哈希成一个值,将查询也哈希成一个值,建立函数式线段树,然后对于查询[L,R],查询个数是否大于0。
int n,m,K,a[N];
int st[N],ed[N];
u64 b[N],bNum;
u64 p[N],q[N];
u64 getHash(int L,int R)
{
u64 ans=0;
int i;
for(i=L;i<=R;i++) ans=ans*107+a[i];
return ans;
}
struct node
{
int L,R,a,b,s;
};
node tree[N<<4];
int root[N],tot;
int build(int a,int b)
{
int k=++tot;
tree[k].a=a;
tree[k].b=b;
tree[k].s=0;
int mid=(a+b)>>1;
if(a!=b)
{
tree[k].L=build(a,mid);
tree[k].R=build(mid+1,b);
}
return k;
}
int insert(int p,int x)
{
int k=++tot;
tree[k]=tree[p];
tree[k].s++;
if(tree[k].a==x&&tree[k].b==x) return k;
int mid=(tree[k].a+tree[k].b)>>1;
if(x<=mid) tree[k].L=insert(tree[p].L,x);
else tree[k].R=insert(tree[p].R,x);
return k;
}
int get(int p,int x)
{
if(tree[p].a==tree[p].b) return tree[p].s;
int mid=(tree[p].a+tree[p].b)>>1;
if(x<=mid) return get(tree[p].L,x);
else get(tree[p].R,x);
}
int main()
{
RD(n,m,K);
int i;
FOR1(i,n) RD(a[i]);
bNum=n-K+1;
FOR1(i,bNum) p[i]=b[i]=getHash(i,i+K-1);
int j,x;
u64 t;
FOR1(i,m)
{
RD(st[i],ed[i]); ed[i]=ed[i]-K+1;
t=0;
FOR1(j,K) RD(x),t=t*107+x;
q[i]=b[++bNum]=t;
}
sort(b+1,b+bNum+1);
root[0]=build(1,bNum);
FOR1(i,n-K+1)
{
a[i]=lower_bound(b+1,b+bNum+1,p[i])-b;
root[i]=insert(root[i-1],a[i]);
}
FOR1(i,m)
{
x=lower_bound(b+1,b+bNum+1,q[i])-b;
if(get(root[ed[i]],x)-get(root[st[i]-1],x)>0) puts("No");
else puts("Yes");
}
}