信息学训练营NOIP模拟题(2)-数字序列seq

本文试题为往期清北学堂信息学训练营内部模拟测试题，建议审题解题后再看答案，仅供大家学习,如需测试数据请留言。

往期题目：

信息学训练营NOIP模拟题(1)-strings

代码：

AC CODE

#include <cstdio>

#include <ctime>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = (int)2e5;

typedef int arr[N + 10];

int f[N + 10][21];

arr dep, seq, para;

int operations, n, ans, root;

void add(int id, int x) {

seq[++n] = id;

f[id][0] = seq[n - 1], dep[id] = dep[f[id][0]] + 1;

for (int c = 1; c <= 20; ++c) {

if (dep[id] <= (1 << c)) break;

f[id][c] = f[f[id][c - 1]][c - 1];

}

}

void revoke(int x) {

++n, seq[n] = seq[n - x - 1];

}

int query(int x) {

int res = seq[n];

x = dep[res] - x - 1;

for (int c = 20; c >= 0; --c)

if (x >= (1 << c)) res = f[res][c], x ^= (1 << c);

return para[res];

}

int main() {

freopen('seq.in', 'r', stdin);

freopen('seq.out', 'w', stdout);

int test;

for (scanf('%d', &test); test--; ) {

scanf('%d', &operations);

seq[n = 1] = N + 1, dep[N + 1] = 1, ans = 0, root = N + 1;

for (int k = 1; k <= operations; ++k) {

int tp, c;

scanf('%d %d', &tp, &c);

para[k] = c;

if (tp == 1) add(k, c);

else if (tp == 2) revoke(c);

else printf('%d\n', ans = query(c));

}

}

return 0;

}

试题解析：