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); }
上一篇: 三种for循环遍历
推荐阅读
-
cf1136E. Nastya Hasn't Written a Legend(二分 线段树)
-
BZOJ4552: [Tjoi2016&Heoi2016]排序(线段树 二分)
-
洛谷P4632 [APIO2018] New Home 新家(动态开节点线段树 二分答案 扫描线 set)
-
CodeForces - 1454F Array Partition(线段树+二分)
-
CodeForces - 558E A Simple Task (计数排序 线段树)
-
D. Multiset(权值线段树/树状数组/二分)
-
bzoj4552(排序 二分答案+01序列)
-
HDU 2871 Memory Control (线段树+区间合并+成段更新+二分)
-
cf1136E. Nastya Hasn't Written a Legend(二分 线段树)
-
BZOJ4552: [Tjoi2016&Heoi2016]排序(线段树 二分)