洛谷 5161 WD 与数列

发表于 | 分类于 | 12

首先差分，问题转化为求一个字符串中有多少对本质相同且不相交不相邻的子串（与 (n2) 的和）。

对于前缀 i,j (i>j)，考虑统计它们的所有公共后缀的贡献。
设 l 为后缀长度，len 为 i,j 的最长公共后缀长度（即 Parent Tree 上的 LCA 包含子串的最长长度）。
则有 j+1<i−l+1，即 l<i−j。
而又有 l≤len。
故 i,j 的贡献应为 min(i−j−1,len)。

考虑静态链分治确定 LCA，那么考虑对于子树内的前缀 i，计算所有与它不在同一棵子树内的 j 的贡献：

  1. 若 i−len≤j<i，其贡献为 i−j−1；
  2. 若 j<i−len，其贡献为 len；
  3. 若 i<j≤i+len，其贡献为 j−i−1；
  4. 若 j>i+len，其贡献为 len。

于是链分治时对 endpos 维护一棵线段树和一个 vector 即可。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <cstdio>
#include <vector>
#include <utility>
#include <unordered_map>
using namespace std;
const int N = 3e5;
int n,a[N + 5];
long long ans;
namespace SEG
{
    struct node
    {
        long long sum;
        int cnt;
        int ls,rs;
    } seg[(N << 5) + 5];
    void insert(int x,int &p,int tl,int tr)
    {
        static int tot = 0;
        !p && (p = ++tot),seg[p].sum += x,++seg[p].cnt;
        if(tl == tr)
            return ;
        int mid = tl + tr >> 1;
        x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
    }
    int merge(int p,int q)
    {
        if(!p || !q)
            return p | q;
        seg[p].sum += seg[q].sum,seg[p].cnt += seg[q].cnt,
        seg[p].ls = merge(seg[p].ls,seg[q].ls),
        seg[p].rs = merge(seg[p].rs,seg[q].rs);
        return p;
    }
    inline pair<long long,int> operator+(const pair<long long,int> &x,const pair<long long,int> &y)
    {
        return make_pair(x.first + y.first,x.second + y.second);
    }
    pair<long long,int> query(int l,int r,int p,int tl,int tr)
    {
        if(l > r || r < tl || l > tr)
            return make_pair(0,0);
        if(!p || (l <= tl && tr <= r))
            return make_pair(seg[p].sum,seg[p].cnt);
        int mid = tl + tr >> 1;
        pair<long long,int> ret(0,0);
        l <= mid && (ret = ret + query(l,r,seg[p].ls,tl,mid),1);
        r > mid && (ret = ret + query(l,r,seg[p].rs,mid + 1,tr),1);
        return ret;
    }
}
namespace SAM
{
    struct node
    {
        unordered_map<int,int> ch;
        int fa,len;
    } sam[(N << 1) + 5];
    int las = 1,tot = 1;
    int c[N + 5],a[(N << 1) + 5];
    int sz[(N << 1) + 5],son[(N << 1) + 5],rt[(N << 1) + 5];
    vector<int> edp[(N << 1) + 5];
    inline void insert(int x,int pos)
    {
        int cur = las,p = ++tot;
        sam[p].len = sam[cur].len + 1;
        for(;cur && !sam[cur].ch.count(x);cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
                for(;cur && sam[cur].ch.count(x) && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        ++sz[las = p],edp[las].push_back(pos),SEG::insert(pos,rt[las],1,n);
    }
    int to[(N << 1) + 5],pre[(N << 1) + 5],first[(N << 1) + 5];
    inline void add(int u,int v)
    {
        static int tot = 0;
        to[++tot] = v,pre[tot] = first[u],first[u] = tot;
    }
    inline void build()
    {
        for(register int i = 1;i <= tot;++i)
            ++c[sam[i].len],i > 1 && (add(sam[i].fa,i),1);
        for(register int i = 1;i <= n;++i)
            c[i] += c[i - 1];
        for(register int i = tot;i > 1;--i)
            a[c[sam[i].len]--] = i;
        for(register int i = tot;i > 1;--i)
        {
            sz[sam[a[i]].fa] += sz[a[i]];
            if(!son[sam[a[i]].fa] || sz[son[sam[a[i]].fa]] < sz[a[i]])
                son[sam[a[i]].fa] = a[i];
        }
    }
    void dfs(int p)
    {
        int len = sam[p].len;
        pair<long long,int> s;
        if(son[p])
        {
            dfs(son[p]),edp[p].swap(edp[son[p]]),rt[p] = SEG::merge(rt[p],rt[son[p]]);
            for(register vector<int>::iterator it = edp[son[p]].begin();it != edp[son[p]].end();++it)
                edp[p].push_back(*it),
                s = SEG::query(*it - len,*it - 1,rt[p],1,n),ans += (long long)s.second * (*it - 1) - s.first,
                s = SEG::query(1,*it - len - 1,rt[p],1,n),ans += (long long)s.second * len,
                s = SEG::query(*it + 1,*it + len,rt[p],1,n),ans += s.first - (long long)s.second * (*it + 1),
                s = SEG::query(*it + len + 1,n,rt[p],1,n),ans += (long long)s.second * len;
            vector<int>().swap(edp[son[p]]);
        }
        for(register int i = first[p];i;i = pre[i])
            if(to[i] ^ son[p])
            {
                dfs(to[i]);
                for(register vector<int>::iterator it = edp[to[i]].begin();it != edp[to[i]].end();++it)
                    edp[p].push_back(*it),
                    s = SEG::query(*it - len,*it - 1,rt[p],1,n),ans += (long long)s.second * (*it - 1) - s.first,
                    s = SEG::query(1,*it - len - 1,rt[p],1,n),ans += (long long)s.second * len,
                    s = SEG::query(*it + 1,*it + len,rt[p],1,n),ans += s.first - (long long)s.second * (*it + 1),
                    s = SEG::query(*it + len + 1,n,rt[p],1,n),ans += (long long)s.second * len;
                vector<int>().swap(edp[to[i]]),rt[p] = SEG::merge(rt[p],rt[to[i]]);
            }
    }
}
int main()
{
    scanf("%d",&n),ans = (long long)n * (n - 1) / 2;
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i),i > 1 && (SAM::insert(a[i] - a[i - 1],i - 1),1);
    SAM::build(),SAM::dfs(1);
    printf("%lld\n",ans);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment