#4604. The kth maximum number

給定一個(gè)大小不超過$5\times 10^5$的矩形區(qū)域，有一些點(diǎn)有點(diǎn)權(quán)。

每次詢問給定$x_1,y_1,x_2,y_2,k$問以$x_1,y_1$為右下角，$x_2,y_2$為左上角的矩形中權(quán)值第$k$大是多少。

其實(shí)于P1527 [國(guó)家集訓(xùn)隊(duì)]矩陣乘法是基本差不多的，就是矩形的大小變大了，無法進(jìn)行二維樹狀數(shù)組操作

但是，矩形數(shù)點(diǎn)不就是一個(gè)二維偏序問題嘛，可以樹套樹來解決，于是我們有了如下的做法，

考慮整體二分，

先對(duì)$x,y$進(jìn)行離散化（保證常數(shù)小一點(diǎn)吧），對(duì)每個(gè)橫左邊建立一顆主席樹，同時(shí)用樹狀數(shù)組維護(hù)，

于是在二分過程中，我們對(duì)每個(gè)點(diǎn)的修改操作，直接修改即可，同時(shí)對(duì)主席樹加上內(nèi)存回收機(jī)制，這樣可以保證不會(huì)炸空間，

之后對(duì)每個(gè)矩陣的查詢，我們只要在區(qū)間$[x_1,x_2]$的主席樹上查詢值在$[y_1,y_2]$有多少即可，

整體復(fù)雜度$O(n{\log }^{3}n)$，由于$n$比較小，實(shí)測(cè)跑得還是挺快的。

#include <bits/stdc++.h>using namespace std;const int N = 1e5 + 10;int X[N], Y[N], V[N], ans[N], n, m, nn, mm, tot;int root[N], ls[N * 300], rs[N * 300], sum[N * 300], stk[N * 300], top, num;void update(int &rt, int l, int r, int x, int v) {if (!rt) {if (top) {rt = stk[top--];}else {rt = ++num;}}sum[rt] += v;if (l == r) {return ;}int mid = l + r >> 1;if (x <= mid) {update(ls[rt], l, mid, x, v);}else {update(rs[rt], mid + 1, r, x, v);} }int A[50], B[50], cnt1, cnt2;int query(int l, int r, int L, int R) {if (l >= L && r <= R) {int res = 0;for (int i = 1; i <= cnt1; i++) {res -= sum[A[i]];}for (int i =1 ; i <= cnt2; i++) {res += sum[B[i]];}return res;}int mid = l + r >> 1, res = 0, A1[50], B1[50];if (L <= mid) {for (int i = 1; i <= cnt1; i++) {A1[i] = A[i];A[i] = ls[A[i]];}for (int i = 1; i <= cnt2; i++) {B1[i] = B[i];B[i] = ls[B[i]];}res += query(l, mid, L, R);for (int i = 1; i <= cnt1; i++) {A[i] = A1[i];}for (int i = 1; i <= cnt2; i++) {B[i] = B1[i];}}if (R > mid) {for (int i = 1; i <= cnt1; i++) {A1[i] = A[i];A[i] = rs[A[i]];}for (int i = 1; i <= cnt2; i++) {B1[i] = B[i];B[i] = rs[B[i]];}res += query(mid + 1, r, L, R);for (int i = 1; i <= cnt1; i++) {A[i] = A1[i];}for (int i = 1; i <= cnt2; i++) {B[i] = B1[i];}}return res; }inline int lowbit(int x) {return x & (-x); }void update(int x, int y, int v) {while (x <= nn) {update(root[x], 1, mm, y, v);x += lowbit(x);} }int get_sum(int l, int r, int L, int R) {if (l > r || L > R) {return 0;}cnt1 = cnt2 = 0;for (int i = l - 1; i; i -= lowbit(i)) {A[++cnt1] = root[i];}for (int i = r; i; i -= lowbit(i)) {B[++cnt2] = root[i];}return query(1, mm, L, R); }struct Res {int x1, y1, x2, y2, v, id, op; }q[N], q1[N], q2[N];void solve(int l, int r, int L, int R) {if (L > R || l > r) {return ;}if (l == r) {for (int i = L; i <= R; i++) {if (q[i].op == 2) {ans[q[i].id] = l;}}return ;}int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;for (int i = L; i <= R; i++) {if (q[i].op == 1) {if (q[i].v > V[mid]) {update(q[i].x1, q[i].y1, 1);q2[++cnt2] = q[i];}else {q1[++cnt1] = q[i];}}else {int cur = get_sum(q[i].x1, q[i].x2, q[i].y1, q[i].y2);if (cur >= q[i].v) {q2[++cnt2] = q[i];}else {q[i].v -= cur;q1[++cnt1] = q[i];}}}for (int i = 1; i <= cnt2; i++) {if (q2[i].op == 1) {update(q2[i].x1, q2[i].y1, -1);}}for (int i = 1; i <= cnt1; i++) {q[L + i - 1] = q1[i];}for (int i = 1; i <= cnt2; i++) {q[L + cnt1 + i - 1] = q2[i];}solve(l, mid, L, L + cnt1 - 1), solve(mid + 1, r, L + cnt1, R); }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);scanf("%d %d", &n, &m);for (int i = 1, op; i <= m; i++) {scanf("%d", &op);if (op & 1) {int x, y, v;scanf("%d %d %d", &x, &y, &v);q[i] = {x, y, 0, 0, v, 0, 1};X[++tot] = x, Y[tot] = y, V[tot] = v;}else {int x1, y1, x2, y2, v;scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &v);q[i] = {x1, y1, x2, y2, v, i, 2};}}sort(X + 1, X + 1 + tot), sort(Y + 1, Y + 1 + tot), sort(V + 1, V + 1 + tot);nn = unique(X + 1, X + 1 + tot) - (X + 1);mm = unique(Y + 1, Y + 1 + tot) - (Y + 1);tot = unique(V + 1, V + 1 + tot) - (V + 1);for (int i = 1; i <= m; i++) {if (q[i].op & 1) {q[i].x1 = lower_bound(X + 1, X + 1 + nn, q[i].x1) - X;q[i].y1 = lower_bound(Y + 1, Y + 1 + mm, q[i].y1) - Y;}else {q[i].x1 = lower_bound(X + 1, X + 1 + nn, q[i].x1) - X;q[i].y1 = lower_bound(Y + 1, Y + 1 + mm, q[i].y1) - Y;q[i].x2 = upper_bound(X + 1, X + 1 + nn, q[i].x2) - X;q[i].y2 = upper_bound(Y + 1, Y + 1 + mm, q[i].y2) - Y;q[i].x2--, q[i].y2--;}}for (int i = 1; i <= m; i++) {ans[i] = -1;}solve(0, tot, 1, m);for (int i = 1; i <= m; i++) {if (ans[i] != -1) {if (ans[i] == 0) {puts("NAIVE!ORZzyz.");}else {printf("%d\n", V[ans[i]]);}}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的#4604. The kth maximum number（整体二分 + 树套树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。