首页 > 代码库 > ZOJ 2112 Dynamic Rankings（带修改的区间第K大，分块+二分搜索+二分答案）
ZOJ 2112 Dynamic Rankings（带修改的区间第K大，分块+二分搜索+二分答案）
The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], ..., a[N], you can ask it like: what is the k-th smallest number of a[i], a[i+1], ..., a[j]? (For some i<=j, 0<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.
Your task is to write a program for this computer, which
- Reads N numbers from the input (1 <= N <= 50,000)
- Processes M instructions of the input (1 <= M <= 10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change some a[i] to t.
Input
The first line of the input is a single number X (0 < X <= 4), the number of the test cases of the input. Then X blocks each represent a single test case.
The first line of each block contains two integers N and M, representing N numbers and M instruction. It is followed by N lines. The (i+1)-th line represents the number a[i]. Then M lines that is in the following format
Q i j k or
C i t
It represents to query the k-th number of a[i], a[i+1], ..., a[j] and change some a[i] to t, respectively. It is guaranteed that at any time of the operation. Any number a[i] is a non-negative integer that is less than 1,000,000,000.
There‘re NO breakline between two continuous test cases.
Output
For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1],..., a[j])
There‘re NO breakline between two continuous test cases.
Sample Input
2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
3
6
#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)#define CLR(arr,val) memset(arr,val,sizeof(arr))#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);typedef pair<int, int> pii;typedef long long LL;const double PI = acos(-1.0);const int N = 50010;const int M = 10010;const int BC = 233;struct Block{ int l, r;};Block B[M];int arr[N], belong[N], unit, bcnt, b[N];int n, m;void reset(int x){ for (int i = B[x].l; i <= B[x].r; ++i) b[i] = arr[i]; sort(b + B[x].l, b + B[x].r + 1);}void init(){ unit = sqrt(n); bcnt = n / unit; if (n % unit) ++bcnt; int i; for (i = 1; i <= bcnt; ++i) { B[i].l = (i - 1) * unit + 1; B[i].r = i * unit; } B[bcnt].r = n; for (i = 1; i <= n; ++i) belong[i] = (i - 1) / unit + 1; for (i = 1; i <= bcnt; ++i) reset(i);}void update(int x, int t){ int bx = belong[x]; arr[x] = t; reset(bx);}int bs(int x, int key){ int l = B[x].l, r = B[x].r; int ans = -1; while (l <= r) { int mid = MID(l, r); if (b[mid] <= key) { ans = mid; l = mid + 1; } else r = mid - 1; } return ~ans ? ans - B[x].l + 1 : 0;}int query(int l, int r, int k){ int L = 0, R = 1e9; int ans = 1; int bl = belong[l], br = belong[r], i; while (L <= R) { int tk = 0; int mid = MID(L, R); for (i = l; i <= B[bl].r; ++i) if (arr[i] <= mid) ++tk; for (i = B[br].l; i <= r; ++i) if (arr[i] <= mid) ++tk; for (i = bl + 1; i < br; ++i) tk += bs(i, mid); if (tk >= k) { ans = mid; R = mid - 1; } else L = mid + 1; } return ans;}int main(void){ int tcase, i; char ops[3]; int l, r, k, x, t; scanf("%d", &tcase); while (tcase--) { scanf("%d%d", &n, &m); for (i = 1; i <= n; ++i) scanf("%d", &arr[i]); init(); for (i = 1; i <= m; ++i) { scanf("%s", ops); if (ops[0] == ‘Q‘) { scanf("%d%d%d", &l, &r, &k); printf("%d\n", query(l, r, k)); } else { scanf("%d%d", &x, &t); update(x, t); } } } return 0;}ZOJ 2112 Dynamic Rankings（带修改的区间第K大，分块+二分搜索+二分答案）