首页 > > 程序设计 > C/C++ >

bzoj3207--Hash+主席树

2018-06-17 23:28:56来源：未知阅读 ()

题目大意：

给定一个n个数的序列和m个询问(n,m<=100000)和k，每个询问包含k+2个数字：l,r,b[1],b[2]...b[k]，要求输出b[1]~b[k]在[l,r]中是否出现。

思路：
把所有连续的k个数字hash一下，然后扔进主席树，询问时在主席树中查询就可以了。

注意(坑)点：
1、hash值要用unsigned long long存

2、如果直接求l+r>>1会爆，所以要改成(l>>1)+(r>>1)+(l&r&1)

3、Yes和No是反的。。。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<limits.h>
 6 using namespace std;
 7 #define N 100001
 8 #define M ULLONG_MAX
 9 #define ll unsigned long long
10 inline char Nc(){
11     static char buf[100000],*p1=buf,*p2=buf;
12     if(p1==p2){
13         p2=(p1=buf)+fread(buf,1,100000,stdin);
14         if(p1==p2)return EOF;
15     }
16     return *p1++;
17 }
18 inline void Read(int& x){
19     char c=Nc(),b=1;
20     for(;c<'0'||c>'9';c=Nc())if(c=='-')b=-1;
21     for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=Nc());x*=b;
22 }
23 struct Gj{
24     int l,r,w;
25 }c[N*80];
26 int Num,i,j,k,n,m,Rt[N],x,y,z,a[N];
27 ll Hash[N],w,h;
28 inline void Update(int& Node,ll l,ll r,ll x){
29     c[++Num]=c[Node];Node=Num;
30     c[Node].w++;
31     if(l==r)return;
32     ll Mid=(l>>1)+(r>>1)+(l&r&1);
33     if(x<=Mid)Update(c[Node].l,l,Mid,x);else Update(c[Node].r,Mid+1,r,x);
34 }
35 inline bool Query(int x,int y,ll l,ll r,ll h){
36     if(c[y].w-c[x].w==0)return 0;
37     if(l==r)return 1;
38     ll Mid=(l>>1)+(r>>1)+(l&r&1);
39     if(h<=Mid)return Query(c[x].l,c[y].l,l,Mid,h);else return Query(c[x].r,c[y].r,Mid+1,r,h);
40 }
41 int main()
42 {
43     Read(n);Read(m);Read(k);
44     for(i=1;i<=n;i++)Read(a[i]);
45     for(i=1;i<=n;i++)Hash[i]=Hash[i-1]*99997+a[i];
46     for(w=1,i=1;i<=k;i++)w*=99997;
47     for(i=k;i<=n;i++){
48         Rt[i]=Rt[i-1];
49         Update(Rt[i],1,M,Hash[i]-Hash[i-k]*w);
50     }
51     for(i=1;i<=m;i++){
52         Read(x);Read(y);
53         for(h=0,j=1;j<=k;j++)Read(z),h=h*99997+z;
54         if(y-x+1>=k&&Query(Rt[x+k-2],Rt[y],1,M,h))puts("No");else puts("Yes");
55     }
56     return 0;
57 }