QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #630863 | #9425. Generated String | yyyyxh | RE | 3ms | 40628kb | C++14 | 7.9kb | 2024-10-11 20:42:43 | 2024-10-11 20:42:51 |
Judging History
answer
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
int read() {
char c = getchar();
while (c < 48 || c > 57)
c = getchar();
int x = 0;
do
x = x * 10 + (c ^ 48), c = getchar();
while (c >= 48 && c <= 57);
return x;
}
const int N = 100003, T = 500003;
int n, q;
char s[N];
namespace SA {
int buc[N], rk[N], sa[N], od[N], id[N], ht[17][N], w, p;
bool eq(int x, int y) {
return od[x] == od[y] && od[x + w] == od[y + w];
}
void getSA(int m) {
for (int i = 1; i <= n; ++i)
++buc[rk[i] = s[i]];
for (int i = 1; i <= m; ++i)
buc[i] += buc[i - 1];
for (int i = n; i; --i)
sa[buc[rk[i]]--] = i;
for (int i = 1; i <= m; ++i)
buc[i] = 0;
w = 1;
p = 0;
while (true) {
for (int i = n; i > n - w; --i)
id[++p] = i;
for (int i = 1; i <= n; ++i)
if (sa[i] > w)
id[++p] = sa[i] - w;
for (int i = 1; i <= n; ++i)
++buc[od[i] = rk[i]];
for (int i = 1; i <= m; ++i)
buc[i] += buc[i - 1];
for (int i = n; i; --i)
sa[buc[rk[id[i]]]--] = id[i];
for (int i = 1; i <= m; ++i)
buc[i] = 0;
rk[sa[1]] = p = 1;
for (int i = 2; i <= n; ++i) {
if (!eq(sa[i], sa[i - 1]))
++p;
rk[sa[i]] = p;
}
if (p == n)
break;
w <<= 1, m = p, p = 0;
}
}
void getLCP() {
s[n + 1] = '!';
for (int i = 1, k = 0; i <= n; ++i) {
if (k)
--k;
if (rk[i] == 1)
continue;
while (s[i + k] == s[sa[rk[i] - 1] + k])
++k;
ht[0][rk[i]] = k;
}
for (int t = 1; t < 17; ++t)
for (int i = 2; i + (1 << t) - 1 <= n; ++i)
ht[t][i] = min(ht[t - 1][i], ht[t - 1][i + (1 << (t - 1))]);
}
int lcp(int x, int y) {
if (x == y)
return n - x + 1;
x = rk[x], y = rk[y];
if (x > y)
swap(x, y);
int k = __lg(y - x);
return min(ht[k][x + 1], ht[k][y - (1 << k) + 1]);
}
} // namespace SA
vpii v1[N], v2[N];
int id1[N], lef1[N], rig1[N], num1;
int id2[N], lef2[N], rig2[N], num2;
int del[N], res[N];
char op[N];
int cnt;
vi bel[T], sn[T];
void build(vi, int);
void split(vi vec, int fa) {
if (vec.empty())
return;
vector<int> vc[26];
for (int x : vec)
vc[s[v1[x].back().fi] - 'a'].emplace_back(x);
for (int c = 0; c < 26; ++c)
build(vc[c], fa);
}
void build(vi vec, int fa) {
if (vec.empty())
return;
if (vec.size() == 1u) {
int p = ++cnt;
sn[fa].emplace_back(p);
bel[p].emplace_back(vec.back());
return;
}
int mx = 0, ps = 0;
for (int x : vec) {
int len = v1[x].back().se - v1[x].back().fi + 1;
if (len > mx)
mx = len, ps = x;
}
map<int, vi> mp;
for (int x : vec) {
if (x == ps)
continue;
int len = 0;
int cur = v1[ps].back().fi;
while (!v1[x].empty()) {
auto &[l, r] = v1[x].back();
int tmp = min(SA::lcp(l, cur), v1[ps].back().se - cur + 1);
if (tmp > r - l) {
len += r - l + 1;
v1[x].pop_back();
} else {
len += tmp;
l += tmp;
break;
}
}
mp[len].emplace_back(x);
}
int mxlen = prev(mp.end())->fi;
while (true) {
assert(!v1[ps].empty());
auto &[l, r] = v1[ps].back();
if (mxlen > r - l) {
mxlen -= r - l + 1;
v1[ps].pop_back();
} else {
l += mxlen;
break;
}
}
prev(mp.end())->se.emplace_back(ps);
for (auto [lcplen, vc] : mp) {
int p = ++cnt;
sn[fa].emplace_back(p);
vi tmp;
for (int x : vc) {
if (v1[x].empty())
bel[p].emplace_back(x);
else
tmp.emplace_back(x);
}
split(tmp, fa = p);
}
}
void dfs(int u) {
for (int x : bel[u])
if (op[x] == '?')
lef1[x] = num1;
for (int x : bel[u])
if (op[x] == '+')
id1[x] = ++num1;
for (int v : sn[u])
dfs(v);
for (int x : bel[u])
if (op[x] == '?')
rig1[x] = num1;
}
struct node {
int v, x, y, id;
friend bool operator<(const node a, const node b) {
if (a.x ^ b.x)
return a.x < b.x;
return a.id < b.id;
}
} o[N];
int tr[N];
void upd(int x, int v) {
while (x <= num2)
tr[x] += v, x += (x & -x);
}
int qry(int x) {
int res = 0;
while (x)
res += tr[x], x ^= (x & -x);
return res;
}
void solve(int l, int r) {
if (l == r)
return;
int mid = (l + r) >> 1;
solve(l, mid);
solve(mid + 1, r);
int ed = 0;
for (int i = l; i <= mid; ++i) {
if (op[i] == '+')
o[++ed] = (node){1, id1[i], id2[i], 0};
if (op[i] == '-')
o[++ed] = (node){-1, id1[del[i]], id2[del[i]], 0};
}
for (int i = r; i > mid; --i)
if (op[i] == '?') {
o[++ed] = (node){1, rig1[i], rig2[i], i};
o[++ed] = (node){1, lef1[i], lef2[i], i};
o[++ed] = (node){-1, lef1[i], rig2[i], i};
o[++ed] = (node){-1, rig1[i], lef2[i], i};
}
sort(o + 1, o + ed + 1);
for (int i = 1; i <= ed; ++i) {
if (o[i].id)
res[o[i].id] += qry(o[i].y) * o[i].v;
else
upd(o[i].y, o[i].v);
}
for (int i = 1; i <= ed; ++i)
if (!o[i].id)
upd(o[i].y, -o[i].v);
}
int main() {
n = read();
q = read();
char cc = getchar();
while (isspace(cc))
cc = getchar();
for (int i = 1; i <= n; ++i)
s[i] = cc, cc = getchar();
SA::getSA(123);
SA::getLCP();
vi init;
for (int i = 1; i <= q; ++i) {
cc = getchar();
while (isspace(cc))
cc = getchar();
op[i] = cc;
if (cc == '+') {
int len = read();
v1[i].resize(len);
v2[i].resize(len);
for (int t = 0; t < len; ++t) {
int l = read(), r = read();
v1[i][len - 1 - t].fi = l;
v1[i][len - 1 - t].se = r;
v2[i][t].fi = n - r + 1;
v2[i][t].se = n - l + 1;
}
init.emplace_back(i);
}
if (cc == '-')
del[i] = read();
if (cc == '?') {
int len1 = read();
v1[i].resize(len1);
for (int t = len1 - 1; ~t; --t) {
v1[i][t].fi = read();
v1[i][t].se = read();
}
int len2 = read();
v2[i].resize(len2);
for (int t = 0; t < len2; ++t) {
v2[i][t].se = n - read() + 1;
v2[i][t].fi = n - read() + 1;
}
init.emplace_back(i);
}
}
split(init, 0);
dfs(0);
for (int i = 0; i <= cnt; ++i)
bel[i].clear(), sn[i].clear();
cnt = 0;
for (int i = 1; i <= q; ++i) {
swap(id1[i], id2[i]);
swap(lef1[i], lef2[i]);
swap(rig1[i], rig2[i]);
v1[i].swap(v2[i]);
}
swap(num1, num2);
reverse(s + 1, s + n + 1);
SA::getSA(123);
SA::getLCP();
build(init, 0);
dfs(0);
solve(1, q);
for (int i = 1; i <= q; ++i)
if (op[i] == '?')
printf("%d\n", res[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 40628kb
input:
8 7 abcaabbc + 3 1 3 2 4 3 8 + 2 1 4 1 8 + 1 2 4 ? 1 5 6 1 7 8 - 3 + 1 2 5 ? 1 2 3 1 5 5
output:
2 1
result:
ok 2 lines
Test #2:
score: -100
Runtime Error
input:
5 2000 bbaab + 1 3 5 + 2 5 5 3 5 - 2 ? 1 1 3 3 3 3 4 5 2 5 - 1 ? 3 1 1 2 4 1 5 1 3 4 ? 1 1 2 2 2 4 4 4 ? 1 1 5 1 5 5 + 3 1 2 1 5 1 4 ? 2 1 5 1 3 2 1 2 5 5 ? 1 3 4 1 4 5 - 9 ? 1 1 4 1 2 3 + 2 1 5 1 2 + 1 1 4 - 15 - 14 ? 2 2 5 2 5 1 3 4 + 1 2 3 - 19 + 3 1 4 1 5 4 5 - 21 + 1 2 5 ? 3 1 5 5 5 1 5 1 3 5 ?...