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