ybw051114
所有文章 标签 分类 文档 关于 热力图
ybw051114

目录

P4036-[JSOI2008]火星人

   约 1825 字   预计阅读 4 分钟    次阅读  

P4036-[JSOI2008]火星人

题目:

题目描述:

火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。

比方说，有这样一个字符串：madamimadam，我们将这个字符串的各个字符予以标号：

1
2

序号 1 2 3 4 5 6 7 8 9 10 11 
字符 m a d a m i m a d a m

现在，火星人定义了一个函数 $LCQ(x, y)$，表示：该字符串中第 $x$ 个字符开始的字串，与该字符串中第 $y$ 个字符开始的字串，两个字串的公共前缀的长度。比方说，$LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0$

在研究 $LCQ$ 函数的过程中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出 $LCQ$ 函数的值；同样，如果求出了 $LCQ$ 函数的值，也可以很快地将该字符串的后缀排好序。

尽管火星人聪明地找到了求取 $LCQ$ 函数的快速算法，但不甘心认输的地球人又给火星人出了个难题：在求取 $LCQ$ 函数的同时，还可以改变字符串本身。具体地说，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此复杂的问题中，火星人是否还能够做到很快地求取 $LCQ$ 函数的值。

输入格式:

第一行给出初始的字符串。第二行是一个非负整数 $M$ ，表示操作的个数。接下来的M行，每行描述一个操作。操作有 $3$ 种，如下所示

  1. 询问。语法：$Q$ $x$ $y$ ，$x$ ,$y$ 均为正整数。功能：计算 $LCQ(x,y)$ 限制：$1$ $\leq$ $x$ , $y$ $\leq$ 当前字符串长度 。
  2. 修改。语法：$R$ $x$ $d$，$x$ 是正整数，$d$ 是字符。功能：将字符串中第 $x$ 个数修改为字符 $d$ 。限制：$x$ 不超过当前字符串长度。
  3. 插入：语法：$I$ $x$ $d$ ，$x$ 是非负整数，$d$ 是字符。功能：在字符串第 $x$ 个字符之后插入字符 $d$ ，如果 $x=0$，则在字符串开头插入。限制：$x$ 不超过当前字符串长度

输出格式:

对于输入文件中每一个询问操作，你都应该输出对应的答案。一个答案一行。

样例:

样例输入1:

1
2
3
4
5
6
7
8
9

madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

样例输出1:

1
2
3
4
5

5
1
0
2
1

思路:

实现:

  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
196
197
198
199
200
201
202
203
204
205
206
207
208
209

// Problem: P4036 [JSOI2008]火星人
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4036
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/ios.h"

namespace IO
{
const int S = (1 << 20) + 5;
char buf[S], *H, *T;
inline char Get()
{
    if (H == T)
        T = (H = buf) + fread(buf, 1, S, stdin);
    if (H == T)
        return -1;
    return *H++;
}
inline int read()
{
    int x = 0;
    char c = Get();
    while (!isdigit(c))
        c = Get();
    while (isdigit(c))
        x = x * 10 + c - '0', c = Get();
    return x;
}
inline char readc()
{
    char c = Get();
    while ((c < 'A' || c > 'Z') && (c < 'a' || c > 'z'))
        c = Get();
    return c;
}
char obuf[S], *oS = obuf, *oT = oS + S - 1, c, qu[55];
int qr;
inline void flush()
{
    fwrite(obuf, 1, oS - obuf, stdout);
    oS = obuf;
}
inline void putc(char x)
{
    *oS++ = x;
    if (oS == oT)
        flush();
}
template <class I>
inline void print(I x)
{
    if (!x)
        putc('0');
    while (x)
        qu[++qr] = x % 10 + '0', x /= 10;
    while (qr)
        putc(qu[qr--]);
    putc('\n');
}
} // namespace IO

using namespace IO;
typedef unsigned long long ull;
const int N = 150010;
const double alpha = 0.75;
int lc[N], rc[N], sz[N], tot = 0, rt = 0;
ull val[N], sum[N], pw[N];
vector<int> A;

