BZOJ2002 & LCT模板(分块不会搞)-白红宇

BZOJ2002 & LCT模板(分块不会搞)

阅读量：5108 次

发布时间：2019-06-13

本文共 6974 字，大约阅读时间需要 23 分钟。

题意:

　　看题.

　　某天，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 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
               #include 
               
                 #include 
                
                  #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
                 
                   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 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
               #include 
               
                 #include 
                
                  #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
                 
                   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; } }}

转载于:https://www.cnblogs.com/YCuangWhen/p/5287950.html

你可能感兴趣的文章