线段树合并的话这个noip最难题就是个裸题了。

　　注意merge最后return x，以及如果需要区间查询的话这里还需要up，无数次死于这里。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 300010int n,m,p[N],a[N],fa[N][20],deep[N],ans[N],root[2][N],cnt[2]={ 0},t=0;vector
            
              op1[N],op2[N];struct data{ int to,nxt;}edge[N<<1];struct data2{ int l,r,x;}tree[2][N<<5];void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}void dfs(int k){ for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k][0]) { fa[edge[i].to][0]=k; deep[edge[i].to]=deep[k]+1; dfs(edge[i].to); }}int lca(int x,int y){ if (deep[x]
             
              =deep[y]) x=fa[x][j]; if (x==y) return x; for (int j=19;~j;j--) if (fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j]; return fa[x][0];}int merge(int x,int y,int l,int r,int p){ if (!x||!y) return x|y; if (l==r) {tree[p][x].x+=tree[p][y].x;return x;} int mid=l+r>>1; tree[p][x].l=merge(tree[p][x].l,tree[p][y].l,l,mid,p); tree[p][x].r=merge(tree[p][x].r,tree[p][y].r,mid+1,r,p); return x;}void ins(int &k,int x,int l,int r,int v,int p){ if (!k) k=++cnt[p]; if (l==r) {tree[p][k].x+=v;return;} int mid=l+r>>1; if (x<=mid) ins(tree[p][k].l,x,l,mid,v,p); else ins(tree[p][k].r,x,mid+1,r,v,p);}int query(int k,int l,int r,int x,int p){ if (!k) return 0; if (l==r) return tree[p][k].x; int mid=l+r>>1; if (x<=mid) return query(tree[p][k].l,l,mid,x,p); else return query(tree[p][k].r,mid+1,r,x,p);}void getans(int k){ for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k][0]) { getans(edge[i].to); root[0][k]=merge(root[0][k],root[0][edge[i].to],0,n<<1,0); root[1][k]=merge(root[1][k],root[1][edge[i].to],0,n<<1,1); } for (int i=0;i
              
               0) ins(root[0][k],op1[k][i],0,n<<1,1,0); else ins(root[0][k],-op1[k][i],0,n<<1,-1,0); for (int i=0;i
               
                0) ins(root[1][k],op2[k][i],0,n<<1,1,1); else ins(root[1][k],-op2[k][i],0,n<<1,-1,1); ans[k]+=query(root[0][k],0,n<<1,deep[k]+a[k],0)+query(root[1][k],0,n<<1,deep[k]-a[k]+n,1);}int main(){#ifndef ONLINE_JUDGE freopen("bzoj4719.in","r",stdin); freopen("bzoj4719.out","w",stdout);#endif n=read(),m=read(); for (int i=1;i