题目概述

有一个二进制数序列 $\{A_n\}$ ，现在有 $Q$ 个询问，每次询问 $(L,R,X)$ 表示询问 $[L,R]$ 中与二进制数 $X$ 异或值最大的元素的下标。

解题报告

友情提示：这题剧毒。翰爷和法老一起秒了，翰爷表示阈值之后长度小的串可以直接用可持久化Trie来做，但是长度长的串就比较麻烦，法老表示长度长的串可以直接哈希+二分出两两之间第一个不相同的位置就可以比较了。

写起来巨麻烦，细节很多，要注意位数不够的各种情况。CC空间没有限制真爽。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<vector>
using namespace std;
typedef unsigned long long ULL;
const int maxn=100000,maxl=1000000,S=500,maxt=maxn*S+maxn,maxm=maxl/S;

int n,te,si,ro[maxn+5],son[maxt+5][2],sum[maxt+5],LX;char s[maxl+5];vector<int> v[maxl+S+5];
int m;int pos[maxm+5];vector<bool> a[maxm+5];int p[maxm+5][maxm+5];vector<ULL> ha[maxm+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r))?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
inline int reads(char *s){
    int len=0;char ch=readc();while (!isdigit(ch)) {if (ch==EOF) return EOF;ch=readc();}
    while (isdigit(ch)) s[++len]=ch,ch=readc();s[len+1]=0;return len;
}
inline void Fix(char *s,int len){
    int D=S-len;for (int i=S;i>D;i--) s[i]=s[i-D];
    for (int i=1;i<=D;i++) s[i]='0';s[S+1]=0;
}
int Insert(int p,char *s,int i=1){
    int now=++si;son[now][0]=son[p][0];son[now][1]=son[p][1];sum[now]=sum[p]+1;
    if (s[i]) son[now][s[i]-'0']=Insert(son[p][s[i]-'0'],s,i+1);return now;
}
namespace Trie{
    int si,son[maxl+S+5][2];
    inline void Insert(char *s,int pos,int p=0){
        for (int i=1;s[i];i++) {int &now=son[p][s[i]-'0'];if (!now) now=++si;p=now;}
        v[p].push_back(pos);
    }
}
inline void Make(){
    for (int i=1;i<=m;i++){
        ha[i].push_back(a[i][0]?233:23);
        for (int j=1,si=a[i].size();j<si;j++)
            ha[i].push_back(ha[i][j-1]*2333+(a[i][j]?233:23));
    }
}
inline int Find(int A,int B){
    if (a[A].size()!=a[B].size()) return -1;int L=0,R=int(a[A].size())-1;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) ha[A][mid]!=ha[B][mid]?R=mid-1:L=mid+1;return L;
}
inline bool cmp(int A,int B){
    int LA=a[A].size(),LB=a[B].size();if (LA==LB&&p[A][B]==LA) return A<B;
    if (LA!=LB) {int MAX=max(LA,LB);bool fl=LA>LB;if (MAX<=LX) fl^=s[LX-MAX+1]=='1';return fl;}
    bool fl=a[A][p[A][B]];if (LA-p[A][B]<=LX) fl^=s[LX-(LA-p[A][B])+1]=='1';return fl;
}
inline int Min(const vector<int> &v,int l,int r){
    int L=0,R=int(v.size())-1;
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) v[mid]>=l?R=mid-1:L=mid+1;
    if (L==v.size()||v[L]>r) return 0;return v[L];
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int i=(readi(n),readi(te),1),len;i<=n;i++)
        if (len=reads(s),ro[i]=ro[i-1],len<=S) Fix(s,len),Trie::Insert(s,i),ro[i]=Insert(ro[i],s);
        else {pos[++m]=i;for (int i=1;i<=len;i++) a[m].push_back(s[i]-48);}
    Make();for (int i=1;i<m;i++) for (int j=i+1;j<=m;j++) p[i][j]=p[j][i]=Find(i,j);
    for (int L,R;te;te--){
        readi(L);readi(R);LX=reads(s);int ans=0;
        for (int i=1;i<=m;i++) if (L<=pos[i]&&pos[i]<=R&&(!ans||cmp(i,ans))) ans=i;
        int pA=ro[L-1],pB=ro[R],P=0;if (LX<S) Fix(s,LX),LX=S;
        for (int i=LX-S+1;s[i];i++){
            int c=s[i]-'0';if (sum[son[pB][c^1]]-sum[son[pA][c^1]]) c^=1;
            pA=son[pA][c];pB=son[pB][c];P=Trie::son[P][c];
        }int p=0;if (P) p=Min(v[P],L,R);
        if (p&&(!ans||a[ans].size()<=LX&&s[LX-a[ans].size()+1]=='1')) ans=p; else ans=pos[ans];
        printf("%d\n",ans);
    }return 0;
}