526互联

The 2023 ICPC Asia EC Regionals Online Contest (I) - Problem H. Range Periodicity Query

发布时间 2023-10-05 01:52:28作者: Claris

对于一个周期长度$p$来说，如果它不是$S_k$的周期，那么它一定不是$S_{k+1}$的周期，因此可以二分出分界线$t_p$满足它是$S_p,S_{p+1},S_{p+2},\dots,S_{t_p}$的周期，但不是$S_{t_p+1}$的周期。对于一个询问$(k,l,r)$，问题等价于寻找区间中数值最小的数，满足它的$t$值至少为$k$。将所有询问按$k$从大到小排序，并将所有周期按$t$值从大到小排序，用线段树支持单点修改、区间查询最小值即可。

时间复杂度$\mathcal{O}(n\log n)$。

 

#include<cstdio>
const int BUF=20000000;
char Buf[BUF],*buf=Buf;
inline void readch(char&a){for(;!((*buf>='a'&&*buf<='z')||(*buf>='A'&&*buf<='Z'));buf++);a=*buf++;}
inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
const int OUT=4000000;
char Out[OUT],*ou=Out;int Outn[30],Outcnt;
inline void write(int x){
  if(x<0){
    *ou++='-';
    x*=-1;
  }
  if(!x)*ou++=48;
  else{
    for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;
    while(Outcnt)*ou++=Outn[Outcnt--];
  }
}
inline void writeln(int x){write(x);*ou++='\n';}
const int N=500005,S1=13331,P1=1000000007,S2=233,P2=1000000009;
int n,m,q,i,j,x,y,f[N],st[N],head,tail,cur,que[N][2],ans[N],pos[N],v[1111111];
int p1[N],h1[N*2],p2[N],h2[N*2];
char a[N*2];
int e[N],w[N],nxt[N];
int g[N],nxtq[N];
inline int geth1(int l,int r){return((h1[r]-1LL*h1[l-1]*p1[r-l+1])%P1+P1)%P1;}
inline int geth2(int l,int r){return((h2[r]-1LL*h2[l-1]*p2[r-l+1])%P2+P2)%P2;}
inline int getper(int x){
  int l=x+1,r=n,mid,t=x;
  while(l<=r){
    mid=(l+r)>>1;
    int L=st[mid],R=L+mid-1;
    if(geth1(L,R-x)==geth1(L+x,R)&&geth2(L,R-x)==geth2(L+x,R))l=(t=mid)+1;else r=mid-1;
  }
  return t;
}
inline void up(int&a,int b){a>b?(a=b):0;}
void build(int x,int a,int b){
  v[x]=N;
  if(a==b){
    pos[a]=x;
    return;
  }
  int mid=(a+b)>>1;
  build(x<<1,a,mid),build(x<<1|1,mid+1,b);
}
inline void ins(int x,int p){for(x=pos[x];x;x>>=1)up(v[x],p);}
void ask(int x,int a,int b,int c,int d){
  if(c<=a&&b<=d){
    up(cur,v[x]);
    return;
  }
  int mid=(a+b)>>1;
  if(c<=mid)ask(x<<1,a,mid,c,d);
  if(d>mid)ask(x<<1|1,mid+1,b,c,d);
}
int main(){
  fread(Buf,1,BUF,stdin);
  read(n);
  head=n+1;
  tail=n;
  for(i=1;i<=n;i++){
    char op;
    readch(op);
    if(op>='a'&&op<='z')a[--head]=op;
    else a[++tail]=op-'A'+'a';
    st[i]=head;
  }
  for(p1[0]=i=1;i<=n;i++)p1[i]=1LL*p1[i-1]*S1%P1;
  for(i=head;i<=tail;i++)h1[i]=(1LL*h1[i-1]*S1+a[i])%P1;
  for(p2[0]=i=1;i<=n;i++)p2[i]=1LL*p2[i-1]*S2%P2;
  for(i=head;i<=tail;i++)h2[i]=(1LL*h2[i-1]*S2+a[i])%P2;
  for(i=1;i<=n;i++)f[i]=getper(i);
  read(m);
  for(i=1;i<=m;i++){
    read(x);
    y=f[x];
    w[i]=x;
    nxt[i]=e[y];
    e[y]=i;
  }
  read(q);
  for(i=1;i<=q;i++){
    read(x);read(que[i][0]);read(que[i][1]);
    nxtq[i]=g[x];
    g[x]=i;
  }
  build(1,1,m);
  for(i=n;i;i--){
    for(j=e[i];j;j=nxt[j])ins(j,w[j]);
    for(j=g[i];j;j=nxtq[j]){
      cur=N;
      ask(1,1,m,que[j][0],que[j][1]);
      if(cur>i)cur=-1;
      ans[j]=cur;
    }
  }
  for(i=1;i<=q;i++)writeln(ans[i]);
  fwrite(Out,1,ou-Out,stdout);
}