HDU6231 & P2824
HDU6231 K-th Number
给你一个长度为 \(n\) 的序列 \(A\)，有一个初始为空的序列 \(B\)，把 \(A\) 中所有子区间的第 \(K\) 大加入序列 \(B\) 中，求 \(B\) 中的第 \(M\) 大
\(n\le 10^5,K\le n\)
考虑二分答案，假设当前答案是 \(x\)，把原序列中所有 \(<x\) 的元素变成 \(0\)，所有 \(\ge x\) 的元素变成 \(1\)
只有包含 \(1\) 的个数 \(\le K\) 的区间，加入的数才会排在 \(x\) 的前面，算出 \(x\) 的前面有多少个数，来二分第 \(M\) 个位置即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int sum[N];
int n, k;
long long m;
inline bool check(int x){
long long res = 0;
for(int i = 1; i <= n; i++){
sum[i] = sum[i-1];
if(a[i] >= x){
sum[i] ++;
}
}
for(int i = 1, j = 1; i <= n && j <= n; i ++){
while(sum[j] - sum[i-1] < k && j <= n) j++;
res += n - j + 1;
}
return res >= m;
}
int main(){
int T;
scanf("%d", &T);
while(T--){
scanf("%d%d%lld", &n, &k, &m);
for(int i = 1; i <= n; i ++){
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + n + 1);
int l = 1, r = n+1, ans;
while(l < r){
int mid = (l + r) >> 1;
if(check(b[mid])) { ans = mid, l = mid + 1;}
else r = mid;
}
printf("%d\n", b[ans]);
}
return 0;
}
P2824 [HEOI2016/TJOI2016]排序
同样的套路，考虑二分答案
假设当前二分的值是 \(x\)，把序列中所有 \(<x\) 的都变成 \(0\)，所有 \(\ge x\) 的都变成 \(1\)
则排序的操作就是区间清空，前/后缀赋 \(1\)
按第 \(q\) 个位置的数是否为 \(1\) 二分即可（是否 \(\ge x\))
二分复杂度是 \(O(\log n)\) 的，每次建线段树，暴力执行询问是 \(O(n\log n+m\log n)\)
复杂度是 \(O((n+m)\log^2 n)\)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N], b[N];
int base[N];
int Q;
struct Operator {
int l, r;
int type;
}q[N];
struct Node {
int l, r;
int sum;
int tag;
}tr[N << 4];
inline void pushup(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u) {
if(tr[u].tag == -1)
return ;
Node &ls = tr[u << 1], &rs = tr[u << 1 | 1];
ls.sum = tr[u].tag * (ls.r - ls.l + 1);
rs.sum = tr[u].tag * (rs.r - rs.l + 1);
ls.tag = tr[u].tag;
rs.tag = tr[u].tag;
tr[u].tag = -1;
}
void build(int u, int l, int r) {
tr[u].l = l, tr[u].r = r;
tr[u].tag = -1;
if(l == r) {
tr[u].sum = base[l];
return ;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
int query_seg(int u, int l, int r) {
if(l <= tr[u].l && tr[u].r <= r) {
return tr[u].sum;
}
int ans = 0;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid)
ans += query_seg(u << 1, l, r);
if(r > mid)
ans += query_seg(u << 1 | 1, l, r);
return ans;
}
int query(int u, int x) {
if(tr[u].l == tr[u].r) {
return tr[u].sum;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid)
return query(u << 1, x);
else
return query(u << 1 | 1, x);
}
void modify(int u, int l, int r, int k) {
if(l <= tr[u].l && tr[u].r <= r) {
tr[u].sum = k * (tr[u].r - tr[u].l + 1);
tr[u].tag = k;
return ;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid)
modify(u << 1, l, r, k);
if(r > mid)
modify(u << 1 | 1, l, r, k);
pushup(u);
}
void DoOperator(int x) {
int Num1 = query_seg(1, q[x].l, q[x].r);
modify(1, q[x].l, q[x].r, 0);
if(q[x].type == 0)
modify(1, q[x].r - Num1 + 1, q[x].r, 1);
else
modify(1, q[x].l, q[x].l + Num1 - 1, 1);
}
bool check(int x) {
for(int i = 1; i <= n; i++)
base[i] = a[i] >= x;
build(1, 1, n);
for(int i = 1; i <= m; i++)
DoOperator(i);
return query(1, Q);
}
int BinarySearch() {
int l = 1, r = n;
while(l < r) {
int mid = l + r >> 1;
if(check(b[mid])) l = mid + 1;
else r = mid;
}
return l - 1;
}
int main() {
//freopen("sort.in", "r", stdin);
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
memcpy(b, a, (n + 1) * sizeof(int));
sort(b + 1, b + 1 + n);
for(int i = 1; i <= m; i++)
scanf("%d%d%d", &q[i].type, &q[i].l, &q[i].r);
scanf("%d", &Q);
printf("%d\n", b[BinarySearch()]);
return 0;
}