[Codeforces1037H]Security(SAM+线段树合并)

题面

分析

CF什么时候也开始出这种套路题了
和[NOI2018]你的名字几乎一模一样,看到区间串问题,用线段树维护right集合,每次沿着转移边走的时候要判断一下转移到的节点的right集合中是否有在\([l,r]\)内的值.
因此对于每个询问串在自动机上跑求出和区间内字符的LCP.然后倒序,每次尝试加一个比当前字符大的字符,判断区间内是否存在这样的转移即可。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxc 26
#define maxn 500000
#define maxlogn 30
using namespace std;
int n,m;
char s[maxn+5],t[maxn+5];



struct segment_tree {
#define lson(x) (tree[x].ls)
#define rson(x) (tree[x].rs)
    struct node {
        int ls;
        int rs;
        int val;
    } tree[maxn*maxlogn+5];
    int ptr=0;
    void push_up(int x) {
        tree[x].val=tree[lson(x)].val+tree[rson(x)].val;
    }
    void update(int &x,int upos,int l,int r) {
        x=++ptr;
        if(l==r) {
            tree[x].val++;
            return;
        }
        int mid=(l+r)>>1;
        if(upos<=mid) update(lson(x),upos,l,mid);
        else update(rson(x),upos,mid+1,r);
        push_up(x);
    }
    int query(int x,int L,int R,int l,int r) {
        if(x==0||L>R) return 0;
        if(L<=l&&R>=r) return tree[x].val;
        int mid=(l+r)>>1;
        int ans=0;
        if(L<=mid) ans+=query(lson(x),L,R,l,mid);
        if(R>mid) ans+=query(rson(x),L,R,mid+1,r);
        return ans;
    }
    int merge(int x,int y) {
        if(!x||!y) return x+y;
        int now=++ptr;
        tree[now].val=tree[x].val+tree[y].val;
        lson(now)=merge(lson(x),lson(y));
        rson(now)=merge(rson(x),rson(y));
        return now;
    }
#undef lson
#undef rson
} Tr;


struct SAM {
#define link(x) t[x].link
#define len(x) t[x].len
    struct node {
        int ch[maxc];
        int link;
        int len;
        int root;
    } t[maxn*2+5];
    const int root=1;
    int last=root;
    int ptr=1;
    void extend(int c,int pos) {
        int p=last,cur=++ptr;
        len(cur)=len(p)+1;
        if(pos) Tr.update(t[cur].root,pos,1,n);
        while(p&&t[p].ch[c]==0) {
            t[p].ch[c]=cur;
            p=link(p);
        }
        if(p==0) link(cur)=root;
        else {
            int q=t[p].ch[c];
            if(len(p)+1==len(q)) link(cur)=q;
            else {
                int clo=++ptr;
                len(clo)=len(p)+1;
                for(int i=0; i<maxc; i++) t[clo].ch[i]=t[q].ch[i];
                link(clo)=link(q);
                link(q)=link(cur)=clo;
                while(p&&t[p].ch[c]==q) {
                    t[p].ch[c]=clo;
                    p=link(p);
                }
            }
        }
        last=cur;
    }
    void insert(char *s) {
        int len=strlen(s+1);
        for(int i=1; i<=len; i++) extend(s[i]-'a',i);
    }
    void topo_sort() {
        static int in[maxn+5];
        queue<int>q;
        for(int i=1; i<=ptr; i++) in[link(i)]++;
        for(int i=1; i<=ptr; i++) if(!in[i]) q.push(i);
        while(!q.empty()) {
            int x=q.front();
            q.pop();
            if(link(x)==0) continue;
            in[link(x)]--;
            t[link(x)].root=Tr.merge(t[link(x)].root,t[x].root);
            if(in[link(x)]==0) q.push(link(x));
        }
    }
    void match(char *st,int l,int r) {
        static int no[maxn+5];
        int len=strlen(st+1);
        int x=root;
        no[0]=1;
        for(int i=1; i<=len; i++) no[i]=-1;
        for(int i=1; i<=len; i++) {
            int c=st[i]-'a';
            if(t[x].ch[c]&&Tr.query(t[t[x].ch[c]].root,l,r,1,n)) x=t[x].ch[c];
            else break;
            no[i]=x;
        }
        for(int i=len; i>=0; i--) {
            if(no[i]==-1) continue;
            int c=st[i+1]-'a'+1;
            int x=no[i];
            if(i==len) c=0;
            for(int j=c; j<maxc; j++) {
                if(Tr.query(t[t[x].ch[j]].root,l+i,r,1,n)) {
                    //注意因为当前节点在i+1位,所以right的范围不是[l,r]而是[l+i,r]
                    for(int k=1; k<=i; k++) putchar(st[k]);
                    putchar(j+'a');
                    putchar('\n');
                    return;
                }
            }
        }
        puts("-1");
    }
} S;

int main() {
//  int l,r;
    scanf("%s",s+1);
    n=strlen(s+1);
    scanf("%d",&m);
    int l,r;
    S.insert(s);
    S.topo_sort();
    for(int i=1; i<=m; i++) {
        scanf("%d %d %s",&l,&r,t+1);
        S.match(t,l,r);
    }
}
/*
bacb
4
1 3 ac
*/