luogu P3521 [POI2011]ROT-Tree Rotations

思路

合并时候统计逆序对贡献

代码

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define ll long long
using namespace std;
const int maxn=2e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,cnt;
ll ans,ans1,ans2;
struct edge {
    int ch[2],siz;
}e[maxn*30];
void build(int &now,int l,int r,int k) {
    now=++cnt;e[now].siz++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(k<=mid) build(e[now].ch[0],l,mid,k);
    else build(e[now].ch[1],mid+1,r,k);
}
int merge(int x,int y) {
    if(!x || !y) return x+y;
    e[x].siz+=e[y].siz;
    ans1+=1LL*e[e[x].ch[0]].siz*e[e[y].ch[1]].siz;
    ans2+=1LL*e[e[x].ch[1]].siz*e[e[y].ch[0]].siz;
    e[x].ch[0]=merge(e[x].ch[0],e[y].ch[0]);
    e[x].ch[1]=merge(e[x].ch[1],e[y].ch[1]);
    return x;
}
int dfs() {
    int tmp=read(),x=0;
    if(!tmp) {
        int ls=dfs(),rs=dfs();
        x=merge(ls,rs);
        ans+=min(ans1,ans2);
        ans1=ans2=0;
    }
    else build(x,1,n,tmp);
    return x;
}
int main() {
    n=read();
    dfs();
    cout<<ans<<"\n";
    return 0;
}
全部评论

相关推荐

点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务