Algorithm is introduced
Give two line segment trees and merge them into one.
Recursively merge the two line segment trees. Use two Pointers p,qp,qp,q to start at the root of two line segment trees. For a node, if p=0p=0p=0 or Q =0q=0q=0, that is to say, one of the two line segment trees does not have this point, PPP or QQQ that is not 000 is directly taken as the new node of the merged line segment tree. If both trees exist for a point, recursively merge their subtrees and update the node information. In addition, for leaf nodes, simply merge.
sample
P3605 [USACO17JAN]Promotion Counting
Train of thought
Although tree arrays are particularly easy to write, they’re still useful for practice. First discretize niuniu’s ability value, maintain a weight line segment tree for each node, start from leaf nodes and merge the line segment tree of each child node, directly query the number of weight line segment tree larger than their own ability value, and then maintain themselves into the answer.
code
#include<bits/stdc++.h>
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
#definebl(u,i) for(int i=head[u]; i; i=e[i].nxt)
#define en puts("")
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll>
typedef long long ll;
typedef double db;
using namespace std;
const ll INF=0x3f3f3f3f;
void read(a) {}
void OP(a) {}
void op(a) {}
template <typename T, typename. T2>inline void read(T &_, T2 &... oth)
{
int__ =0; _ =0;
char ch=getchar(a);while(!isdigit(ch))
{
if(ch==The '-') __ =1;
ch=getchar(a); }while(isdigit(ch))
{
_=_*10+ch- 48;
ch=getchar(a); } _ = __? - _ : _;read(oth...) ; }template <typename T>
void Out(T _)
{
if(_ <0)
{
putchar(The '-'); _ = - _; }if(_ > =10)
Out(_ /10);
putchar(_ %10+'0');
}
template <typename T, typename. T2>inline void OP(T _, T2... oth)
{
Out(_).putchar('\n');
OP(oth...) ; }template <typename T, typename. T2>inline void op(T _, T2... oth)
{
Out(_).putchar(' ');
op(oth...) ; }/ * # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # * /
const ll N=1E5+10;
ll n,fa,tot,cnt;
ll head[N],ans[N],a[N],root[N];
struct Node{
ll l,r,val;
}t[20*N];
struct Edge{
ll nxt,to,w;
}e[N];
vector<ll> ve;
void add_edge(ll u,ll v,ll w,int flag)
{
e[++tot]=(Edge){head[u],v,w};
head[u]=tot;
if(flag)
add_edge(v,u,w,0);
}
void update(ll p)
{
t[p].val=t[t[p].l].val+t[t[p].r].val;
}
void merge(ll &p,ll q,ll l,ll r)
{
if(! p || ! q) { p=p|q;return;
}
if(l==r)
{
t[p].val+=t[q].val;
return;
}
ll mid=(l+r)>>1;
merge(t[p].l,t[q].l,l,mid);
merge(t[p].r,t[q].r,mid+1,r);
update(p);
}
ll query(ll p,ll l,ll r,ll al,ll ar)
{
if(al<=l && ar>=r)
return t[p].val;
ll mid=(l+r)>>1;
ll ret=0;
if(al<=mid)
ret+=query(t[p].l,l,mid,al,ar);
if(ar>mid)
ret+=query(t[p].r,mid+1,r,al,ar);
return ret;
}
void add(ll &p,ll l,ll r,ll pos,ll val)
{
if(! p) p=++cnt;if(l==r)
{
t[p].val+=val;
return;
}
ll mid=(l+r)>>1;
if(pos<=mid)
add(t[p].l,l,mid,pos,val);
else
add(t[p].r,mid+1,r,pos,val);
update(p);
}
void dfs(ll u)
{
root[u]=++cnt;
bl(u,i)
{
ll v=e[i].to;
dfs(v);
merge(root[u],root[v],1,n);
}
ans[u]=query(root[u],1,n,a[u]+1,n);
add(root[u],1,n,a[u],1);
}
int main(a)
{
read(n);
rep(i,1,n)
{
read(a[i]);
ve.emplace_back(a[i]);
}
rep(i,2,n)
{
read(fa);
add_edge(fa,i,0.0);
}
sort(ve.begin(),ve.end());
ve.erase(unique(ve.begin(),ve.end()),ve.end());
rep(i,1,n)
a[i]=lower_bound(ve.begin(),ve.end(),a[i])-ve.begin() +1;
dfs(1);
rep(i,1,n)
OP(ans[i]);
}
Copy the codeP3521 [POI2011]ROT-Tree Rotations
Train of thought
First, it can be found that swapping left and right subtrees only affects the number of inversion pairs between left and right subtrees, but does not affect the number of inversion pairs within the subtrees and between the ancestor subtrees. Therefore, for each node, it can be greedy to take the minimum value of the inversion pairs between swapping left and right subtrees and not swapping.
How do you quickly find the number of inversions between the left and right subtrees? A weight line segment tree was built for each node, and the answers contributed by this node were maintained while the line segment trees corresponding to uuU subtrees were merged. Suppose PPP refers to the segment tree corresponding to the left subtree, and QQQ points to the right, because the subscript of the number in the PPP tree must be smaller than that in QQQ, so the number of inverse pairs before the swap is the product of the value of the right PPP subtree and the value of the left QQQ subtree, and the swap is PPP left times QQQ right.
code
#include<bits/stdc++.h>
#definerep(i,st,ed) for(int i=st; i<=ed; ++i)
#definebl(u,i) for(int i=head[u]; i; i=e[i].nxt)
#define en puts("")
#define LLM LONG_LONG_MAX
#define LLm LONG_LONG_MIN
#define pii pair<ll,ll>
typedef long long ll;
typedef double db;
using namespace std;
const ll INF=0x3f3f3f3f;
void read(a) {}
void OP(a) {}
void op(a) {}
template <typename T, typename. T2>inline void read(T &_, T2 &... oth)
{
int__ =0; _ =0;
char ch=getchar(a);while(!isdigit(ch))
{
if(ch==The '-') __ =1;
ch=getchar(a); }while(isdigit(ch))
{
_=_*10+ch- 48;
ch=getchar(a); } _ = __? - _ : _;read(oth...) ; }template <typename T>
void Out(T _)
{
if(_ <0)
{
putchar(The '-'); _ = - _; }if(_ > =10)
Out(_ /10);
putchar(_ %10+'0');
}
template <typename T, typename. T2>inline void OP(T _, T2... oth)
{
Out(_).putchar('\n');
OP(oth...) ; }template <typename T, typename. T2>inline void op(T _, T2... oth)
{
Out(_).putchar(' ');
op(oth...) ; }/ * # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # * /
const ll N=2E5+10;
ll n,ans,ans1,ans2,cnt;
struct Node
{
ll l,r,val;
}t[20*N];
void add(ll &p,ll l,ll r,ll val)
{
if(! p) p=++cnt; ++t[p].val;if(l==r)
return;
ll mid=(l+r)>>1;
if(val<=mid)
add(t[p].l,l,mid,val);
else
add(t[p].r,mid+1,r,val);
}
void merge(ll &p,ll q)
{
if(! p || ! q) { p=p|q;return;
}
t[p].val+=t[q].val;
ans1+=t[t[p].r].val*t[t[q].l].val;
ans2+=t[t[p].l].val*t[t[q].r].val;
merge(t[p].l,t[q].l);
merge(t[p].r,t[q].r);
}
void dfs(ll &u)
{
ll lc,rc,x;
u=0;
read(x);
if(! x) {dfs(lc);
dfs(rc);
u=lc;
ans1=ans2=0;
merge(u,rc);
ans+=min(ans1,ans2);
}
else
add(u,1,n,x);
}
int main(a)
{
read(n);
ll tmp=0;
dfs(tmp);
OP(ans);
}
Copy the code