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

相关推荐

牛客刘北:如果暑期实习是27届的话,你要晚一年才会毕业,企业为什么会等你呢?要搞清时间逻辑呀!27届现在实习只能是在暑假实习,这是日常实习,不是暑期实习。所以多去投日常实习吧,暑期实习肯定不会要你的
点赞 评论 收藏
分享
看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗?&nbsp;那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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