P3521 【[POI2011]ROT-Tree Rotations】

看到大佬们都在说输入毒瘤

但是因为输入是从上往下递归的

合并多颗线段树也是递归的 （先合并下面的再往上）

所以可以输入的时候就求答案了

大概就是

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;
}

卡空间卡了好久（我太菜了不会写内存池