社区讨论

关于本题的另类解法

FFigo17
P3521[POI 2011] ROT-Tree Rotations参与者 4已保存回复 9

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@lo8tvnph
此快照首次捕获于
2023/10/28 00:28
2 年前
此快照最后确认于
2023/10/28 00:28
2 年前
查看原帖
rt
没学过线段树合并，所以不知道和题解有没有重复。

声明：只是单纯地分享一下考场思路，没有任何其他企图

对于一个节点 fafa 及其左儿子 LL，右儿子 RR，发现各自子树内的逆序对可以递归下去贪心，在 fafa 这里只需要考虑“跨过”fafa 的逆序对即可（也就是分治）。
考虑启发式分治，每次选 sizsiz 小的那个子树用树状数组计算逆序对数 cntcnt，将答案加上 min(cnt,sizL×sizR−cnt)min( cnt , siz_L \times siz_R -cnt )。
然后启发式合并，用 STL::vector 记录子树内的子节点；并将 fafa 继承大儿子的树状数组。
复杂度是丑陋的 O(nlog⁡2n)O(n \log^2n)，但跑得飞快，平均30毫左右。
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;

inline int read(){
	int s=0;char c=getchar();
	while(c<48||c>57) c=getchar();
	while(c>=48&&c<=57) s=(s<<1)+(s<<3)+c-48,c=getchar();
	return s;
}

int num;

int n,top;
ll ans;
int L[500005],R[500005],siz[500005];
int v[500005],pos[500005];
vector<int> son[500005];

int init(){
	int p=++top,now=read();
	if(now){
		siz[p]=1,v[p]=now;
		pos[p]=p,son[p].push_back(v[p]);
		return p;
	}
	L[p]=init(),R[p]=init();
	if(siz[L[p]]<siz[R[p]]) swap(L[p],R[p]);
	siz[p]+=siz[L[p]],siz[p]+=siz[R[p]];
	return p;
}

int tre[200005];
int lowbit(int x){return x&-x;}
void add(int x,int y){while(x<=n) tre[x]+=y,x+=lowbit(x);}
int find(int x){int s=0;while(x>0) s+=tre[x],x-=lowbit(x);return s;}

void dfs(int x){
	int l=L[x],r=R[x];
	if(!l||!r){
		add(v[x],1);
		return;
	}
	
	ll cnt=0;int pl,pr;
	dfs(r),pr=pos[r]; for(int i=0;i<son[pr].size();i++) add(son[pr][i],-1);
	dfs(l),pl=pos[l]; for(int i=0;i<son[pr].size();i++) cnt+=siz[l]-find(son[pr][i]);
	
	ans+=min(cnt,(ll)siz[l]*siz[r]-cnt);
	for(int i=0;i<son[pr].size();i++) add(son[pr][i],1),
		son[pl].push_back(son[pr][i]);
	pos[x]=pl;
}

int main(){

	n=read();
	init();
	dfs(1);
	
	printf("%lld",ans);
	
	return 0;
}
代码也丑，希望对大家有帮助吧。
不过估计讨论版没人会理 吧 。
吃灰o(╥﹏╥)o

回复

共 9 条回复，欢迎继续交流。

正在加载回复...