欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-06 12:25:49
题意 "题目链接" Sol 神仙二分Orz 首先二分一个答案,表示假设询问的位置为$x$,把$ = x$的看成$1$,$ define Pair pair define MP(x, y) make_pair(x, y) define fi first define se second using n ......

题意

题目链接

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);
}