题解：P7769 「CGOI-1」大师选徒

· · 题解

考虑什么时候 \forall k\in[0,r-l],a_{l+k}+a_{b+k}=s，等价于：

特判 l=r，令 A_i=a_i-a_{i+1},B_i=-A_i，则相当于问是否存在 B_b,\dots,B_{b+r-l-1} 与 A_l,\dots,A_{r-1} 完全匹配且 a_b=s-a_l。

若没有第二个条件，可以用后缀数组实现快速比较子串，二分即可。那么直接将排序结果挂到后缀起点对应的值上二分，即可做到 O(n\log n)。

卡了很久，你最好使用小常数 SA。

#include<bits/stdc++.h>
#define rep(i,l,r) for(int i=(l),qwp=(r);i<=qwp;i++)
#define per(i,r,l) for(int i=(r),qwp=(l);i>=qwp;i--)
#define repll(i,l,r) for(ll i=(l),qwp=(r);i<=qwp;i++)
#define perll(i,r,l) for(ll i=(r),qwp=(l);i>=qwp;i--)
#define pb push_back
#define ins insert
#define clr clear
#define rem(S,X) (S).erase((S).find((X)))
#define uset unordered_set
#define umap unordered_map
#define mset multiset
using namespace std;
namespace ax_by_c{
const int MB=1<<20;
struct FastIO{
    char ib[MB+100],*p,*q;
    char ob[MB+100],*r,stk[128];
    int tp;
    FastIO(){p=q=ib,r=ob,tp=0;}
    ~FastIO(){fwrite(ob,1,r-ob,stdout);}
    char read_char(){
        if(p==q){
            p=ib,q=ib+fread(ib,1,MB,stdin);
            if(p==q)return 0;
        }
        return *p++;
    }
    template<typename T>
    void read_int(T& x){
        char c=read_char(),l=0;
        for(x=0;!isdigit(c);c=read_char())l=c;
        for(;isdigit(c);c=read_char())x=x*10-'0'+c;
        if(l=='-')x=-x;
    }
    void write_char(char c){
        if(r-ob==MB)r=ob,fwrite(ob,1,MB,stdout);
        *r++=c;
    }
    template<typename T>
    void write_int(T x){
        if(x<0)write_char('-'),x=-x;
        do stk[++tp]=x%10+'0';
        while(x/=10);
        while(tp)write_char(stk[tp--]);
    }
}IO;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
const int N=8e5+5;
const int LN=20;
namespace SA{
    int cnt[N],id[N],ork[N*2];
    void bld(int n,int *s,int *rk,int *sa,int *ht){
        int m=n;
        rep(i,1,n)rk[i]=s[i],cnt[rk[i]]++;
        rep(i,1,m)cnt[i]+=cnt[i-1];
        rep(i,1,n)sa[cnt[rk[i]]--]=i;
        for(int w=1;w<=n;w<<=1){
            int idx=0;
            rep(i,n-w+1,n)id[++idx]=i;
            rep(i,1,n)if(sa[i]>w)id[++idx]=sa[i]-w;
            rep(i,1,m)cnt[i]=0;
            rep(i,1,n)cnt[rk[i]]++;
            rep(i,1,m)cnt[i]+=cnt[i-1];
            per(i,n,1)sa[cnt[rk[id[i]]]--]=id[i];
            rep(i,1,n)ork[i]=rk[i];
            int p=0;
            rep(i,1,n){
                if(ork[sa[i-1]]!=ork[sa[i]]||ork[sa[i-1]+w]!=ork[sa[i]+w])p++;
                rk[sa[i]]=p;
            }
            if(p==n)break;
            m=p;
        }
        rep(i,1,n){
            ht[rk[i]]=max(ht[rk[i-1]]-1,0);
            while(s[sa[rk[i]-1]+ht[rk[i]]]==s[sa[rk[i]]+ht[rk[i]]])ht[rk[i]]++;
        }
    }
}
struct DS1{
    int lg2[N],mn[N][LN];
    void bld(int n,int *a){
        rep(i,2,n)lg2[i]=lg2[i>>1]+1;
        rep(i,1,n)mn[i][0]=a[i];
        rep(j,1,19)rep(i,1,n-(1<<j)+1)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
    }
    int Q(int l,int r){
        int x=lg2[r-l+1];
        return min(mn[l][x],mn[r-(1<<x)+1][x]);
    }
}ST;
int n,q,a[N];
int s[N],hsh[N],hc;
int rk[N],sa[N],ht[N];
set<int>S;
vector<int>pos[N];
bool cmp(int l1,int r1,int l2,int r2){
    if(l1==l2)return r1<r2;
    int p=ST.Q(min(rk[l1],rk[l2])+1,max(rk[l1],rk[l2]));
    if(p<min(r1-l1+1,r2-l2+1))return s[l1+p]<s[l2+p];
    return r1-l1+1<r2-l2+1;
}
void slv(int _csid,int _csi){
    IO.read_int(n),IO.read_int(q);
    rep(i,1,n)IO.read_int(a[i]),S.ins(a[i]);
    rep(i,1,n-1)s[i]=a[i]-a[i+1],s[n+i]=a[i+1]-a[i];
    rep(i,1,n*2)hsh[++hc]=s[i];
    sort(hsh+1,hsh+1+hc),hc=unique(hsh+1,hsh+1+hc)-hsh-1;
    rep(i,1,n*2)s[i]=lower_bound(hsh+1,hsh+1+hc,s[i])-hsh;
    SA::bld(n*2,s,rk,sa,ht);
    ST.bld(n*2,ht);
    rep(i,1,n*2)if(n<sa[i]&&sa[i]<n*2)pos[a[sa[i]-n]].pb(sa[i]);
    rep(_,1,q){
        int ss,l,r;
        IO.read_int(ss),IO.read_int(l),IO.read_int(r);
        if(l==r){
            if(S.count(ss-a[l]))IO.write_char('Y'),IO.write_char('e'),IO.write_char('s'),IO.write_char('\n');
            else IO.write_char('N'),IO.write_char('o'),IO.write_char('\n');
            continue;
        }
        if(ss-a[l]<1||n<ss-a[l]||!pos[ss-a[l]].size()){
            IO.write_char('N'),IO.write_char('o'),IO.write_char('\n');
            continue;
        }
        int p=0,q=0;
        {
            int L=0,R=pos[ss-a[l]].size()-1,mid,res=-1;
            while(L<=R){
                mid=(L+R)>>1;
                if(cmp(pos[ss-a[l]][mid],min(pos[ss-a[l]][mid]+r-l-1,n*2),l,r-1))res=mid,L=mid+1;
                else R=mid-1;
            }
            p=res+1;
        }
        {
            int L=0,R=pos[ss-a[l]].size()-1,mid,res=-1;
            while(L<=R){
                mid=(L+R)>>1;
                if(!cmp(l,r-1,pos[ss-a[l]][mid],min(pos[ss-a[l]][mid]+r-l-1,n*2)))res=mid,L=mid+1;
                else R=mid-1;
            }
            q=res;
        }
        if(p<=q)IO.write_char('Y'),IO.write_char('e'),IO.write_char('s'),IO.write_char('\n');
        else IO.write_char('N'),IO.write_char('o'),IO.write_char('\n');
    }
}
void main(){
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1,csid=-1;
    // scanf("%d",&csid);
    // scanf("%d",&T);
    // scanf("%d",&csid);
    rep(i,1,T)slv(csid,i);
}
}
int main(){
    string __name="";
    if(__name!=""){
        freopen((__name+".in").c_str(),"r",stdin);
        freopen((__name+".out").c_str(),"w",stdout);
    }
    ax_by_c::main();
    return 0;
}
/*
g++ -std=c++14 -O2 -Wall -Wextra "-Wl,--stack=200000000" A.cpp -o A.exe
A.exe
*/