# [HNOI2010] 弹飞绵羊

2018/08/09 06:51

Code

编号是从0开始的（调了1小时），pushup的时候不要把size[ch[x][0]]打成了ch[x][0]（调了40多分钟）

/*By DennyQi*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define  Max(a,b)  (((a)>(b)) ? (a) : (b))
#define  Min(a,b)  (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int MAXN = 200010;
const int MAXM = 27010;
const int INF = 1061109567;
int x = 0; int w = 1; register int c = getchar();
while(c ^ '-' && (c < '0' || c > '9')) c = getchar();
if(c == '-') w = -1, c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * w;
}
int N,M,opt,x,y;
int K[MAXN];
int size[MAXN],ch[MAXN][2],fa[MAXN],tag[MAXN];
inline bool rson(int f, int x){
return ch[f][1] == x;
}
inline bool isroot(int x){
return (ch[fa[x]][0] != x) && (ch[fa[x]][1] != x);
}
inline void pushup(int x){
size[x] = size[ch[x][0]] + size[ch[x][1]] + 1;
}
inline void rotate(int x){
int f = fa[x], gf = fa[f];
int p = rson(f, x), q = !p;
if(!isroot(f)) ch[gf][rson(gf,f)] = x;
fa[x] = gf;
ch[f][p] = ch[x][q], fa[ch[x][q]] = f;
ch[x][q] = f, fa[f] = x;
pushup(f), pushup(x);
}
void pushdown(int x){
if(!isroot(x)) pushdown(fa[x]);
if(!tag[x]) return;
swap(ch[x][0], ch[x][1]);
tag[ch[x][0]] ^= 1;
tag[ch[x][1]] ^= 1;
tag[x] = 0;
}
inline void splay(int x){
pushdown(x);
while(!isroot(x)){
int f = fa[x], gf = fa[f];
if(isroot(f)){
rotate(x);
break;
}
if(rson(gf,f) != rson(f,x)){
rotate(x), rotate(x);
}
else{
rotate(f), rotate(x);
}
}
}
inline void access(int x){
for(int y = 0; x; y = x, x = fa[x]){
splay(x);
ch[x][1] = y;
pushup(x);
}
}
inline void makeroot(int x){
access(x);
splay(x);
tag[x] ^= 1;
}
inline int findroot(int x){
access(x);
splay(x);
for(; ch[x][0]; x = ch[x][0]);
return x;
}
inline void split(int x, int y){
makeroot(x);
access(y);
splay(y);
}
inline void link(int x, int y){
makeroot(x);
fa[x] = y;
}
inline void cut(int x, int y){
split(x, y);
if(ch[y][0] != x || ch[x][1] != 0) return;
fa[x] = ch[y][0] = 0;
}
inline int query(int x){
split(x, N+1);
return size[N+1] - 1;
}
}qxz;
int main(){
N = r;
for(int i = 1; i <= N; ++i){
K[i] = r;
if(i + K[i] > N){
}
else{
}
}
M = r;
while(M--){
opt = r, x = r + 1;
if(opt == 1){
printf("%d\n", qxz.query(x));
}
else{
y = r;
if(x + K[x] > N){
qxz.cut(x, N+1);
}
else{
qxz.cut(x, x+K[x]);
}
if(x + y > N){
}
else{
}
K[x] = y;
}
}
return 0;
}

0
0 收藏

0 评论
0 收藏
0