[Poi2011]Tree Rotations线段树合并-白红宇

[Poi2011]Tree Rotations线段树合并

阅读量：5126 次

发布时间：2019-06-13

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

整理一下线段树合并的思路，大体是给每个树上节点分配一个根编号建一棵log长的权值线段树，一开始树上只有这个树节点的节点权

merge两个树节点的时候，对于当前合并的值域（例如两棵线段树的表示1到n/2的节点），

任意取两棵树中的一个节点编号，空的返回另一个，把树丰满起来，同时更新一下计数就可以了

#include
     
        //#pragma comment(linker, "/STACK:1024000000,1024000000")   #include
      
         #include
       
          #include
        
           #include
         
            #include
          
            #include
           
             #include
            
             #include
             
               #include
               #include
               
                 #include
                
                  #include
                 
                  using namespace std; //#define ll long long #define ull unsigned long long#define pb push_back #define FOR(a) for(int i=1;i<=a;i++) #define sqr(a) (a)*(a)#define dis(a,b) sqrt(sqr(a.x-b.x)+sqr(a.y-b.y))ll qp(ll a,ll b,ll mod){ ll t=1;while(b){if(b&1)t=t*a%mod;b>>=1;a=a*a%mod;}return t;}struct DOT{ll x;ll y;};inline void read(int &x){int k=0;char f=1;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())k=k*10+c-'0';x=k*f;} const int dx[4]={0,0,-1,1};const int dy[4]={1,-1,0,0};const int inf=0x3f3f3f3f; const ll Linf=0x3f3f3f3f3f3f3f3f;const ll mod=1e9+7;;const int maxn=8e6+34;int RT;int n,a[maxn];int seg;int tree[maxn],lson[maxn],rson[maxn];int root[maxn];vector
                  
                   G[maxn];int Time;void pushup(int rt){tree[rt]=tree[lson[rt]]+tree[rson[rt]];}void build(int &rt,int l,int r,int pos){ rt=++seg; if(l==r){ tree[rt]=1;return; } int m=l+r>>1; if(pos<=m)build(lson[rt],l,m,pos); else build(rson[rt],m+1,r,pos); pushup(rt);}ll ans,ans1,ans2;int merge(int x,int y){ if(!x)return y;if(!y)return x; ans1+=1ll*tree[rson[x]]*tree[lson[y]]; ans2+=1ll*tree[lson[x]]*tree[rson[y]]; lson[x]=merge(lson[x],lson[y]); rson[x]=merge(rson[x],rson[y]); pushup(x); return x;}void dfs(int u){ if(a[u])return; dfs(G[u][0]);dfs(G[u][1]); ans1=ans2=0; root[u]=merge(root[G[u][0]],root[G[u][1]]); ans+=min(ans1,ans2);}void init(int &rt){ rt=++Time;scanf("%d",&a[Time]); if(a[Time])return; G[rt].pb(0);G[rt].pb(0); init(G[rt][0]); init(G[rt][1]);}int main(){ scanf("%d",&n); init(RT); for(int i=1;i<=Time;i++){ if(a[i])build(root[i],1,n,a[i]); } dfs(RT); printf("%lld\n",ans);}