线段树划分时按照子树的size平分

听说会变成一个log的,实际效果不明

BZOJ1036

#include 
     
      #include 
      
       #include 
       
        #define LL long long using namespace std;   struct treenode{      LL sum,maxi;      int mid,l,r,lc,rc;  }tr[400001];   int size[200001],nd[200001],next[400001],dep[200001],des[400001],fa[200001];  int heav[200001],top[200001],ori[200001],cnt,id[200001];  int a[200001],root[200001],n,t1,t2,dsize[200001];  char st[201];   void addedge(int x,int y){     next[++cnt]=nd[x];des[cnt]=y;nd[x]=cnt;  }   void dfs1(int po){      size[po]=1;int maxi=0;      for (int p=nd[po];p!=-1;p=next[p])        if (!dep[des[p]]){            dep[des[p]]=dep[po]+1;            fa[des[p]]=po;            dfs1(des[p]);            size[po]+=size[des[p]];            if (size[des[p]]>maxi){              maxi=size[des[p]];              heav[po]=des[p];        }      }  }   void dfs2(int po,int tp){      top[po]=tp;ori[++cnt]=po;id[po]=cnt;dsize[po]=1;      if (heav[po]) dfs2(heav[po],tp);      for (int p=nd[po];p!=-1;p=next[p])        if (des[p]!=heav[po]&&dep[des[p]]==dep[po]+1){          dfs2(des[p],des[p]);                    dsize[po]+=size[des[p]];        }          }   void update(int po){    tr[po].maxi=max(tr[tr[po].lc].maxi,tr[tr[po].rc].maxi);    tr[po].sum=tr[tr[po].lc].sum+tr[tr[po].rc].sum;  }   void build(int l,int r){      tr[++cnt].l=l;tr[cnt].r=r;      if (l==r){        tr[cnt].sum=tr[cnt].maxi=a[ori[l]];      return;        }        int totd=0,mini=1e9,t=0;for (int i=l;i<=r;i++) totd+=dsize[ori[i]];    for (int i=l;i
        
         tr[po].mid)        ret+=segsum(tr[po].rc,max(tr[po].mid+1,tarl),tarr);      return(ret);  }   LL quesum(int x,int y){      LL ret=0;      while (top[x]!=top[y]){        if (dep[top[x]]
         
          tr[po].mid)      ret=max(segmax(tr[po].rc,max(tr[po].mid+1,tarl),tarr),ret);      return(ret);  }   LL quemax(int x,int y){      LL ret=-1e9;      while (top[x]!=top[y]){        if (dep[top[x]]