2020 wannafly camp day1 I K小数查询 —— 分块

题目链接：点我啊╭(╯^╰)╮

题目大意：

    多次操作
    区间取 $min$
    区间求第 $k$ 小

解题思路：

    分块处理，设块大小为 $p$
    块内排好序，查询时更新
    二分答案，对整块直接 $upper\_bound$
    对两边零散点暴力查
    更新时间复杂度：$p\times logp+\frac{n}{p}$
    查询时间复杂度：$logn\times (\frac{n}{p}\times logp+p)$

核心：分块

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
using pii = pair <int,int>;
const int maxn = 8e4 + 5;
int n, m, a[maxn];
int size, bnum, lz[maxn];
int L[maxn], R[maxn];
vector <int> v[maxn];inline int get_id(int x){return x / size;
}inline void update(int l, int r, int x){int id = get_id(l);if(L[id] < l){v[id].clear();for(int i=L[id]; i<=R[id]; i++){a[i] = min(a[i], lz[id]);if(i >= l && i <= r) a[i] = min(a[i], x);v[id].push_back(a[i]);}sort(v[id].begin(), v[id].end());id++;} if(id >= bnum) return;while(R[id]<=r && id<bnum){lz[id] = min(lz[id], x);id++;} if(L[id]>r || id>=bnum) return;v[id].clear();for(int i=L[id]; i<=R[id]; i++){a[i] = min(a[i], lz[id]);if(i >= l && i <= r) a[i] = min(a[i], x);v[id].push_back(a[i]);}sort(v[id].begin(), v[id].end());
}inline int ck(int l, int r, int k){int id = get_id(l), res = 0;if(L[id] < l){for(int i=l; i<=min(R[id], r); i++){a[i] = min(a[i], lz[id]);if(a[i] <= k) res++;}id++;}if(id >= bnum) return res;while(R[id]<=r && id<bnum){if(lz[id] <= k) res += R[id] - L[id] + 1;else res += upper_bound(v[id].begin(), v[id].end(), k) - v[id].begin();id++;}if(L[id]>r || id>=bnum) return res;for(int i=L[id]; i<=min(R[id], r); i++){a[i] = min(a[i], lz[id]);if(a[i] <= k) res++;}return res;
}inline int query(int L, int R, int k){int l = 1, r = 1e9, mid;while(l <= r){mid = l + r >> 1;if(ck(L, R, mid) >= k) r = mid - 1;else l = mid + 1;}return l;
}int main() {scanf("%d%d", &n, &m);for(int i=0; i<n; i++) scanf("%d", a+i);size = sqrt(n), bnum = (n - 1) / size + 1;for(int i=0; i<bnum; i++){lz[i] = 0x3f3f3f3f;L[i] = i * size, R[i] = i * size + size - 1;if(i == bnum - 1) R[i] = n - 1;for(int j=L[i]; j<=R[i]; j++) v[i].push_back(a[j]);sort(v[i].begin(), v[i].end());}while(m--){int op, l, r, k;scanf("%d%d%d%d", &op, &l, &r, &k);l--, r--;if(op == 1) update(l, r, k);else printf("%d\n", query(l, r, k));}
}