LP3521 [POI2011]ROT-Tree Rotations

Author Avatar
空気浮遊 2018年11月01日
  • 在其它设备中阅读本文章
  • 线段树合并
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

Problem

https://www.luogu.org/problemnew/show/P3521

Solution

这玩意怎么这么像我考过的一道...

现在想想我那东西好像不太好用这东西优化 emm

这边就是计算左右子树互相贡献的最小值之和就行了

也是我第一次打线段树合并纪念一下 emm

Code

// Code by ajcxsu
// Problem: ROT

#include<bits/stdc++.h>
using namespace std;

struct Node *nil; 
struct Node {
    int val;
    Node *ls, *rs;
    Node(int v=0):val(v) { ls=rs=nil; }
} ;
void ini() { nil=new Node(), nil->ls=nil->rs=nil; }

void updata(Node *&x, int l, int r, int d) {
    Node *nd=new Node(); *nd=*x, x=nd, x->val++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(d<=mid) updata(x->ls, l, mid, d);
    else updata(x->rs, mid+1, r, d);
}
typedef long long ll;
ll na, nb;
void Merge(Node *&x, Node *a, Node *b, int l, int r) {
    if(a==nil) { x=b; return; }
    if(b==nil) { x=a; return; }
    Node *nd=new Node(); *nd=*x, x=nd, x->val=a->val+b->val;
    na+=1ll*a->rs->val*b->ls->val, nb+=1ll*b->rs->val*a->ls->val; 
    int mid=(l+r)>>1;
    Merge(x->ls, a->ls, b->ls, l, mid);
    Merge(x->rs, a->rs, b->rs, mid+1, r);
    delete a;
    delete b;
}

int n;
ll ans;
Node *dfs() {
    Node *ln, *rn, *ret=nil;
    int x;
    cin>>x;
    if(!x) {
        ln=dfs(), rn=dfs();
        na=nb=0; Merge(ret, ln, rn, 1, n);
        ans+=min(na, nb);
    }
    else updata(ret, 1, n, x);
    return ret;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), ini();
    cin>>n;
    dfs();
    cout<<ans<<endl;
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/sol-luogu-3521.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • May 2025 1
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 31
    • August 2018 18
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 281
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material