rt,TLE#11,代码如下
#include <iostream>
#include <cstdio>
const int BUFFER_SIZE = 1 << 20;
char rb[BUFFER_SIZE], *rp = rb, *rt = rb;
inline char read_char() {
return rp == rt ? (rt = rb + fread(rb, 1, BUFFER_SIZE, stdin), rp = rb, *rp++) : *rp++;
}
inline int read_int() {
int x = 0;
char ch = read_char(), flag = 0;
while (ch != '-' && (ch < '0' || ch > '9')) {
ch = read_char();
}
if (ch == '-') {
flag = 1;
ch = read_char();
}
for (x = 0; ch >= '0' && ch <= '9'; ch = read_char()) {
x = x * 10 + (ch - '0');
}
return flag ? -x : x;
}
int p1 = -1;
char buf[BUFFER_SIZE];
const int p2 = BUFFER_SIZE - 1;
inline void flush() {
fwrite(buf, 1, p1 + 1, stdout);
p1 = -1;
}
inline void put_char(char s) {
if (p1 == p2)
flush();
buf[++p1] = s;
}
inline void write_int(int n) {
static char s[40];
static int top = 0;
static int flag = n < 0;
n = n > 0 ? n : -n;
while (s[++top] = (n % 10) + '0', n /= 10);
if (flag) s[++top] = '-';
while (put_char(s[top]), --top);
return;
}
const int nn = 1e6 + 5;
int a[nn], n, m;
namespace SegTree {
struct node {
int val;
node *left_son, *right_son;
node() {
val = 0;
left_son = right_son = NULL;
}
};
node *root[nn];
void build(node *p, const int l, const int r) {
if (l == r) {
p -> val = a[l];
return;
}
p -> left_son = new node();
p -> right_son = new node();
int mid = l + r >> 1;
build(p -> left_son, l, mid);
build(p -> right_son, mid + 1, r);
return;
}
node* modify(node *p, const int &k, const int &val, const int l, const int r) {
node *now = new node();
*now = *p;
p = now;
if (l == r) {
p -> val = val;
return p;
}
int mid = l + r >> 1;
if (k <= mid) p -> left_son = modify(p -> left_son, k, val, l, mid);
else p -> right_son = modify(p -> right_son, k, val, mid + 1, r);
return p;
}
int ask(node *p, const int &k, const int l, const int r) {
if (l == r) return p -> val;
int mid = l + r >> 1;
if (k <= mid) return ask(p -> left_son, k, l, mid);
else return ask(p -> right_son, k, mid + 1, r);
}
};
using namespace SegTree;
int main() {
n = read_int();
m = read_int();
for (register int i = 1; i <= n; ++i) a[i] = read_int();
root[0] = new node();
build(root[0], 1, n);
int ver, opt, k, val;
for (register int i = 1; i <= m; ++i) {
ver = read_int();
opt = read_int();
k = read_int();
if (opt == 1) {
val = read_int();
root[i] = modify(root[ver], k, val, 1, n);
} else {
printf("%d\n", ask(root[ver], k, 1, n));
root[i] = root[ver];
}
}
}
感觉不像常数问题,是哪里写假了吗