bool isbad(int o) { return sz[lc[o]] > alpha * sz[o] + 5 || sz[rc[o]] > alpha * sz[o] + 5; }
void maintain(int o)
{
    sum[o] = sum[rc[o]] + val[o] * pw[sz[rc[o]]] + sum[lc[o]] * pw[sz[rc[o]] + 1];
    sz[o] = sz[lc[o]] + sz[rc[o]] + 1;
}

void flatten(int o)
{
    if (!o)
        return;
    flatten(lc[o]);
    A.push_back(o);
    flatten(rc[o]);
}

void rebuild(int &o, int l, int r)
{
    int mid = (l + r) / 2;
    o = A[mid - 1];
    lc[o] = rc[o] = 0;
    if (l < mid)
        rebuild(lc[o], l, mid - 1);
    if (r > mid)
        rebuild(rc[o], mid + 1, r);
    maintain(o);
}

void insert(int &o, int k, int x)
{
    if (!o)
    {
        o = ++tot;
        lc[o] = rc[o] = 0;
        val[o] = sum[o] = x;
        sz[o] = 1;
        return;
    }
    if (isbad(o))
    {
        A.clear();
        flatten(o);
        rebuild(o, 1, A.size());
    }
    int szl = sz[lc[o]];
    if (k <= szl)
        insert(lc[o], k, x);
    else
        insert(rc[o], k - szl - 1, x);
    maintain(o);
}

void modify(int o, int k, int x)
{
    int szl = sz[lc[o]];
    if (k == szl + 1)
        val[o] = x;
    else if (k <= szl)
        modify(lc[o], k, x);
    else
        modify(rc[o], k - szl - 1, x);
    maintain(o);
}

ull find(int o, int l, int r, int nl, int nr)
{
    if (l == nl && r == nr)
        return sum[o];
    int szl = sz[lc[o]];
    ull res = 0;
    if (nr < l + szl)
        return find(lc[o], l, l + szl - 1, nl, nr);
    if (nl > l + szl)
        return find(rc[o], l + szl + 1, r, nl, nr);
    if (nl < l + szl)
        res = find(lc[o], l, l + szl - 1, nl, l + szl - 1);
    if (nl <= l + szl && nr >= l + szl)
        res = res * pw[1] + val[o];
    if (nr > l + szl)
        res = res * pw[nr - l - szl] + find(rc[o], l + szl + 1, r, l + szl + 1, nr);
    return res;
}

int lcp(int x, int y)
{
    int res = 0;
    for (int i = 17; i >= 0; i--)
    {
        if (x + (1 << i) - 1 > tot)
            continue;
        if (y + (1 << i) - 1 > tot)
            continue;
        ull s1 = find(rt, 1, tot, x, x + (1 << i) - 1);
        ull s2 = find(rt, 1, tot, y, y + (1 << i) - 1);
        if (s1 != s2)
            continue;
        res |= 1 << i;
        x += 1 << i;
        y += 1 << i;
    }
    return res;
}

int main()
{
    pw[0] = 1;
    for (int i = 1; i < N; i++)
        pw[i] = pw[i - 1] * 131;
    static char ss[N];
    scanf("%s", ss + 1);
    tot = strlen(ss + 1);
    for (int i = 1; i <= tot; i++)
        A.push_back(i), val[i] = ss[i] - 'a' + 1;
    rebuild(rt, 1, tot);
    for (int m = read(); m; m--)
    {
        char opt = readc();
        if (opt == 'I')
        {
            int x = read();
            char d = readc();
            insert(rt, x, d - 'a' + 1);
        }
        if (opt == 'R')
        {
            int x = read();
            char d = readc();
            modify(rt, x, d - 'a' + 1);
        }
        if (opt == 'Q')
            print(lcp(read(), read()));
    }
    flush();
    return 0;
}
更新于 2025-05-14  5842a98
阅读原始文档
 字符串, 2008, 各省省选, 平衡树, 江苏, , Notebooks/OI/OJ/Luogu
返回 | 主页