原代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 200005;
int n;
struct hjtTree {
char v;
int ls, rs;
} tree[maxn*20];
int tot, caozuo, tail[maxn];
int rt[maxn];
int jmp[maxn];
char ch;
void upd(int p) {
if(tree[p].ls==0 && tree[p].rs==0) return;
tree[p].v = tree[tree[p].ls].v + tree[tree[p].rs].v;
}
int build(int l, int r, char v) {
int p = ++tot;
if(l==r) {
tree[p].v = v;
return p;
}
int midd = (l+r) >> 1;
tree[p].ls = build(l, midd, v);
tree[p].rs = build(midd+1, r, v);
upd(p);
return p;
}
int insert(int p, int l, int r, int x, char v) {
int q = ++tot;
tree[q] = tree[p];
if(tree[q].ls==tree[q].rs && tree[q].rs==0) { //----------------------------------
tree[q].v = v;
return q;
}
int midd = (l+r) >> 1;
if(x<=midd) {
tree[q].ls = insert(tree[q].ls, l, midd, x, v);
}
else if(x>midd) {
tree[q].rs = insert(tree[q].rs, midd+1, r, x, v);
}
upd(q);
return q;
}
char query(int p, int l, int r, int x) {
if(l==r) {
return tree[p].v;
}
int midd = (l+r) >> 1;
if(x <= midd) return query(tree[p].ls, l, midd, x);
else return query(tree[p].rs, midd+1, r, x);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
scanf("%d", &n);
rt[0] = build(1, n, 0);
for(int i=1; i<=n; ++i) {
scanf(" %c", &ch);
if(ch=='T') {
scanf(" %c", &ch);
int p = caozuo;
while(jmp[p]) p = jmp[p];
++caozuo;
tail[caozuo] = tail[p] + 1;
rt[caozuo] = insert(rt[p], 1, n, tail[caozuo], ch);
}
else if(ch=='U') {
int t;
scanf("%d", &t);
++caozuo;
jmp[caozuo] = caozuo-1-t;
}
else {
int t;
scanf("%d", &t);
int p = caozuo;
while(jmp[p]) p = jmp[p];
printf("%c\n", query(rt[p], 1, n, t));
}
}
return 0;
}
WA掉1、3、6三个点。
改成
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 200005;
int n;
struct hjtTree {
char v;
int ls, rs;
} tree[maxn*20];
int tot, caozuo, tail[maxn];
int rt[maxn];
int jmp[maxn];
char ch;
void upd(int p) {
if(tree[p].ls==0 && tree[p].rs==0) return;
tree[p].v = tree[tree[p].ls].v + tree[tree[p].rs].v;
}
int build(int l, int r, char v) {
int p = ++tot;
if(l==r) {
tree[p].v = v;
return p;
}
int midd = (l+r) >> 1;
tree[p].ls = build(l, midd, v);
tree[p].rs = build(midd+1, r, v);
upd(p);
return p;
}
int insert(int p, int l, int r, int x, char v) {
int q = ++tot;
tree[q] = tree[p];
if(l==r) {//-------------------------------------------
tree[q].v = v;
return q;
}
int midd = (l+r) >> 1;
if(x<=midd) {
tree[q].ls = insert(tree[q].ls, l, midd, x, v);
}
else if(x>midd) {
tree[q].rs = insert(tree[q].rs, midd+1, r, x, v);
}
upd(q);
return q;
}
char query(int p, int l, int r, int x) {
if(l==r) {
return tree[p].v;
}
int midd = (l+r) >> 1;
if(x <= midd) return query(tree[p].ls, l, midd, x);
else return query(tree[p].rs, midd+1, r, x);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
scanf("%d", &n);
rt[0] = build(1, n, 0);
for(int i=1; i<=n; ++i) {
scanf(" %c", &ch);
if(ch=='T') {
scanf(" %c", &ch);
int p = caozuo;
while(jmp[p]) p = jmp[p];
++caozuo;
tail[caozuo] = tail[p] + 1;
rt[caozuo] = insert(rt[p], 1, n, tail[caozuo], ch);
}
else if(ch=='U') {
int t;
scanf("%d", &t);
++caozuo;
jmp[caozuo] = caozuo-1-t;
}
else {
int t;
scanf("%d", &t);
int p = caozuo;
while(jmp[p]) p = jmp[p];
printf("%c\n", query(rt[p], 1, n, t));
}
}
return 0;
}
AC了。
改动的地方在注释那一行,也就是把判定左右子树都为0改为判定l==r。
求原因QwQ