兰州网站建设科技公司,小程序加盟招商代理,用花生做网站,苏州微网站制作整理一下线段树合并的思路#xff0c;大体是给每个树上节点分配一个根编号建一棵log长的权值线段树#xff0c;一开始树上只有这个树节点的节点权merge两个树节点的时候#xff0c;对于当前合并的值域#xff08;例如两棵线段树的表示1到n/2的节点#xff09;#xff0c;… 整理一下线段树合并的思路大体是给每个树上节点分配一个根编号建一棵log长的权值线段树一开始树上只有这个树节点的节点权merge两个树节点的时候对于当前合并的值域例如两棵线段树的表示1到n/2的节点任意取两棵树中的一个节点编号空的返回另一个把树丰满起来同时更新一下计数就可以了#includebits/stdc.h
//#pragma comment(linker, /STACK:1024000000,1024000000)
#includestdio.h
#includealgorithm
#includequeue
#includestring.h
#includeiostream
#includemath.h
#includestack
#includeset
#includemap
#includevector
#includeiomanip
#includebitset
using namespace std; //#define ll long long
#define ull unsigned long long
#define pb push_back
#define FOR(a) for(int i1;ia;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 t1;while(b){if(b1)tt*a%mod;b1;aa*a%mod;}return t;
}
struct DOT{ll x;ll y;};
inline void read(int x){int k0;char f1;char cgetchar();for(;!isdigit(c);cgetchar())if(c-)f-1;for(;isdigit(c);cgetchar())kk*10c-0;xk*f;}
const int dx[4]{0,0,-1,1};
const int dy[4]{1,-1,0,0};
const int inf0x3f3f3f3f;
const ll Linf0x3f3f3f3f3f3f3f3f;
const ll mod1e97;;const int maxn8e634;int RT;
int n,a[maxn];int seg;
int tree[maxn],lson[maxn],rson[maxn];
int root[maxn];vectorintG[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){rtseg;if(lr){tree[rt]1;return;}int mlr1;if(posm)build(lson[rt],l,m,pos);else build(rson[rt],m1,r,pos);pushup(rt);
}
ll ans,ans1,ans2;int merge(int x,int y){if(!x)return y;if(!y)return x;ans11ll*tree[rson[x]]*tree[lson[y]];ans21ll*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]);ans1ans20;root[u]merge(root[G[u][0]],root[G[u][1]]);ansmin(ans1,ans2);
}void init(int rt){rtTime;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 i1;iTime;i){if(a[i])build(root[i],1,n,a[i]);}dfs(RT);printf(%lld\n,ans);
} 转载于:https://www.cnblogs.com/Drenight/p/8611191.html
