题意:
看题.
某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿 着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置， 则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何 时候弹力系数均为正整数。
n<=20w.
SOL:
LCT啊...啊啊啊啊啊啊啊啊啊
我一直想打一个属于我的模板,然后我就打了,打了三个版本,然后一直TLE....具体的过程是这样的...
第一遍:懵懵懂懂地打了一个lct,然后傻傻分不清楚了fa和pre,然后各种注释得代码没法看...那么换一个吧.
第二遍:终于解决了答案问题!!!然而在调试过程中,发现合并时子树中结点的pre不能及时更新...然后就一直想啊,一直想啊....怎么处理呢...然后自认为很机灵地把pre默认变成树的结构...每次合并把pre,splay以后单独翻出来...一直TLE莫名其妙然后发现...这他妈不是相当于一个一个加点吗...woc真是傻逼...
然后看了别人的代码...然后体会到了智商的捉急...可以用一个数组记录树的结构为什么偏要强加给pre...旋转的时候可以顺便传pre的啊...
然后就写完了.
马丹常数大的一逼...2000ms...原来用stack7000ms这不是日了狗了么...去掉几个pushdown快了4ms....醉了醉了...有空还要优化一下...pushdown的那部分总觉得有点丝帛,还有这道题树是有向边有更快更短的写法,不用反转,大概这个地方会快一点.多打几个题比较一下好了.
妈的多少个下午和晚上啊...花了多少图啊... 啊啊啊啊啊啊啊...
关于LCT...其实还是非常简单的...我觉得这是lj讲的最不好的...或者是两个月前我还太傻逼...
网上论文非常多...代码也非常显然...那么就不多说了= =
----------------------------------split line--------------------------------------
关于优化的一些事情...贴一张优化的过程图...
中间那个2948ms是随便拉一个写的差不多的模板跑的时间.
7000ms是开的stl的stack,然后改成数组模拟变成2000+ms,比他快难道是读入优化的原因?
然后去掉几个pushdown少了4ms...
然后发现原来看着书写的时候养成随手splay的好习惯...去掉少了200ms...
然后发现全程没有加inline啊!!!不行不行,赶紧加.加了inline又快了200ms...
然后看link和cut的过程(看模板打的= =)...然后想到原来我自己实现的时候因为这种有向边并不需要写beroot,然后根据原来自己口胡打了改了几句话又快了200ms....
1400ms虽然还是不太理想----800ms是怎么跑出来QAQ...不过不想改了...
于是论剪枝的重要性...(剪了个卵...什么都没干...)
再贴个1400的code...
/*==========================================================================
# Last modified: 2016-03-17 14:14
# Filename: 2002_3.cpp
# Description:
==========================================================================*/
#define me AcrossTheSky
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #include <set>
#include <map>
#include <queue>
#include <vector> #define lowbit(x) (x)&(-x)
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define getlc(a) ch[(a)][0]
#define getrc(a) ch[(a)][1] #define maxn 200010
#define maxm 100000
#define pi 3.1415926535898
#define _e 2.718281828459
#define INF 1070000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull; template<class T> inline
void read(T& num) {
bool start=false,neg=false;
char c;
num=0;
while((c=getchar())!=EOF) {
if(c=='-') start=neg=true;
else if(c>='0' && c<='9') {
start=true;
num=num*10+c-'0';
} else if(start) break;
}
if(neg) num=-num;
}
/*==================split line==================*/
int ch[maxn][2],rev[maxn],nxt[maxn],fa[maxn],pre[maxn],s[maxn];
int stack[maxn];
int n;
inline void pushup(int x){
s[x]=1+s[ch[x][0]]+s[ch[x][1]];
}
inline void pushdown(int x){
if (rev[x]){
swap(ch[x][0],ch[x][1]);
rev[ch[x][0]]^=1;
rev[ch[x][1]]^=1;
rev[x]=0;
}
}
inline void rotate(int x){
//pushdown(x);
int p=fa[x],q=fa[p],d=ch[p][1]==x;
fa[ch[p][d]=ch[x][d^1]]=p; pushup(p);
fa[ch[x][d^1]=p]=x;
fa[x]=q;
if (q){
if (ch[q][1]==p) ch[q][1]=x;
else if (ch[q][0]==p) ch[q][0]=x;
}
else pre[x]=pre[p];
//pushup(x);
}
inline void splay(int x){
int top=0;
for(int i=x;i;i=fa[i])
stack[++top]=i;
for(;top;top--) pushdown(stack[top]);
for (int y;(y=fa[x])!=0;rotate(x))
if (fa[y])
rotate((getlc(y)==x)==(getlc(fa[y])==y)?y:x);
}
inline void access(int x){
int v;
splay(x);
if(ch[x][1]) pre[ch[x][1]]=x,fa[ch[x][1]]=0,ch[x][1]=0;
//pushup(x);
while (v=pre[x]) {
splay(v);
pre[x]=0;
if (ch[v][1]) pre[ch[v][1]]=v,fa[ch[v][1]]=0;
ch[v][1]=x; fa[x]=v;
pushup(v);
x=v;
}
}
inline void beroot(int x){
access(x);
splay(x);
rev[x]^=1;
}
inline void cut(int x,int y){
//beroot(x);
access(x);
splay(y);
ch[y][1]=0;
fa[x]=pre[x]=0;
pushup(y);
}
inline void link(int x,int y){
beroot(x); pre[x]=y;
//access(x); splay(x);
}
int main(){
int n,m; read(n);
FORP(i,1,n) {int x,to; read(x); to=min(i+x,n+1); s[i]=1; pre[i]=nxt[i]=to;}
s[n+1]=1;
read(m);
FORP(i,1,m){
int t; read(t); int x; read(x); x++;
if (t==1){
beroot(n+1);
access(x); splay(x);
printf("%d\n",s[ch[x][0]]);
}
else {
int y; read(y); y=min(x+y,n+1);
cut(x,nxt[x]); link(x,y); nxt[x]=y;
}
}
}
Code:
/*==========================================================================
# Last modified: 2016-03-17 14:14
# Filename: 2002_3.cpp
# Description:
==========================================================================*/
#define me AcrossTheSky
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #include <set>
#include <map>
#include <queue>
#include <vector> #define lowbit(x) (x)&(-x)
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define getlc(a) ch[(a)][0]
#define getrc(a) ch[(a)][1] #define maxn 200010
#define maxm 100000
#define pi 3.1415926535898
#define _e 2.718281828459
#define INF 1070000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull; template<class T> inline
void read(T& num) {
bool start=false,neg=false;
char c;
num=0;
while((c=getchar())!=EOF) {
if(c=='-') start=neg=true;
else if(c>='0' && c<='9') {
start=true;
num=num*10+c-'0';
} else if(start) break;
}
if(neg) num=-num;
}
/*==================split line==================*/
int ch[maxn][2],rev[maxn],nxt[maxn],fa[maxn],pre[maxn],s[maxn];
int stack[maxn];
int n;
void pushup(int x){
s[x]=1+s[ch[x][0]]+s[ch[x][1]];
}
void pushdown(int x){
if (rev[x]){
swap(ch[x][0],ch[x][1]);
rev[ch[x][0]]^=1;
rev[ch[x][1]]^=1;
rev[x]=0;
}
}
void rotate(int x){
//pushdown(x);
int p=fa[x],q=fa[p],d=ch[p][1]==x;
fa[ch[p][d]=ch[x][d^1]]=p; pushup(p);
fa[ch[x][d^1]=p]=x;
fa[x]=q;
if (q){
if (ch[q][1]==p) ch[q][1]=x;
else if (ch[q][0]==p) ch[q][0]=x;
}
else pre[x]=pre[p];
//pushup(x);
}
void splay(int x){
int top=0;
for(int i=x;i;i=fa[i])
stack[++top]=i;
for(;top;top--) pushdown(stack[top]);
for (int y;(y=fa[x])!=0;rotate(x))
if (fa[y])
rotate((getlc(y)==x)==(getlc(fa[y])==y)?y:x);
}
void access(int x){
int v;
splay(x);
if(ch[x][1]) pre[ch[x][1]]=x,fa[ch[x][1]]=0,ch[x][1]=0;
//pushup(x);
while (v=pre[x]) {
splay(v);
pre[x]=0;
if (ch[v][1]) pre[ch[v][1]]=v,fa[ch[v][1]]=0;
ch[v][1]=x; fa[x]=v;
pushup(v);
x=v;
}
}
void beroot(int x){
access(x);
splay(x);
rev[x]^=1;
}
void cut(int x,int y){
beroot(x);
access(y);
splay(y);
ch[y][0]=0;
fa[x]=pre[x]=0;
pushup(y);
}
void link(int x,int y){
beroot(x); pre[x]=y;
access(x); splay(x);
}
int main(){
int n,m; read(n);
FORP(i,1,n) {
int x; read(x);
int to=min(i+x,n+1);
s[i]=1; pre[i]=to; nxt[i]=to;
}
s[n+1]=1;
read(m);
FORP(i,1,m){
int t; read(t); int x; read(x); x++;
if (t==1){
beroot(n+1);
access(x); splay(x);
printf("%d\n",s[ch[x][0]]);
}
else {
int y; read(y); y=min(x+y,n+1);
cut(x,nxt[x]); link(x,y); nxt[x]=y;
}
}
}