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;
}
全部评论

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
nus2201602...:兄弟,你这个简历撕了丢了吧,就是一坨,去找几个项目,理解项目流程,看几遍就是你的了,看看八股就去干了,多看看牛客里别人发出来的简历,对着写,你这写的啥啊,纯一坨
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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