看到大佬们都在说输入毒瘤
但是因为输入是从上往下递归的
合并多颗线段树也是递归的 （先合并下面的再往上）
所以可以输入的时候就求答案了
大概就是
int dfs(){ int x; scanf("%d",&x); if(x!=0) return new_node(x);//叶子节点就直接加一个点 return merge(dfs(),dfs());//不然就递归合并两个子树 } int main(){ cin>>n; cout<<tree[dfs()].ans; }然后补全new_node()和merge()两个函数 就没了
#include <bits/stdc++.h> #define N 50000100 #define mid ((l+r)>>1) using namespace std; int n,nn; struct node{ int lson,rson,sum; long long ans; }tree[N]; inline int new_node(int x,int l=1,int r=n){ int k=++nn; tree[nn].sum=1; if(l==r) return nn; if(x<=mid) tree[nn].lson=new_node(x,l,mid); else tree[nn].rson=new_node(x,mid+1,r); return k; } long long res0,res1; inline int merge(int x,int y,int l=1,int r=n){ if(!y||!x){ res0=res1=0; return x|y; } tree[x].ans=tree[x].ans+tree[y].ans; long long aa=1ll*tree[tree[x].rson].sum*tree[tree[y].lson].sum,bb=1ll*tree[tree[x].lson].sum*tree[tree[y].rson].sum; tree[x].lson=merge(tree[x].lson,tree[y].lson,l,mid);//合并左子树 aa+=res0; bb+=res1; tree[x].rson=merge(tree[x].rson,tree[y].rson,mid+1,r);//合并右子树 aa+=res0; bb+=res1; tree[x].ans+=min(aa,bb); tree[x].sum=tree[tree[x].lson].sum+tree[tree[x].rson].sum; res0=aa,res1=bb; return x; } inline int dfs(){ int x; scanf("%d",&x); if(x!=0) return new_node(x); return merge(dfs(),dfs()); } int main(){ cin>>n; cout<<tree[dfs()].ans; }卡空间卡了好久（我太菜了不会写内存池
