LibreOJ 3311 「ZJOI2020」字符串

发表于 | 分类于 | 21

咋这么难写啊（

先不管本质不同，考虑如何计算区间内平方串个数。
枚举一个 run r=(l,r,p)，枚举 len=2kp，其中 k∈N+，那么容易发现该区间内长度为 len 的平方串出现的位置是一条斜率为 1 的线段 (l,l+len−1)→(r−len+1,r)。

接下来考虑本质不同的条件，注意到本质相同的平方串长度一定相等（废话），故可以考虑将一个平方串的等价类中所有出现位置按顺序列出，设相邻两个为 [l0,r0],[l1,r1]，则考虑在 (l0,r1) 处作一个 −1 的贡献。
根据我们小学就学过的植树问题，容易发现这样每种等价类只会留下一次贡献。
考虑同一个 run 内的平方串，其删去的贡献显然仍构成一条线段。
然后在不同的 run 之间用哈希表维护出现位置即可。

考虑复杂度。同 run 内枚举的长度个数不会超过 σ(n)，故这部分贡献的线段的个数是 O(n) 的。
而一个 run 内本质不同的平方串的个数不超过本原平方串的个数，也即 O(nlogn)。
总共即 O(nlog2n)。

感觉写得好丑……不过能过就不管了（

代码： 

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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include <cmath>
#include <cstdio>
#include <cstring>
#include <utility>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 2e5;
int n,q;
char s[N + 5];
struct Hash
{
    int P,mod;
    int pw[N + 5],hs[N + 5];
    inline Hash(int a,int b)
    {
        P = a,mod = b;
    }
    inline void init()
    {
        pw[0] = 1;
        for(register int i = 1;i <= n;++i)
            pw[i] = (long long)pw[i - 1] * P % mod,
            hs[i] = ((long long)hs[i - 1] * P + s[i] - 'a' + 1) % mod;
    }
    inline int hash(int l,int r)
    {
        return (hs[r] - (long long)hs[l - 1] * pw[r - l + 1] % mod + mod) % mod;
    }
} h1(17,1e9 + 7),h2(17,1e9 + 9);
inline int LCP(int a,int b)
{
    int l = 1,r = min(n - a + 1,n - b + 1),mid,ret = 0;
    while(l <= r)
        mid = l + r >> 1,
        h1.hash(a,a + mid - 1) == h1.hash(b,b + mid - 1) && h2.hash(a,a + mid - 1) == h2.hash(b,b + mid - 1) ? (ret = mid,l = mid + 1) : (r = mid - 1);
    return ret;
}
inline int LCS(int a,int b)
{
    int l = 1,r = min(a,b),mid,ret = 0;
    while(l <= r)
        mid = l + r >> 1,
        h1.hash(a - mid + 1,a) == h1.hash(b - mid + 1,b) && h2.hash(a - mid + 1,a) == h2.hash(b - mid + 1,b) ? (ret = mid,l = mid + 1) : (r = mid - 1);
    return ret;
}
int ly[N + 5];
pair<int,int> st[N + 5];
int top;
inline void lyndon(int op)
{
    top = 0;
    for(register int i = n,j;i;--i)
    {
        j = i;
        for(register int lcp;top;--top)
        {
            lcp = LCP(i,st[top].first);
            if((s[i + lcp] >= s[st[top].first + lcp]) ^ op)
                break;
            j = st[top].second;
        }
        st[++top] = make_pair(i,ly[i] = j);
    }
}
struct Run
{
    int l,r,p;
    inline bool operator<(const Run &o) const
    {
        return l ^ o.l ? l < o.l : r < o.r;
    }
    inline bool operator==(const Run &o) const
    {
        return l == o.l && r == o.r;
    }
} runs[N * 2 + 5];
int tot;
namespace BIT
{
    #define lowbit(x) ((x) & -(x))
    int c[N + 5];
    long long s[N + 5];
    inline void clear()
    {
        memset(c,0,sizeof c),memset(s,0,sizeof s);
    }
    inline void update(int x,int k,int flag = 0)
    {
        for(register int i = x;i <= n;i += lowbit(i))
            c[i] += k,flag && (s[i] += (long long)k * x);
    }
    inline pair<int,long long> query(int x)
    {
        int cnt = 0;
        long long sum = 0;
        for(;x;x -= lowbit(x))
            cnt += c[x],sum += s[x];
        return make_pair(cnt,sum);
    }
}
long long ans[N + 5];
struct s_change
{
    int x,y,k;
} pnt[(N << 5) + 5],ray[(N << 5) + 5];
int pnt_tot,ray_tot;
struct s_query
{
    int x,y,id;
} qry[N * 2 + 5];
int qry_tot;
void calc_pnts()
{
    BIT::clear();
    sort(pnt + 1,pnt + pnt_tot + 1,[](const s_change &x,const s_change &y)
    {
        return x.x ^ y.x ? x.x < y.x : x.y < y.y;
    });
    sort(qry + 1,qry + qry_tot + 1,[](const s_query &x,const s_query &y)
    {
        return x.x ^ y.x ? x.x < y.x : x.y < y.y;
    });
    for(register int i = 1,j = 1;i <= qry_tot;++i)
    {
        for(;j <= pnt_tot && pnt[j].x <= qry[i].x;++j)
            BIT::update(pnt[j].y,pnt[j].k);
        ans[abs(qry[i].id)] += qry[i].id < 0 ? -BIT::query(qry[i].y).first : BIT::query(qry[i].y).first;
    }
}
void calc_rays(int flag = 0)
{
    BIT::clear();
    sort(ray + 1,ray + ray_tot + 1,[](const s_change &x,const s_change &y)
    {
        return x.x - x.y ^ y.x - y.y ? x.x - x.y > y.x - y.y : x.x < y.x;
    });
    sort(qry + 1,qry + qry_tot + 1,[](const s_query &x,const s_query &y)
    {
        return x.x - x.y ^ y.x - y.y ? x.x - x.y > y.x - y.y : x.x < y.x;
    });
    for(register int i = 1,j = 1;i <= qry_tot;++i)
    {
        for(;j <= ray_tot && ray[j].x - ray[j].y >= qry[i].x - qry[i].y + flag;++j)
            BIT::update(ray[j].x,ray[j].k,1);
        auto t = BIT::query(qry[i].x);
        long long v = (long long)t.first * (qry[i].x + 1) - t.second;
        ans[abs(qry[i].id)] += qry[i].id < 0 ? -v : v;
    }
}
unordered_map<int,unordered_map<int,int>> vis;
int main()
{
    scanf("%d%d%s",&n,&q,s + 1);
    h1.init(),h2.init();
    for(register int op = 0;op <= 1;++op)
    {
        lyndon(op);
        for(register int i = 1,lcp,lcs;i < n;++i)
            lcp = LCP(i,ly[i] + 1),lcs = LCS(i - 1,ly[i]),
            lcp + lcs >= ly[i] - i + 1 && (runs[++tot] = (Run){i - lcs,ly[i] + lcp,ly[i] - i + 1},1);
    }
    sort(runs + 1,runs + tot + 1),tot = unique(runs + 1,runs + tot + 1) - runs - 1;
    int l,r,p;
    for(register int i = 1;i <= q;++i)
        scanf("%d%d",&l,&r),qry[++qry_tot] = (s_query){n,r,i},qry[++qry_tot] = (s_query){l - 1,r,-i};
    for(register int i = 1;i <= tot;++i)
    {
        l = runs[i].l,r = runs[i].r,p = runs[i].p;
        for(register int len = 2 * p;l + len - 1 <= r;len += 2 * p)
        {
            ray[++ray_tot] = (s_change){l,l + len - 1,1},ray[++ray_tot] = (s_change){r - len + 2,r + 1,-1};
            if(l <= r - len - p + 1)
                ray[++ray_tot] = (s_change){l,l + len + p - 1,-1},ray[++ray_tot] = (s_change){r - len - p + 2,r + 1,1};
        }
        for(register int s = l,t,ha,hb;s < l + p;++s)
            for(register int len = 2 * p;s + len - 1 <= r;len += 2 * p)
            {
                t = s + ((r - s - len + 1) / p) * p,
                ha = h1.hash(s,s + len - 1),hb = h2.hash(s,s + len - 1);
                if(vis.count(ha) && vis[ha].count(hb))
                    pnt[++pnt_tot] = (s_change){vis[ha][hb],s + len - 1,-1};
                vis[ha][hb] = t;
            }
    }
    calc_pnts();
    calc_rays();
    for(register int i = 1;i <= ray_tot;++i)
        swap(ray[i].x,ray[i].y);
    for(register int i = 1;i <= qry_tot;++i)
        swap(qry[i].x,qry[i].y);
    calc_rays(1);
    for(register int i = 1;i <= q;++i)
        printf("%lld\n",ans[i]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment