BZOJ3207 花神的嘲讽计划

hash值建主席树。

垃圾题面没有熟虑范围害我MLE——>RE。

By：大奕哥

 #include<bits/stdc++.h>

 #define unll unsigned long long

 #define inf 18446744073709551615UL

 using namespace std;

 const int N=;

 struct node{

     int l,r,s;

 }t[];

 int a[N],rt[N],n,m,k,cnt;unll H[N],pos[N],num;

 void change(int &x,unll l,unll r,unll w)

 {

     t[++cnt]=t[x];x=cnt;

     if(l==r){

         t[x].s++;return;

     }

     int mid=l+r>>;

     if(w<=mid)change(t[x].l,l,mid,w);

     else change(t[x].r,mid+,r,w);

     t[x].s=t[t[x].l].s+t[t[x].r].s;

 }

 int query(int x,int y,unll l,unll r,unll w)

 {

     if(l==r)return t[x].s-t[y].s;

     unll mid=l+r>>;

     if(w<=mid)return query(t[x].l,t[y].l,l,mid,w);

     else return query(t[x].r,t[y].r,mid+,r,w);

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&k);unll base=;

     for(int i=;i<=n;++i)scanf("%d",&a[i]);

     for(int i=;i<=k;++i)base*=;

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

     {

         H[i]=H[i-]*+a[i];

         pos[++num]=H[i]-H[i-k]*base;

     }

     sort(pos+,pos++num);num=unique(pos+,pos++num)-pos-;

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

     rt[i]=rt[i-],change(rt[i],,num,lower_bound(pos+,pos++num,H[i]-H[i-k]*base)-pos);

     int l,r,x; unll w;

     for(int i=;i<=m;++i)

     {

         scanf("%d%d",&l,&r);w=;

         for(int j=;j<=k;++j)

         {

             scanf("%d",&x);

             w=w*+x;

         }

         int p=lower_bound(pos+,pos++num,w)-pos;

         if(pos[p]!=w)puts("Yes");

         else if(query(rt[r],rt[l+k-],,num,p))puts("No");

         else puts("Yes");

     }

     return ;

 }