poj3468  裸线段树。因为在熟悉splay 所以就用splay交了一发。。。开始用的scanf()!==2 居然TLE了。。。然后我就当单组测试数据做的 然后就过了  囧TZ  

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define rt ch[root][1]#define lrt ch[rt][0]#define ls ch[x][0]#define rs ch[x][1]#define inf 0x3f3f3f3fconst int maxn=100100;int root,top;//root为新建节点时的根节点int ch[maxn][2],f[maxn];long long sz[maxn],num[maxn],val[maxn],sum[maxn],add[maxn];int n,m;//ch[x][0],ch[x][1]:x的左右儿子,f[x]:x的父亲节点,val[x]:x的值,sz[x]以x为根的子树的节点个数inline void pushup(int x){ sz[x]=sz[ls]+sz[rs]+1; sum[x]=sum[ls]+sum[rs]+val[x]; //维护其他信息}inline void pushdown(int x){ if(add[x]) { val[x]+=add[x]; add[ls]+=add[x]; add[rs]+=add[x]; sum[ls]+=(long long)(sz[ls]*add[x]); sum[rs]+=(long long)(sz[rs]*add[x]); add[x]=0; } //维护其他信息}inline void link(int y,int x,int d)//把节点y的(左或右)儿子设为x{ f[x]=y; ch[y][d]=x;}inline int is(int x)//判断x为左儿子0还是右儿子1{ return ch[f[x]][1]==x;}inline void rotate(int x,int d){ int y=f[x]; int z=f[y]; pushdown(y); pushdown(x); link(y,ch[x][d],!d); if(z) link(z,x,is(y)); f[x]=z; link(x,y,d); pushup(y);}inline void zag(int x){ rotate(x,0);}inline void zig(int x){ rotate(x,1);}inline void splay(int x,int goal=0)//第二个元素没有传参就默认为0，splay到0即将该节点旋转到根//将根为r的子树调整到x的父节点为goal的位置{ pushdown(x); while(f[x]!=goal) { int y=f[x]; int z=f[y]; if(z==goal) { rotate(x,!is(x)); break; } if(ch[z][0]==y) { if(ch[y][0]==x) zig(y),zig(x); else zag(x),zig(x); } else { if(ch[y][1]==x) zag(y),zag(x); else zig(x),zag(x); } } if(goal==0) root=x; pushup(x);}//splay操作一般不做改动inline void newnode(int &x,int father,long long v){ x=++top; f[x]=father; val[x]=v; add[x]=0; ls=rs=0; sz[x]=0; //.....按题意建立信息}inline bool insert(int v){ int x=root; while(ch[x][val[x]
           
            r) return ; int mid=(l+r)>>1; newnode(x,y,num[mid]); build(ls,x,l,mid-1); build(rs,x,mid+1,r); pushup(x);}inline void init(int n){ root=top=0; ch[0][0]=ch[0][1]=f[0]=val[0]=add[0]=sz[0]=sum[0]=0; newnode(root,0,0); newnode(rt,root,0); sz[root]=2; for(int i=0; i