[BZOJ3879] SvT

Description

给定一个长为 \(n\) 的串和 \(m\) 次询问，每次询问 \(t\) 个后缀之间两两LCP。\(n\leq 5\cdot 10^5,\sum t\leq 3\cdot 10^6\) 。

Solution

就是求出来SA，然后把给定的 \(t\) 个串按照 \(rk\) 排序。求出相邻两个LCP -> 求出序列间两两最小值 -> 考虑贡献，对于每个数求是哪些数对的最小值 -> 求每个数左边右边第一个比它小的数 -> 单调栈。

woc好牛逼

Code

#pragma GCC optimize(2)
#include
using std::min;
using std::max;
using std::swap;
using std::vector;
typedef double db;
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pair
#define all(A) A.begin(),A.end()
#define mp(A,B) std::make_pair(A,B)
const int N=5e5+5;

char s[N];
int l[N],r[N];
int stk[N],val[N],top;
int n,m,lg[N],st[N][20];
int rk[N],height[N],sa[N];
int x[N],y[N],c[N],a[N*10];

bool cmp(int x,int y){
    return rk[x]k) y[++num]=sa[i]-k;
        for(int i=1;i<=m;i++) c[i]=0;
        for(int i=1;i<=n;i++) c[x[i]]++;
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i;i--) sa[c[x[y[i]]]--]=y[i];
        swap(x,y);num=x[sa[1]]=1;
        for(int i=2;i<=n;i++) x[sa[i]]=y[sa[i]]==y[sa[i-1]] and y[sa[i]+k]==y[sa[i-1]+k]?num:++num;
        if(num==n) return;m=num;
    }
}

void gh(int k=0){
    for(int i=1;i<=n;i++) rk[sa[i]]=i;
    for(int i=1;i<=n;i++){
        if(rk[i]==1) continue;
        if(k) k--;
        int j=sa[rk[i]-1];
        while(i+k<=n and j+k<=n and s[i+k]==s[j+k]) k++;
        height[rk[i]]=k;
    }
}

void gt(){
    for(int i=2;i<=n;i++) lg[i]=lg[i-1]+((1<y) swap(x,y);x++;
    int k=lg[y-x+1];
    return min(st[x][k],st[y-(1<=val[i]) r[stk[top--]]=i;
            stk[++top]=i;
        } while(top) r[stk[top--]]=len;
        for(int i=len-1;i;i--){
            while(top and val[stk[top]]>val[i]) l[stk[top--]]=i;
            stk[++top]=i;
        } while(top) l[stk[top--]]=0;
        for(int i=1;i