BZOJ2002: [Hnoi2010]Bounce 弹飞绵羊(LCT)
2018-06-17 20:43:49来源:未知 阅读 ()
Submit: 13753 Solved: 6983
[Submit][Status][Discuss]
Description
某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞。绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任何时候弹力系数均为正整数。
Input
第一行包含一个整数n,表示地上有n个装置,装置的编号从0到n-1,接下来一行有n个正整数,依次为那n个装置的初始弹力系数。第三行有一个正整数m,接下来m行每行至少有两个数i、j,若i=1,你要输出从j出发被弹几次后被弹飞,若i=2则还会再输入一个正整数k,表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000,对于100%的数据n<=200000,m<=100000
Output
对于每个i=1的情况,你都要输出一个需要的步数,占一行。
Sample Input
1 2 1 1
3
1 1
2 1 1
1 1
Sample Output
3
HINT
Source
1A了好激动QWQ..
首先考虑没有修改操作,那么一个递推就解决了
但是有修改操作呢?
对于一个节点来说,它有且仅有一条出边,这样我们如果开一个超级点,表示到达这个点就跳出去的话,这很显然是一棵树
删除操作就相当于断开一条边,然后再连接一条边
于是我们可以用LCT维护这个东西
如果$i$这个位置跳一下能跳出去,就向$N+1$连边,否则向它能跳到的位置连边
询问操作,我们可以先把要询问的节点置成根,然后access(N+1),最后把$N+1$ splay到根节点,那么$N+1$的子树大小就是答案
刚开始想的是维护深度,但是平衡树维护深度特别麻烦QWQ....
// luogu-judger-enable-o2 // luogu-judger-enable-o2 // luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN=3 * 1e5 + 10; inline int read() { char c = getchar();int x = 0,f = 1; while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();} return x * f; } #define ls(x) T[x].ch[0] #define rs(x) T[x].ch[1] #define fa(x) T[x].f struct node { int ch[2], f, r, siz; }T[MAXN]; bool isroot(int x) { return T[fa(x)].ch[0] != x && T[fa(x)].ch[1] != x; } void update(int x) { T[x].siz = T[ls(x)].siz + T[rs(x)].siz + 1; } bool ident(int x) { return T[fa(x)].ch[0] == x ? 0 : 1; } void connect(int x, int fa, int how) { T[x].f = fa; T[fa].ch[how] = x; } void pushdown(int x) { if(T[x].r) { swap(ls(x), rs(x)); T[ls(x)].r ^= 1; T[rs(x)].r ^= 1; T[x].r = 0; } } void rotate(int x) { int Y = fa(x), R = fa(Y), Yson = ident(x), Rson = ident(Y); int B = T[x].ch[Yson ^ 1]; T[x].f = R; if(!isroot(Y)) connect(x, R, Rson); connect(B, Y, Yson); connect(Y, x, Yson ^ 1); update(Y);update(x); } int st[MAXN], top = 0; void splay(int x) { int now = x, top = 0; st[++top] = now; while(!isroot(now)) st[++top] = now = fa(now); while(top) pushdown(st[top--]); for(int y = T[x].f; !isroot(x); rotate(x), y = fa(x)) if(!isroot(y)) rotate( ident(x) == ident(y) ? y : x); } void access(int x) { for(int y = 0; x; x = fa(y = x)) splay(x), rs(x) = y, update(x); } int findroot(int x) { access(x); splay(x); while(ls(x)) x = ls(x); return x; } void makeroot(int x) { access(x); splay(x); T[x].r ^= 1; } void link(int x, int y) { makeroot(x); fa(x) = y; } void cut(int x, int y) { makeroot(x); if(findroot(y) == x && fa(x) == y && !rs(x)) fa(x) = T[y].ch[0] = 0, update(y); } int N; int a[MAXN]; int main() { #ifdef WIN32 freopen("a.in","r",stdin); //freopen("a.out","w",stdout); #else #endif N = read(); for(int i = 1; i <= N; i++) { a[i] = read(); (i + a[i] > N) ? link(i, N + 1) : link(i, i + a[i]); } int M = read(); while(M--) { int opt = read(), x = read() + 1; if(opt == 1) { makeroot(x); access(N + 1); splay(N + 1); printf("%d\n", T[N + 1].siz - 1); } else { int y = read(); //splay(x); (x + a[x] > N) ? cut(x, N + 1) : cut(x, x + a[x]); a[x] = y; (x + a[x] > N) ? link(x, N + 1) : link(x, x + a[x]); } } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- P3205 [HNOI2010]合唱队 2019-08-26
- bzoj2002 [ HNOI2010 ] -- LCT 2018-06-17
- 洛谷P3209 [HNOI2010]PLANAR(2-SAT) 2018-06-17
- BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash