专栏首页数据结构与算法BZOJ4552: [Tjoi2016&Heoi2016]排序(线段树 二分)

BZOJ4552: [Tjoi2016&Heoi2016]排序(线段树 二分)

题意

题目链接

Sol

神仙二分Orz

首先二分一个答案,表示假设询问的位置为$x$,把$>= x$的看成$1$,$< x$的看成$0$

对形成的$0/1$序列模拟,线段树维护。

最后根据询问位置上的数缩小答案范围

这题的单调性不好想,但是证起来其实也挺显然的,考虑如果答案$x$最后对应的值为$1$,那么$<x$的值最后对应的答案也一定为$1$

#include<bits/stdc++.h>
#define Pair pair<int, int> 
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
const int MAXN = 4e6 + 10, INF = 1e9 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, Q;
int a[MAXN], b[MAXN], opt[MAXN], L[MAXN], R[MAXN];
#define ls k << 1
#define rs k << 1 | 1
struct Node {
    int l, r, siz, tag, cnt[2];
}T[MAXN];   
Pair operator + (const Pair &a, const Pair &b) {
    return MP(a.fi + b.fi, a.se + b.se);
}
void update(int k) {
    for(int i = 0; i <= 1; i++) T[k].cnt[i] = T[ls].cnt[i] + T[rs].cnt[i];
}
void ps(int k, int val) {
    T[k].cnt[0] = T[k].cnt[1] = 0;
    T[k].cnt[val] = T[k].siz;
    T[k].tag = val;
}
void pushdown(int k) {
    if(T[k].tag == -1) return ;
    ps(ls, T[k].tag); ps(rs, T[k].tag);
    T[k].tag = -1;
}
void Build(int k, int ll, int rr) {
    T[k].l = ll; T[k].r = rr; T[k].siz = rr - ll + 1; T[k].tag = -1; T[k].cnt[0] = T[k].cnt[1] = 0;
    if(ll == rr) {T[k].cnt[b[ll]]++; return ;}
    int mid = ll + rr >> 1;
    Build(ls, ll, mid); Build(rs, mid + 1, rr);
    update(k);
}
Pair Query(int k, int ll, int rr) {
    if(ll <= T[k].l && T[k].r <= rr) return MP(T[k].cnt[0], T[k].cnt[1]);
    int mid = T[k].l + T[k].r >> 1;
    pushdown(k);
    if(ll > mid) return Query(rs, ll, rr);
    if(rr <= mid) return Query(ls, ll, rr);
    return Query(ls, ll, rr) + Query(rs, ll, rr);
}
void Mem(int k, int ll, int rr, int val) {
    if(ll <= T[k].l && T[k].r <= rr) {
        ps(k, val); return ;
    }
    pushdown(k);
    int mid = T[k].l + T[k].r >> 1;
    if(ll <= mid) Mem(ls, ll, rr, val);
    if(rr >  mid) Mem(rs, ll, rr, val);
    update(k);
}
int Point(int k, int pos) {
    if(T[k].l == T[k].r) {
        if(T[k].cnt[1]) return 1;
        else return 0;
    }
    pushdown(k);
    int mid = T[k].l + T[k].r >> 1;
    if(pos <= mid) return Point(ls, pos);
    else return Point(rs, pos);
}
void dfs(int k) {
    if(T[k].l == T[k].r) {
        if(T[k].cnt[1]) printf("1 ");
        else printf("0 ");
        return ;
    }
    pushdown(k);
    dfs(ls); dfs(rs);
}
bool check(int val) {
    for(int i = 1; i <= N; i++) b[i] = (a[i] >= val);
    Build(1, 1, N);
    //dfs(1); puts("");
    for(int i = 1; i <= M; i++) {
        Pair now = Query(1, L[i], R[i]);
        if(opt[i] == 0) Mem(1, L[i], L[i] + now.fi - 1, 0), Mem(1, L[i] + now.fi, R[i], 1);
        else Mem(1, L[i], L[i] + now.se - 1, 1), Mem(1, L[i] + now.se, R[i], 0);
    //  dfs(1); puts("");
    }
    return Point(1, Q);
}
main() {
    N = read(); M = read();
    for(int i = 1; i <= N; i++) a[i] = read();
    for(int i = 1; i <= M; i++) opt[i] = read(), L[i] = read(), R[i] = read();
    Q = read();
    int l = 1, r = N, ans = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    printf("%d", ans);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 洛谷P3437 [POI2006]TET-Tetris 3D(二维线段树 标记永久化)

    对于这题来说,因为有修改操作,我们需要在外层线段树上也打标记,而且标记的形式是对一段区间赋值。所以我们对每个标记需要开线段树来维护更改的位置

    attack
  • 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

    那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列,显然这个序列要满足最后一个\(\mid 1\)要在\(\& 0\)之后

    attack
  • BZOJ3262: 陌上花开(cdq分治)

    第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。

    attack
  • 洛谷P3437 [POI2006]TET-Tetris 3D(二维线段树 标记永久化)

    对于这题来说,因为有修改操作,我们需要在外层线段树上也打标记,而且标记的形式是对一段区间赋值。所以我们对每个标记需要开线段树来维护更改的位置

    attack
  • 栈缓冲区溢出

    https://baike.baidu.com/item/%E8%8E%AB%E9%87%8C%E6%96%AF%E8%A0%95%E8%99%AB/90359...

    字节脉搏实验室
  • 1062. 最简分数(20)

    一个分数一般写成两个整数相除的形式:N/M,其中M不为0。最简分数是指分子和分母没有公约数的分数表示形式。

    AI那点小事
  • 1466: [蓝桥杯2019初赛]等差数列

    数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列,只记得其中N 个整数。现在给出这N 个整数,小明想知道包含这N 个整数的最短的等差数...

    可爱见见
  • 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

    那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列,显然这个序列要满足最后一个\(\mid 1\)要在\(\& 0\)之后

    attack
  • LeetCode31|打印从1到最大的n位数

    这道题算是api的使用方式了,数据的计算,其实自己也没有什么好说的了,但是由于文章的字数必需要达到300字,所有有些时候就只好在这里唠会嗑了,因为文章的原创对于...

    后端Coder
  • 河南理工大学新生挑战赛

    B.The flower 题意:意思就是给一个字符串,然后从字符串中得到子串,并且子串满足情况 1.出现次数大于2,; 2.子串的长度等于k; 找到有多...

    用户7727433

扫码关注云+社区

领取腾讯云代金券