注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

动态树(支持+*删换翻)  

2014-06-29 22:55:36|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
using namespace std;
typedef unsigned int ll;
struct node{int end,next;}g[mm];
ll bst[mm],size[mm],sum[mm],dj[mm],dc[mm];
int fa[mm],he[mm],stack[mm],flag[mm],ch[mm][2];
int tot,n,q,i,j,y,u,v,ans,x;
inline bool top(int w){return (ch[fa[w]][0]!=w&&ch[fa[w]][1]!=w);}
inline void add(int a,int b){g[++tot].end=b;g[tot].next=he[a];he[a]=tot;}
 
inline void rev(int w){flag[w]^=1;swap(ch[w][0],ch[w][1]);}
 
inline void jia(int a,ll b){bst[a]=(bst[a]+b)%MOD;dj[a]=(dj[a]+b)%MOD;
                      sum[a]=(sum[a]+(b*size[a])%MOD)%MOD;
}
                      
inline void che(int a,ll b){bst[a]=(bst[a]*b)%MOD;dj[a]=(dj[a]*b)%MOD;
                      dc[a]=(dc[a]*b)%MOD;sum[a]=(sum[a]*b)%MOD;
}
 
inline void up(int w)
 {sum[w]=(sum[ch[w][0]]+sum[ch[w][1]]+bst[w])%MOD;
  size[w]=size[ch[w][0]]+size[ch[w][1]]+1;
}
 
inline void down(int w)
 {if (flag[w]){if (ch[w][0])rev(ch[w][0]);
               if (ch[w][1])rev(ch[w][1]);
               flag[w]=0;
              }
  if (dc[w]!=1){
           if (ch[w][0])che(ch[w][0],dc[w]);
           if (ch[w][1])che(ch[w][1],dc[w]);dc[w]=1;
               }
 if (dj[w]!=0){
           if (ch[w][0])jia(ch[w][0],dj[w]);
           if (ch[w][1])jia(ch[w][1],dj[w]);dj[w]=0;
           }
 }
  
inline void xz(int x,int f)
 {int y=fa[x];int z=fa[y];
  ch[y][1-f]=ch[x][f];if (ch[x][f])fa[ch[x][f]]=y;//1
  fa[x]=z;if (ch[z][0]==y)ch[z][0]=x;if (ch[z][1]==y)ch[z][1]=x;//2
  fa[y]=x;ch[x][f]=y;//3
  up(y);up(x);
 }
inline void splay(int x)
 {int i,ok=0,p=x;
  down(x);
 while (!top(x)){
                int y=fa[x];int z=fa[y];
                down(z);down(y);down(x);
            if (top(y))xz(x,ch[y][0]==x);
            else if (ch[z][0]==y){
             if (ch[y][0]==x){xz(y,1);xz(x,1);}
                       else {xz(x,0);xz(x,1);}
                                 }
                            else{
             if (ch[y][1]==x){xz(y,0);xz(x,0);}
                       else {xz(x,1);xz(x,0);}
                                 }
                }
                 
 }
inline int Access(int x)
 {int y;
 for (y=0;x;x=fa[y=x])
            {splay(x);
             ch[x][1]=y;
             up(x);
            }
          return y;
 }
           if (c=='+'){x=read();
              Access(u);j=Access(v);
              splay(j);
              if (ch[j][1])jia(ch[j][1],x);
              bst[j]=(bst[j]+x)%MOD; 
              Access(u);splay(j);
              if (ch[j][1])jia(ch[j][1],x);
                          }else
            if (c=='*'){x=read();
              Access(u);j=Access(v);
              splay(j);
              if (ch[j][1])che(ch[j][1],x);
              bst[j]=(bst[j]*x)%MOD;
              Access(u);splay(j);
              if (ch[j][1])che(ch[j][1],x);
                           }else
            if (c=='-'){
                  Access(u);j=Access(v);
                  if (j==v)fa[u]=0;else fa[v]=0;
                 x=read();y=read();
                 Access(x);splay(x);rev(x);fa[x]=y;
                          }else
                          {ans=0;
            Access(u);j=Access(v);splay(j);
              ans=(sum[ch[j][1]]+bst[j])%MOD;
            Access(u);splay(j);ans=(ans+sum[ch[j][1]])%MOD;
            printf("%d\n",ans);
  评论这张
 
阅读(16694)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018