POI2011 Stage 2 Day 2 T2，一道简单的 线段树合并 + 主席树 题目。
题目链接：Luogu P3521/BZOJ 2212/LibreOJ 2163/POI2011 S2D2T2。
题目
题目描述
给一棵 $n$ 个叶子的二叉树，可以交换每个点的左右子树，要求前序遍历叶子的逆序对最少。
数据范围
| 变量 | 数据范围 |
|---|---|
| $n$ | $\leq 2\times 10^5$ |
时空限制
| 题目编号 | 时间限制 | 空间限制 |
|---|---|---|
| Luogu P3521 | $1\text{s}$ | $128\text{MiB}$ |
| BZOJ 2212 | $20\text{s}$ | $259\text{MiB}$ |
| LibreOJ 2163 | $0.16\text{s}$ | $256\text{MiB}$ |
| POI2011 S2D2T2 | $1\text{s}$ | $64\text{MiB}$ |
题解
思路
考虑用 主席树 对权值进行储存，那么对于逆序对，我们可以分成两类。
- 不跨越左右子树的逆序对；
- 跨越左右子树产生的逆序对。
显然，此时交换或不交换都不会改变第一类逆序对的个数，所以我们只需要考虑最小化第二类的逆序对的个数即可。事实上我们只需要处理权值跨过中点的逆序对（类似 归并排序）。
不交换的话是左边那棵树的右半边乘上右边那棵树的的左半边的大小；交换的话则是左边那棵树的左半边乘上左边那棵树的的右半边的大小。
写一个 线段树合并 就可以了。
代码
渐进时间复杂度为 $\Theta(n\log _ 2n)$。
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return res;
}
const int MAXN=200000+5;
namespace SegmentTree{
#define mid ( ( (l) + (r) ) >> 1)
const int MAXSIZE=MAXN*30;
int tot,lson[MAXSIZE],rson[MAXSIZE];
ll sum[MAXSIZE];
int top,S[MAXSIZE];
inline int New(void){
if(top)
return S[top--];
else
return ++tot;
}
inline void del(reg int k){
S[++top]=k;
lson[k]=rson[k]=sum[k]=0;
return;
}
ll ans1,ans2;
inline int merge(reg int u,reg int v){
if(!u||!v)
return u|v;
reg int k=New();
sum[k]=sum[u]+sum[v];
ans1+=sum[rson[u]]*sum[lson[v]];
ans2+=sum[lson[u]]*sum[rson[v]];
lson[k]=merge(lson[u],lson[v]);
rson[k]=merge(rson[u],rson[v]);
del(u),del(v);
return k;
}
inline void Update(reg int &k,reg int l,reg int r,reg int pos){
if(!k)
k=New();
++sum[k];
if(l!=r){
if(pos<=mid)
Update(lson[k],l,mid,pos);
else
Update(rson[k],mid+1,r,pos);
}
return;
}
#undef mid
}
using namespace SegmentTree;
int n;
ll ans;
inline void Solve(reg int &x){
x=0;
reg int val=read();
if(!val){
int lson,rson;
Solve(lson),Solve(rson);
ans1=ans2=0;
x=merge(lson,rson);
ans+=min(ans1,ans2);
}
else
Update(x,1,n,val);
return;
}
int main(void){
n=read();
int root=0;
Solve(root);
printf("%lld\n",ans);
return 0;
}
近期评论