HDU - 6988 Display Substring

传送门：HDU - 6988

思路分析

求第$\text{k}$小，反过来求第$\text{k}$大

二分答案$x$，计算有多少个子串的权值$\geq x$，每个子串，一定是某个后缀的前缀，通过前缀和+双指针可以在$O(n)$的时间复杂度内计算出来，但是子串可能会重复，需要用一种后缀数据结构来去重。

后缀数组：记录每个$\text{i}$往后延伸$\text{len}$开始满足权值$\geq x$，利用$\text{height}$数组，对于排名挨着的两个后缀$\text{x}$和$\text{y}$，可以发现，重复计算的部分，就是$[len,lcp]$这之间的串，减去这部分就可以了。

总的时间复杂度为$O(nlogn)$

AC代码

#include <bits/stdc++.h>
#define V vector
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) (x)&(-x)
#define sz(x) (int)(x).size()
#define each(x,a) for(auto& x:a)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define mcp(a,b) memcpy(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const int N = 1e6+10;

struct Suf_Array {
    int h[N], rk[N], sa[N], y[N], c[N];
    void build(char *str,int n, int m) {
        for (int i = 0; i <= m; i ++) c[i] = 0;
        for (int i = 1; i <= n; i ++) c[rk[i] = (str[i]-'a'+1)] ++;
        for (int i = 1; i <= m; i ++) c[i] += c[i - 1];
        for (int i = n; i >= 1; i --) sa[c[rk[i]]--] = i;
        for (int k = 1; k <= n; k <<= 1) {
            int p = 0;
            for (int i = n - k + 1; i <= n; i ++) y[++p] = i;
            for (int i = 1; i <= n; i ++) if (sa[i] > k) y[++p] = sa[i] - k;
            for (int i = 0; i <= m; i ++) c[i] = 0;
            for (int i = 1; i <= n; i ++) c[rk[i]]++;
            for (int i = 1; i <= m; i ++) c[i] += c[i - 1];
            for (int i = n; i >= 1; i --) sa[c[rk[y[i]]]--] = y[i];
            swap(rk, y);
            rk[sa[1]] = p = 1;
            for (int i = 2; i <= n; i ++)
                rk[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);
            if (p >= n) break;
            m = p;
        }
        for (int i = 1, k = 0; i <= n; i ++) {
            if (k) -- k;
            int j = sa[rk[i] - 1];
            while (str[i + k] == str[j + k]) k ++;
            h[rk[i]] = k;
        }
    }
} SA;

char s[N];
int w[N],sum[N],n,vis[N];
ll k;

int get(int l,int r) {
    if(l>r) return -INF;
    return sum[r]-sum[l-1];
}

ll check(int mid){
    ll ans = 0;
    int j=1;
    for(int i=1;i<=n;i++) vis[i] = 0;
    for(int i=1;i<=n;i++){
        while(j+1<=n && get(i,j)<mid) ++j;
        if(get(i,j)>=mid){
            ans+=n-j+1;
            vis[SA.rk[i]] = j-i+1;
        }
    }
    for(int i=1;i<=n;i++){
        int lcp = SA.h[i];
        int s1 = vis[i-1];
        int s2 = vis[i];
        if(s1 == s2 && s1<=lcp && lcp && s1) ans-=lcp-s1+1;
    }
    return ans;
}

signed main() {

#ifdef xiaofan
    clock_t stTime = clock();
    freopen("1004.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
/*==========================begin============================*/
    IOS;
    int T;
    cin>>T;
    while(T--){
        cin>>n>>k;
        cin>>s+1;
        for(int i=0;i<26;i++) cin>>w[i];
        SA.build(s,n,30);
        for(int i=1;i<=n;i++) sum[i] = sum[i-1]+w[s[i]-'a'];
        int l=1,r = INF;
        ll tot = check(0);
        k = (tot-k+1);
        if(k<=0){
            cout<<-1<<endl;
            continue;
        }
        int ans = -1;
        while(r>=l){
            int mid = (l+r)/2;
            if(check(mid)>=k){
                ans = mid;
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        cout<<ans<<"\n";
    
    }



/*===========================end=============================*/
#ifdef xiaofan
    cerr << "Time Used:" << clock() - stTime << "ms" <<endl;
#endif
    return 0;
}