[HNOI2018] 转盘 [线段树]

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

近期博客可能停更。

Solution

https://www.cnblogs.com/NaVi-Awson/p/8918958.html

以下做一些补充。

一是当两个区间合并的时候,所谓可以直接用左区间 $lx$ 的左儿子的答案并不是指 $val_{lson(lx)}$,而是指 $val_{lx}$。

二是请不要忘记整个线段树是想要做什么。

三是为什么说这题和楼房重建很像,因为想想我们要求的东西:

i  1 2 3 4 5 6
ai 3 2 3 2 2 1

我们对它做一个后缀和看看?

i  1 2 3 4 5 6
Si 3 3 3 2 2 1

那么我们所需要考虑的只有连续的一段区间的最左边的答案(即按上面的例子只有 1,4,6 可能成为答案),因此启发我们维护一段连续向上的区间。

但是呢,个人认为事实上的实现跟这个确实没什么关系,只是方法上相似而已。即分类讨论,用 $\log$ 的时间 pushup。

Code

// Code by ajcxsu
// Problem: circle

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

const int N=2e5+10;
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
int ma[N<<2], mi[N<<2], t[N];
int pup2(int a, int l, int r, int mx) { // merge a to z (mx=ma[z])
    if(l==r) return l+max(ma[a], mx);
    int mid=(l+r)>>1;
    if(ma[rs(a)]>=mx) return min(mi[a], pup2(rs(a), mid+1, r, mx));
    else return min(mid+1+mx, pup2(ls(a), l, mid, mx));
}
void pup(int x, int l, int mid) {
    ma[x]=max(ma[ls(x)], ma[rs(x)]),
    mi[x]=pup2(ls(x), l, mid, ma[rs(x)]);
}
void build(int x, int l, int r) {
    if(l==r) { ma[x]=t[l], mi[x]=l+t[l]; return; }
    int mid=(l+r)>>1;
    build(ls(x), l, mid), build(rs(x), mid+1, r);
    pup(x, l, mid);
}
void updata(int x, int l, int r, int d) {
    if(l==r) { ma[x]=t[l], mi[x]=l+t[l]; return; }
    int mid=(l+r)>>1;
    if(d<=mid) updata(ls(x), l, mid, d);
    else updata(rs(x), mid+1, r, d);
    pup(x, l, mid);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m, p;
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++) cin>>t[i], t[i+n]=t[i]-i-n, t[i]-=i;
    build(1, 1, n<<1);
    int lst;
    cout<<(lst=mi[1]+n-1)<<'\n';
    int x, y;
    while(m--) {
        if(!p) lst=0;
        cin>>x>>y, x^=lst, y^=lst; t[x]=y-x, t[x+n]=y-x-n;
        updata(1, 1, n<<1, x), updata(1, 1, n<<1, x+n);
        cout<<(lst=mi[1]+n-1)<<'\n';
    }
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/sol-hnoi-2018-circle.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