bzoj 4199: [Noi2015]品酒大会

.

题意：给出一个字符串，每个位置有权值，问对于每个$0\le i\lt n$问有多少对位置往后$i$位是相同的，并且求每对权值乘积的最大值
题解：SAM+线段树（+树状数组）
把原串翻转，这样SAM里每个节点表示的就是从某个节点开始的字串了。找所有满足$min\le i\le max$的节点，这些节点就可以对$i$的第一问贡献$pnum\times (pnum-1)$，第二问贡献$\max \lbrace posmx1\times posmx2, posmn\times negmx, negmn1\times negmn2 \rbrace$的答案，其中$pos$、$neg$表示正负，$mx$、$mn$表示最大、最小，$1$、$2$表示第一、第二大/小。遍历每个节点，更新$min$到$max$的答案，可以用线段树（+树状数组）维护。
代码：

#include <bits/stdc++.h>
using namespace std;

long long n, a[300010];
char s[300010];
const long long inf=0x3f3f3f3f3f3f3f3fLL;
struct SAM
{
    struct node
    {
        int max, pnum;
        long long posmx1, posmx2, posmn, negmx, negmn1, negmn2;
        node *ch[26], *next;
        node(int max = 0) : max(max), pnum(1), ch(), next(NULL), posmx1(-1), posmx2(-1), posmn(-1), negmx(1), negmn1(1), negmn2(1) {}
        inline int min()
        {
            return next->max + 1;
        }
        long long get()
        {
            long long a=(posmx1!=-1&&posmx2!=-1)?posmx1*posmx2:-inf;
            long long b=(posmn!=-1&&negmx!=1)?posmn*negmx:-inf;
            long long c=(negmn1!=1&&negmn2!=1)?negmn1*negmn2:-inf;
            return std::max(std::max(a,b),c);
        }
    } * start, *last, pool[600010], *now;
    vector<node *> a;
    void init()
    {
        now = pool;
        start = last = new (now++) node;
    }
    void extend(int c, long long a)
    {
        node *u = new (now++) node(last->max + 1), *v = last;
        if(a>0)
        u->posmx1=u->posmn=a;
        else
        u->negmx=u->negmn1=a;
        while (v && !v->ch[c])
        {
            v->ch[c] = u;
            v = v->next;
        }
        if (!v)
            u->next = start;
        else if(v->ch[c]->max == v->max + 1)
            u->next = v->ch[c];
        else
        {
            node *n = new (now++) node(v->max + 1), *o = v->ch[c];
            n->pnum = 0;
            copy(o->ch, o->ch + 26, n->ch);
            n->next = o->next;
            u->next = o->next = n;
            while(v && v->ch[c] == o)
            {
                v->ch[c] = n;
                v = v->next;
            }
        }
        last = u;
    }
    void geta()
    {
        static int hh[300010];
        memset(hh, 0, sizeof(hh));
        int mx = 0;
        for(node *p = pool; p != now; p++)
        {
            mx=max(mx,p->max);
            hh[p->max]++;
        }
        a.resize(now - pool);
        for(int i = 1; i <= mx; i++)
        hh[i] += hh[i-1];
        for(node *p = pool; p != now; p++)
            a[--hh[p->max]] = p;
    }
    void getpnum()
    {
        geta();
        for(int i = a.size()-1; i > 0; i--)
        {
            node *x=a[i], *y=a[i]->next;
            y->pnum+=x->pnum;
            vector<long long>hh;
            hh.push_back(x->posmx1);
            hh.push_back(x->posmx2);
            hh.push_back(y->posmx1);
            hh.push_back(y->posmx2);
            sort(hh.begin(),hh.end());
            y->posmx1=hh[3];
            y->posmx2=hh[2];
            hh.clear();
            if(y->posmn == -1 || x->posmn == -1)
            y->posmn = max(y->posmn, x->posmn);
            else
            y->posmn = min(y->posmn, x->posmn);
            hh.push_back(x->negmn1);
            hh.push_back(x->negmn2);
            hh.push_back(y->negmn1);
            hh.push_back(y->negmn2);
            sort(hh.begin(),hh.end());
            y->negmn1=hh[0];
            y->negmn2=hh[1];
            if(y->negmx == 1 || x->negmx == 1)
            y->negmx = min(y->negmx, x->negmx);
            else
            y->negmx = max(y->negmx, x->negmx);
        }
    }
}sam;
struct BIT
{
    long long s[300010];
    BIT()
    {
        memset(s,0,sizeof(s));
    }
    int lb(int x)
    {
        return x & -x;
    }
    void add(int x, long long y)
    {
        for(long long i = x; i <= n; i += lb(i))
            s[i] += y;
    }
    long long get(int x)
    {
        long long ans = 0;
        for(int i = x; i; i -= lb(i))
            ans += s[i];
        return ans;
    }
}bit;
struct segment_tree
{
    long long a[1000010],m;
    segment_tree()
    {
        memset(a,-63,sizeof(a));
    }
    void getm()
    {
        m=1;
        while(m<n+2)
        m<<=1;
    }
    void chg(int l, int r, long long x)
    {
        l--;
        r++;
        l+=m;
        r+=m;
        while(l^r^1)
        {
            if(~l&1)
            a[l^1]=max(a[l^1],x);
            if(r&1)
            a[r^1]=max(a[r^1],x);
            l>>=1;
            r>>=1;
        }
    }
    long long get(int x)
    {
        x+=m;
        long long ans=-inf;
        while(x)
        {
            ans=max(ans,a[x]);
            x>>=1;
        }
        return ans;
    }
}seg;

int main()
{
    scanf("%lld%s", &n, s + 1);
    for(int i = 1; i <= n; i++)
        scanf("%lld",&a[i]);
    reverse(s+1, s+1+n);
    reverse(a+1, a+1+n);
    sam.init();
    seg.getm();
    for(int i = 1; i <= n; i++)
        sam.extend(s[i]-'a', a[i]);
    sam.getpnum();
    for(int i = 1; i < sam.a.size(); i++)
    {
        long long hh = (long long)sam.a[i]->pnum * (sam.a[i]->pnum - 1);
        bit.add(sam.a[i]->min(), hh);
        bit.add(sam.a[i]->max+1,-hh);
        seg.chg(sam.a[i]->min(), sam.a[i]->max, sam.a[i]->get());
    }
    if(n>1)
    printf("%lld %lld\n", n * (n-1) / 2, sam.start->get());
    else
    puts("0 0");
    for(int i = 1; i < n; i++)
    {
        long long a=bit.get(i)/2,b=seg.get(i);
        if(a==0)
        puts("0 0");
        else
        printf("%lld %lld\n",a,b);
    }
}