QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #586564 | #6837. AC Automaton | cyj888 | TL | 3ms | 33656kb | C++11 | 8.6kb | 2024-09-24 14:06:48 | 2024-09-24 14:06:48 |
Judging History
answer
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma G++ optimize(1)
#pragma G++ optimize(2)
#pragma G++ optimize(3)
#pragma G++ optimize("Ofast")
#pragma G++ optimize("inline")
#pragma G++ optimize("-fgcse")
#pragma G++ optimize("-fgcse-lm")
#pragma G++ optimize("-fipa-sra")
#pragma G++ optimize("-ftree-pre")
#pragma G++ optimize("-ftree-vrp")
#pragma G++ optimize("-fpeephole2")
#pragma G++ optimize("-ffast-math")
#pragma G++ optimize("-fsched-spec")
#pragma G++ optimize("unroll-loops")
#pragma G++ optimize("-falign-jumps")
#pragma G++ optimize("-falign-loops")
#pragma G++ optimize("-falign-labels")
#pragma G++ optimize("-fdevirtualize")
#pragma G++ optimize("-fcaller-saves")
#pragma G++ optimize("-fcrossjumping")
#pragma G++ optimize("-fthread-jumps")
#pragma G++ optimize("-funroll-loops")
#pragma G++ optimize("-fwhole-program")
#pragma G++ optimize("-freorder-blocks")
#pragma G++ optimize("-fschedule-insns")
#pragma G++ optimize("inline-functions")
#pragma G++ optimize("-ftree-tail-merge")
#pragma G++ optimize("-fschedule-insns2")
#pragma G++ optimize("-fstrict-aliasing")
#pragma G++ optimize("-fstrict-overflow")
#pragma G++ optimize("-falign-functions")
#pragma G++ optimize("-fcse-skip-blocks")
#pragma G++ optimize("-fcse-follow-jumps")
#pragma G++ optimize("-fsched-interblock")
#pragma G++ optimize("-fpartial-inlining")
#pragma G++ optimize("no-stack-protector")
#pragma G++ optimize("-freorder-functions")
#pragma G++ optimize("-findirect-inlining")
#pragma G++ optimize("-frerun-cse-after-loop")
#pragma G++ optimize("inline-small-functions")
#pragma G++ optimize("-finline-small-functions")
#pragma G++ optimize("-ftree-switch-conversion")
#pragma G++ optimize("-foptimize-sibling-calls")
#pragma G++ optimize("-fexpensive-optimizations")
#pragma G++ optimize("-funsafe-loop-optimizations")
#pragma G++ optimize("inline-functions-called-once")
#pragma G++ optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
#define pb push_back
#define ott(i,l,r) for (int i = l; i <= r; i ++)
#define tto(i,l,r) for (int i = r; i >= l; i --)
using namespace std;
using ll = long long;
int read () {
int x = 0; bool f = 0; char c = getchar ();
while (!isdigit (c)) f |= (c == '-'), c = getchar ();
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
if (f) x = -x; return x;
}
const int N = 3e5 + 110;
int n, m, q, idx, B;
ll res;
vector <int> e[N], E[N];
int up[N], dn[N];
int dfn[N], dep[N], fa[N];
int lg[N << 1], f[N << 1][20];
char ch[N];
void dfs0 (int u) {
f[dfn[u] = ++ idx][0] = u, dep[u] = dep[fa[u]] + 1;
for (int v : e[u]) {
dfs0 (v);
f[++ idx][0] = u;
}
return ;
}
int lca (int x, int y) {
x = dfn[x], y = dfn[y];
if (x > y) swap (x, y);
int z = lg[y - x + 1], f1 = f[x][z], f2 = f[y - (1 << z) + 1][z];
return dep[f1] < dep[f2] ? f1 : f2;
}
struct OPT {
int x; char c;
} a[N];
struct BLOCK {
int ac, now, sum;//ac = 'A'count
int s[1201];
void ins (int v) {
if (v >= now) ++ sum;
if (-m <= v && v <= m) ++ s[v + m];
return ;
}
void upd (int i) {
if (ch[i] == 'A') ++ ac;
if (ch[i] == '?') ins (dn[i] - up[i]);
return ;
}
void add (int v) {
if (v == 1) {
sum -= s[(now ++) + m];
res -= 1ll * sum;
}
if (v == -1) {
res += 1ll * sum;
sum += s[(-- now) + m];
}
return ;
}
void clear () {
ac = now = sum = 0;
ott (i, 0, m + m) s[i] = 0;
return ;
}
} b[N];
int id[N], val[N], FA[N];
bool cmp (int x, int y) {
return dfn[x] < dfn[y];
}
void push (int u, int z) {
b[z].upd (u);
for (int v : e[u]) push (v, z);
return ;
}
int Z, OTH;
void find (int x) {
if (id[fa[x]]) {
val[Z = id[x] = ++ idx] = x;
return ;
}
find (fa[x]);
b[Z].upd (fa[x]);
for (int v : e[fa[x]]) {
if (v == x) continue;
if (!OTH) val[OTH = id[v] = ++ idx] = v;
push (v, OTH);
}
return ;
}
void red (int u) {
dn[u] = 0;
for (int v : e[u]) {
up[v] = up[u] + (ch[u] != 'C');
red (v);
dn[u] += dn[v] + (ch[v] != 'A');
}
if (ch[u] == 'A') res += 1ll * dn[u];
if (ch[u] == '?') res += 1ll * max (0, dn[u] - up[u]);
return ;
}
void cup (int u, int V) {
for (int v : E[u]) {
if (val[v] < 0) {
int tv = -val[v];
if (ch[tv] == '?') res -= 1ll * max (0, dn[tv] - up[tv]);
up[tv] += V;
if (ch[tv] == '?') res += 1ll * max (0, dn[tv] - up[tv]);
}
else {
b[v].add (V);
}
cup (v, V);
}
return ;
}
void cdn (int u, int V) {
if (!u) return ;
if (val[u] < 0) {
int tu = -val[u];
if (ch[tu] == '?') res -= 1ll * max (0, dn[tu] - up[tu]);
dn[tu] += V; if (ch[tu] == 'A') res += 1ll * V;
if (ch[tu] == '?') res += 1ll * max (0, dn[tu] - up[tu]);
}
else {
b[u].add (-V), res += 1ll * b[u].ac * V;
}
cdn (FA[u], V);
return ;
}
void sol () {
ott (i, 1, m) val[++ idx] = a[i].x;
sort (val + 1, val + 1 + idx), idx = unique (val + 1, val + 1 + idx) - val - 1;
sort (val + 1, val + 1 + idx, cmp);
ott (i, 2, idx) val[idx + i - 1] = lca (val[i - 1], val[i]); val[idx += idx] = 1;
sort (val + 1, val + 1 + idx), idx = unique (val + 1, val + 1 + idx) - val - 1;
ott (i, 1, idx) {
id[val[i]] = i;
val[i] = -val[i];//区分会修改的点
}
ott (i, 2, idx) {
if (val[i] > 0) break;
if (!id[fa[-val[i]]]) {
OTH = Z = 0, find (-val[i]);
if (OTH) E[FA[OTH] = i].pb (OTH);
E[FA[Z] = id[fa[val[Z]]]].pb (Z), E[FA[i] = Z].pb (i);
}
else E[FA[i] = id[fa[-val[i]]]].pb (i);
}
ott (i, 1, idx) {
if (val[i] > 0) break;
OTH = 0; for (int v : e[-val[i]]) {
if (id[v]) continue;
if (!OTH) {
val[OTH = id[v] = ++ idx] = v;
E[FA[OTH] = i].pb (OTH);
}
push (v, OTH);
}
}
ott (i, 1, m) {
int x = a[i].x; char c = a[i].c;
if (ch[x] != 'C') cup (id[x], -1); if (ch[x] != 'A') cdn (FA[id[x]], -1);
if (ch[x] == 'A') res -= 1ll * dn[x];
if (ch[x] == '?') res -= 1ll * max (0, dn[x] - up[x]);
ch[x] = c;
if (ch[x] == 'A') res += 1ll * dn[x];
if (ch[x] == '?') res += 1ll * max (0, dn[x] - up[x]);
if (ch[x] != 'C') cup (id[x], 1); if (ch[x] != 'A') cdn (FA[id[x]], 1);
printf ("%lld\n", res);
}
ott (i, 1, idx) {
E[i].clear (), FA[i] = 0;
if (val[i] < 0) val[i] = -val[i];
else b[i].clear ();
id[val[i]] = 0, val[i] = 0;
}
m = idx = 0, res = 0; red (1);
return ;
}
int main () {
n = read (), q = read (), cin >> ch + 1; ott (i, 2, n) e[fa[i] = read ()].pb (i);
B = 600; dfs0 (1);
ott (j, 1, 19) {
ott (i, 1, idx - (1 << j) + 1) {
int f1 = f[i][j - 1], f2 = f[i + (1 << j - 1)][j - 1];
f[i][j] = dep[f1] < dep[f2] ? f1 : f2;
}
}
lg[0] = -1; ott (i, 1, idx) lg[i] = lg[i >> 1] + 1;
idx = 0, red (1); ott (i, 1, q) {
int x = read (); char c = getchar ();
a[++ m] = {x, c};
if (i % B == 0 || i == q) sol ();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 30768kb
input:
5 3 AC??C 1 2 2 1 1 ? 4 A 2 ?
output:
4 3 3
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 33656kb
input:
1000 1000 AC?ACCCCC?CCA??CCCCC?A?AC?C??C?ACCCACC?C?CCC?CACACA???????C?????CC?C?AAAAACCA??AAAACACACA???AACAC?CCC?CAC?AAAACCAC???ACAA??A??A?CA?A?ACACACCAA?ACACA?AC??AC??ACAAACCC??CAA?A???CC?AA??AC???A?CCCC??CACCAACC?AA?C?AAACCCA?AAA??C?CC??CACCACAACCA?AACCC?A?CCC?CC???AA?CACCCAAC??CAA??C?AA??CA???CAAA...
output:
2344 2345 2342 2342 2768 2768 2772 2772 2772 2772 2772 2772 2772 2767 2767 2767 2767 2764 2766 2766 2769 2765 2761 2764 2767 2772 2772 2772 2772 2772 2772 2777 2777 2777 2777 2774 2771 2774 2782 2778 2778 2772 2768 2772 2772 2772 2772 2772 2774 2774 2778 2781 2781 2779 2782 2784 2787 2782 2786 2788 ...
result:
ok 1000 lines
Test #3:
score: -100
Time Limit Exceeded
input:
300000 300000 AAA?CA?AA?AC?A?CCA?AACCAAA???CA?ACCAACCCCAACAAA?CCAAAC?A?C??CC?C?C?CCCA?CAA?ACA??C?C?AC??CA??ACA?AA???CACAAA?CACCCCCCC?A?AAAAAC?AACCA????CCC?C?AAACCCAA?C???CCCC?AAACAAA???A?CAAC??A??A??CCCC??AA?C??ACA?AACAAA????CAA???AAAAACC?C?CCA?CCAA?AAC?CC?CA?A??CC??CCAC??C??????AAC?AA?AA?AAC?C??AAC...
output:
14995917235 14995917235 14996064601 14996083631 14995980103 14995925797 14995925797 14995925797 14995967213 14995967213 14995967213 14995876211 14995774037 14995774037 14995774037 14995876791 14995866113 14995756158 14995647554 14995647554 14995560537 14995560537 14995583619 14995583619 14995583619 ...