正解:线段树合并
解题报告:
今天学了下线段树合并,,,感觉线段树相关的应用什么的还是挺有趣的,今天晚上可能会整理一下$QAQ?$
然后直接看这道题
现在考虑对一个节点$nw$,现在已经分别处理出它的$ls$和$rs$的最少逆序对个数了,然后现在考虑要不要交换呢$QAQ$
显然不管$nw$节点的左右子树内部是怎么排列的,他们整体对外部的贡献是不变的,所以我们只要考虑内部的逆序对个数怎么样尽量小$QAQ$
这里就可以考虑对每个节点分别开一个权值线段树,然后逆序对的话可以直接在merge的时候做,树状数组都能有的功能线段树肯定也能有昂$QAQ$
等下放代码$QAQ!$
对了还要说个,就是,它的读入很鬼畜,,,又麻油翻译,,,大概就是说,它是给的一个递归形式的输入,如果是$0$,说明有左右节点,否则为叶子节点
然后这个可以用$dfs$递归读入,而且刚刚好在读入的时候顺便一起做完了$QAQ$
最后夸一下,这题,特别好,它好就好在,,,我我我$RE\&MLE$了七十多次,,,开大点儿就$MLE$小了又会$RE$,,,调了半天发现是我代码中数据类型$int$和$long\ long$的定义有问题$QAQ$
这题动画,唯一要用ll的就是逆序对的个数,其他都不要开昂$QAQ$
然后还有就是,如果有这么一句话:$a=solve();$其中a是个$int$,函数的定义写的返回类型是$ll$,这样写可能就会有一些莫名其妙的后果,所以一定要注意对应$QAQ$!如果$a$是个$int$在定义$solve$的时候一定记得定义成$int$!
没了$QAQ$
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register
#define gc getchar()
#define ll long long int n,nod_cnt;
ll as,ret1,ret2;
struct sgtr{int ls,rs,sz;}tr[]; il int read()
{
rg char ch=gc;rg int x=;rg bool y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
int buildnw(rg int l,rg int r,rg int dat)
{
tr[++nod_cnt].sz=;if(l==r)return nod_cnt;
rg int mid=(l+r)>>,nw=nod_cnt;if(dat<=mid)tr[nod_cnt].ls=buildnw(l,mid,dat);else tr[nod_cnt].rs=buildnw(mid+,r,dat);return nw;
}
int merge(rg int l,rg int r,rg int nw1,rg int nw2)
{
if(!nw1 || !nw2)return nw1+nw2;
if(l==r)return tr[nw1].sz=tr[nw1].sz+tr[nw2].sz,nw1;
rg int mid=(l+r)>>;
ret1+=1ll*tr[tr[nw1].rs].sz*tr[tr[nw2].ls].sz;ret2+=1ll*tr[tr[nw1].ls].sz*tr[tr[nw2].rs].sz;
tr[nw1].ls=merge(l,mid,tr[nw1].ls,tr[nw2].ls);tr[nw1].rs=merge(mid+,r,tr[nw1].rs,tr[nw2].rs);tr[nw1].sz=tr[nw1].sz+tr[nw2].sz;return nw1;
}
int rd()
{
rg int tmp=read();
if(tmp)return buildnw(,n,tmp);
rg int nw=merge(,n,rd(),rd());as+=min(ret1,ret2);ret1=ret2=;return nw;
} int main()
{
n=read();rd();printf("%lld\n",as);
return ;
}
放下代码QAQ