洛谷 7279 光棱碎片

发表于 | 分类于 | 7

首先将限制转化为 ≤R 。
建出反串的后缀树，执行静态链分治（即树上启发式合并）。
设当前结点包含字符串的最长长度为 len，则考虑子树内的后缀 i,j 的贡献。
显然是 min(R−(ai⊕aj),len)。

考虑分类讨论。
若 ai⊕aj≤R−len，需要这部分的数对的个数。
若 R−len<ai⊕aj≤R，需要这部分的数对的 ai⊕aj 之和以及个数。

则问题变为维护一个多重集 S，支持对于 i∈S，查询满足 i⊕v≤R 的 i 的个数以及 i⊕v 的和。
可以考虑使用 Trie 来维护，查询时在 Trie 上走 v⊕R 的路径，当某个时刻 R 的当前位为 1，则意味着若走向另一个儿子，异或值的这一位会变为 0，故将答案加上另一个儿子子树内的贡献即可。
当然，还要加上 v⊕R 本身的贡献。
而同时要查询和，可以套路地维护每一位 1 的个数来支持查询。

时间复杂度 O(nlognlog2ai)。
因为这是一棵后缀树，可以相信良心出题人没有卡树剖，所以是可以过的。

当然，在 SA 的 height 数组上并查集启发式合并或所谓「启发式分裂」并使用可持久化 Trie 也是可以的。
实际上这两种做法都相当于在 height 数组的笛卡尔树上做静态链分治，而 height 数组的笛卡尔树和后缀树某种意义上是等价的。

代码： 

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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int LG = 16;
const int mod = 998244353;
int n,L,R,w[N + 5];
char s[N + 5];
int ans;
namespace TRIE
{
    struct node
    {
        int ch[2];
        int cnt,sum[LG + 5];
    } tr[(N << 5) + 5];
    int tot = 1;
    inline void insert(int v,int d)
    {
        int p = 1;
        tr[p].cnt += d;
        for(register int k = 0;k <= LG;++k)
            tr[p].sum[k] += ((v >> k) & 1) * d;
        for(register int i = LG;~i;--i)
        {
            !(tr[p].ch[(v >> i) & 1]) && (tr[p].ch[(v >> i) & 1] = ++tot),
            p = tr[p].ch[(v >> i) & 1];
            tr[p].cnt += d;
            for(register int k = 0;k <= LG;++k)
                tr[p].sum[k] += ((v >> k) & 1) * d;
        }
    }
    inline pair<int,int> query(int v,int r)
    {
        if(r < 0)
            return make_pair(0,0);
        int p = 1;
        int cnt = 0,sum = 0;
        for(register int i = LG;~i && p;--i)
        {
            if((r >> i) & 1)
            {
                cnt += tr[tr[p].ch[(((v ^ r) >> i) & 1) ^ 1]].cnt;
                for(register int k = 0;k <= LG;++k)
                    if((v >> k) & 1)
                        sum = (sum + (tr[tr[p].ch[(((v ^ r) >> i) & 1) ^ 1]].cnt - tr[tr[p].ch[(((v ^ r) >> i) & 1) ^ 1]].sum[k]) * (1LL << k)) % mod;
                    else
                        sum = (sum + tr[tr[p].ch[(((v ^ r) >> i) & 1) ^ 1]].sum[k] * (1LL << k)) % mod;
            }
            p = tr[p].ch[((v ^ r) >> i) & 1];
        }
        cnt += tr[p].cnt;
        for(register int k = 0;k <= LG;++k)
            if((v >> k) & 1)
                sum = (sum + (tr[p].cnt - tr[p].sum[k]) * (1LL << k)) % mod;
            else
                sum = (sum + tr[p].sum[k] * (1LL << k)) % mod;
        return make_pair(cnt,sum);
    }
}
namespace SAM
{
    struct node
    {
        int ch[26];
        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];
    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[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[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        ++sz[las = p],edp[las].push_back(pos);
    }
    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[a[i]] > sz[son[sam[a[i]].fa]])
                son[sam[a[i]].fa] = a[i];
        }
    }
    void dfs(int p)
    {
        int len = sam[p].len;
        pair<int,int> res1,res2;
        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)
                    TRIE::insert(w[*it],-1);
            }
        if(son[p])
            dfs(son[p]);
        for(register vector<int>::iterator it = edp[p].begin();it != edp[p].end();++it)
            res1 = TRIE::query(w[*it],R - len),
            res2 = TRIE::query(w[*it],R),
            ans = (ans + (long long)res1.first * len) % mod,
            ans = (ans + (long long)(res2.first - res1.first) * R % mod - (res2.second - res1.second + mod) % mod + mod) % mod,
            res1 = TRIE::query(w[*it],L - 1 - len),
            res2 = TRIE::query(w[*it],L - 1),
            ans = (ans - (long long)res1.first * len % mod + mod) % mod,
            ans = (ans - (long long)(res2.first - res1.first) * (L - 1) % mod + (res2.second - res1.second + mod) % mod + mod) % mod;
        for(register vector<int>::iterator it = edp[p].begin();it != edp[p].end();++it)
            TRIE::insert(w[*it],1);
        if(son[p])
        {
            edp[p].swap(edp[son[p]]);
            for(register vector<int>::iterator it = edp[son[p]].begin();it != edp[son[p]].end();++it)
                edp[p].push_back(*it);
            vector<int>().swap(edp[son[p]]);
        }
        for(register int i = first[p];i;i = pre[i])
            if(to[i] ^ son[p])
            {
                for(register vector<int>::iterator it = edp[to[i]].begin();it != edp[to[i]].end();++it)
                    res1 = TRIE::query(w[*it],R - len),
                    res2 = TRIE::query(w[*it],R),
                    ans = (ans + (long long)res1.first * len) % mod,
                    ans = (ans + (long long)(res2.first - res1.first) * R % mod - (res2.second - res1.second + mod) % mod + mod) % mod,
                    res1 = TRIE::query(w[*it],L - 1 - len),
                    res2 = TRIE::query(w[*it],L - 1),
                    ans = (ans - (long long)res1.first * len % mod + mod) % mod,
                    ans = (ans - (long long)(res2.first - res1.first) * (L - 1) % mod + (res2.second - res1.second + mod) % mod + mod) % mod;
                for(register vector<int>::iterator it = edp[to[i]].begin();it != edp[to[i]].end();++it)
                    edp[p].push_back(*it),TRIE::insert(w[*it],1);
                vector<int>().swap(edp[to[i]]);
            }
    }
}
int main()
{
    scanf("%d%s",&n,s + 1);
    for(register int i = 1;i <= n;++i)
        scanf("%d",w + i);
    scanf("%d%d",&L,&R);
    for(register int i = 1;i <= n;++i)
        SAM::insert(s[i] - 'a',i);
    SAM::build(),SAM::dfs(1);
    printf("%d\n",ans);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment