洛谷P2178 [NOI2015]品酒大会(后缀自动机 线段树)

题意

题目链接

sol

说一个后缀自动机+线段树的无脑做法

首先建出sam，然后对parent树进行dp，维护最大次大值，最小次小值

显然一个串能更新答案的区间是\([len_{fa_{x}} + 1, len_x]\)，方案数就相当于是从\(siz_x\)里面选两个，也就是\(\frac{siz_x (siz_x - 1)}{2}\)

直接拿线段树维护一下，标记永久化一下炒鸡好写~

#include<bits/stdc++.h>
#define int long long 
#define ll long long 
using namespace std;
const int maxn = 1e6 + 10;
const ll inf = 2e18 + 10;
template <typename a, typename b> inline bool chmin(a &a, b b){if(a > b) {a = b; return 1;} return 0;}
template <typename a, typename b> inline bool chmax(a &a, b b){if(a < b) {a = b; return 1;} return 0;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, a[maxn];
char s[maxn];
int root = 1, tot = 1, las = 1, ch[maxn][26], fa[maxn], len[maxn], rev[maxn];
ll mx[maxn], mx2[maxn], ans[maxn], ans1[maxn], mn[maxn], mn2[maxn], tmp[maxn], siz[maxn];
vector<int> v[maxn];
void insert(int x, int id) {
    int now = ++tot, pre = las; las = now; siz[now] = 1; len[now] = len[pre] + 1; mx[now] = a[id]; mx2[now] = -inf; mn[now] = a[id]; mn2[now] = inf; rev[id] = now;
    for(; pre && !ch[pre][x]; pre = fa[pre]) ch[pre][x] = now;
    if(!pre) {fa[now] = root; return ;}
    int q = ch[pre][x];
    if(len[pre] + 1 == len[q]) fa[now] = q;
    else {
        int nq = ++tot; fa[nq] = fa[q]; len[nq] = len[pre] + 1; 
        memcpy(ch[nq], ch[q], sizeof(ch[q]));
        fa[now] = fa[q] = nq;
        for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nq;
    }
}
void builddag() {
    for(int i = 1; i <= tot; i++) assert(fa[i] != i), v[fa[i]].push_back(i);
}

int rt, node, ls[maxn], rs[maxn], ad[maxn], si[maxn];
ll sum[maxn], tag[maxn];
void build(int &k, int l, int r) {
    if(!k) k = ++node, tag[k] = -inf, si[k] = r - l + 1;
    if(l == r) return ;
    int mid = l + r >> 1;
    build(ls[k], l, mid);
    build(rs[k], mid + 1, r);
}
void intmax(int k, int l, int r, int ql, int qr, ll v) {
    if(ql <= l && r <= qr) {chmax(tag[k], v); return ;  }
    int mid = l + r >> 1;
    if(ql <= mid) intmax(ls[k], l, mid, ql, qr, v);
    if(qr  > mid) intmax(rs[k], mid + 1, r, ql, qr, v);
}
void intadd(int k, int l, int r, int ql, int qr, ll v) {
    if(ql <= l && r <= qr) {sum[k] += v; return ;}
    int mid = l + r >> 1;
    if(ql <= mid) intadd(ls[k], l, mid, ql, qr, v);
    if(qr  > mid) intadd(rs[k], mid + 1, r, ql, qr, v);
}
ll querynum(int k, int l, int r, int pos) {
    if(!k) return 0;
    ll now = sum[k];
    if(l == r || !k) return now;
    int mid = l + r >> 1;
    if(pos <= mid) now += querynum(ls[k], l, mid, pos);
    else now += querynum(rs[k], mid + 1, r, pos);
    return now;
}
ll querymax(int k, int l, int r, int pos) {
    if(!k) return -inf;
    ll now = tag[k];
    if(l == r || !k) return now;
    int mid = l + r >> 1;
    if(pos <= mid) chmax(now, querymax(ls[k], l, mid, pos));
    else chmax(now, querymax(rs[k], mid + 1, r, pos));
    return now;
}
void dfs(int x) {
    for(auto &to : v[x]) {
        dfs(to);
        siz[x] += siz[to];
        if(mx2[to] > mx[x]) chmax(mx2[x], mx[x]), mx[x] = mx2[to];
        else chmax(mx2[x], mx2[to]);
        if(mx[to] > mx[x]) chmax(mx2[x], mx[x]), mx[x] = mx[to];
        else chmax(mx2[x], mx[to]);
        
        if(mn2[to] < mn[x]) chmin(mn2[x], mn[x]), mn[x] = mn2[to];
        else chmin(mn2[x], mn2[to]);
        if(mn[to] < mn[x]) chmin(mn2[x], mn[x]), mn[x] = mn[to];
        else chmin(mn2[x], mn[to]); 
    }
    if(siz[x] > 1 && x != root) {
        intmax(rt, 1, n, len[fa[x]] + 1, len[x], mx[x] * mx2[x]);
        intmax(rt, 1, n, len[fa[x]] + 1, len[x], mn[x] * mn2[x]);
        
        intadd(rt, 1, n, len[fa[x]] + 1, len[x], 1ll * siz[x] * (siz[x] - 1) / 2);
    }
}

signed main() {
    n = read();
    build(rt, 1, n);
    scanf("%s", s + 1);
    reverse(s + 1, s + n + 1);
    for(int i = 1; i <= n; i++) tmp[i] = a[i] = read(), assert(a[i] != 0);
    reverse(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) insert(s[i] - 'a', i);
    for(int i = 1; i <= tot; i++) {
        ans[i] = -inf;
        if(!mx[i]) mx[i] = -inf;
        if(!mx2[i]) mx2[i] = -inf;
        if(!mn[i]) mn[i] = inf;
        if(!mn2[i]) mn2[i] = inf;   
    }
    builddag();
    dfs(1);
    for(int i = 1; i < n; i++) {
        ans1[i] = querynum(root, 1, n, i);
        ans[i] = querymax(root, 1, n, i);
        
    }
    sort(tmp + 1, tmp + n + 1, greater<int>());
    cout << 1ll * n * (n - 1) / 2 << " " << max(tmp[1] * tmp[2], tmp[n] * tmp[n - 1]) << '\n';
    for(int i = 1; i < n; i++) cout << ans1[i] <<  " " << (ans[i] <= -inf ? 0 : ans[i]) << '\n';
    return 0;
}
/*
2
aa
-100000000 100000000
12
abaabaabaaba
1 -2 3 -4 5 -6 7 -8 9 -10 11 -12
*/