区间第k大的几种解法

梦里梦外; 2023-08-17 17:16 108阅读 0赞

区间第K大问题，变化包括带修改和不带修改，强制在线和允许离线

修改主要是单点修改，我们前面也只讨论这种情况。

接下来我们从编程复杂度和时空复杂度来讨论几种做法。

**1.整体二分(编程复杂度:低-中，时间复杂度:优秀，空间复杂度:优秀)**

缺点:只能做离线

优点:空间都是O(n)。常数小。带修改O(nlog2n)，不带修改O(nlogn)。

但是不带修改的情况，如果允许的话，个人认为加个树状数组写O(nlog2n)的更好写

这时单次solve中面对的问题是，数列中一些点是1其余都是0，然后求区间和的问题

这个问题把区间和变成前缀和相减，然后用vector来对那些需要求前缀的点做桶排

然后双指针即可做到单次solve为O(k)，k为此次处理的操作数，总体O(nlogn)的复杂度

显然如果不差那log的时间，直接用树状数组来处理更好写

下面给了一个带单点修改查询区间第K**小**的整体二分代码

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 
     3 #define lb(x) (x&(-x))
     4 
     5 using namespace std;
     6 
     7 const int N = 2e5 + 5;
     8 
     9 int t, n, m, k, cnt;
    10 
    11 struct node {
    12     int id, i, j, k;
    13 }a[N], q1[N], q2[N];
    14 
    15 int ans[N], b[N];
    16 
    17 int c[N];
    18 
    19 char op[5];
    20 
    21 void add(int i, int x) {
         while (i <= n) c[i] += x, i += lb(i);}
    22 
    23 int ask(int i) {
         int res = 0; while (i > 0) res += c[i], i -= lb(i); return res;}
    24 
    25 void solve(int head, int tail, int l, int r) {
    26     if (head > tail) return;
    27     if (l == r) {
    28         for (int i = head; i <= tail; i ++)
    29             ans[a[i].id] = r;
    30         return;
    31     }
    32     int mid = l + r >> 1, s1 = 0, s2 = 0;
    33     for (int sum, i = head; i <= tail; i ++)
    34         if (a[i].id) {
    35             sum = ask(a[i].j) - ask(a[i].i - 1);
    36             if (sum >= a[i].k) q1[s1 ++] = a[i];
    37             else a[i].k -= sum, q2[s2 ++] = a[i];
    38         }
    39         else {
    40             if (a[i].j <= mid) q1[s1 ++] = a[i], add(a[i].i, a[i].k);
    41             else q2[s2 ++] = a[i];
    42         }
    43     for (int i = 0; i < s1; i ++)
    44         if (!q1[i].id)
    45             add(q1[i].i, -q1[i].k);
    46     memcpy(a + head, q1, sizeof(node) * s1);
    47     memcpy(a + head + s1, q2, sizeof(node) * s2);
    48     solve(head, head + s1 - 1, l, mid);
    49     solve(head + s1, tail, mid + 1, r);
    50 }
    51 
    52 int main() {
    53     ios::sync_with_stdio(false);
    54     for (cin >> t; t --; ) {
    55         cin >> n >> m; k = cnt = 0;
    56         for (int i = 1; i <= n; i ++) {
    57             cin >> b[i];
    58             a[++ k] = (node){
         0, i, b[i], 1};
    59         }
    60         for (int l, r, x, i = 1; i <= m; i ++) {
    61             cin >> op >> l >> r;
    62             if (op[0] == 'Q') {
    63                 cin >> x;
    64                 a[++ k] = (node){++ cnt, l, r, x};
    65             }
    66             else {
    67                 a[++ k] = (node){
         0, l, b[l], -1};
    68                 a[++ k] = (node){
         0, l, b[l] = r, 1};
    69             }
    70         }
    71         solve(1, k, 1, 1e9);
    72         for (int i = 1; i <= cnt; i ++)
    73             printf("%d\n", ans[i]);
    74     }
    75     return 0;
    76 }

2.主席树(**编程复杂度:低-中，时间复杂度:优秀，空间复杂度:高**)

缺点:空间占用多。树套树的常数。

优点:可以在线！时间复杂度同整体二分。空间复杂度和时间复杂度一致。

不带修改是主席树基本操作。带修改就套树状数组，下面给出(和上面同一个问题的)代码。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 
     3 using namespace std;
     4 
     5 const int MAXN = 1e9;
     6 const int N = 5e4 + 5;
     7 
     8 int n, m, a[N], rt[N];
     9 
    10 int tot, tr[N * 800][3];
    11 
    12 int tmp1[100], tmp2[100];
    13 
    14 #define l(x) tr[x][0]
    15 #define r(x) tr[x][1]
    16 #define s(x) tr[x][2]
    17 #define lb(x) (x&(-x))
    18 #define mid (l + r >> 1)
    19 
    20 int change(int o, int l, int r, int k, int v) {
    21     int x = ++ tot; s(x) = s(o) + v;
    22     if (l == r) return x; l(x) = l(o), r(x) = r(o);
    23     k > mid ? r(x) = change(r(o), mid + 1, r, k, v) : l(x) = change(l(o), l, mid, k, v);
    24     return x;
    25 }
    26 
    27 void modify(int i, int p, int v) {
    28     while (i <= n) rt[i] = change(rt[i], 1, MAXN, p, v), i += lb(i);
    29 }
    30 
    31 int ask(int l, int r, int k) {
    32     if (l == r) return r; int sum = 0;
    33     for (int i = 1; i <= tmp1[0]; i ++) sum -= s(l(tmp1[i]));
    34     for (int i = 1; i <= tmp2[0]; i ++) sum += s(l(tmp2[i]));
    35     if (k > sum) {
    36         for (int i = 1; i <= tmp1[0]; i ++) tmp1[i] = r(tmp1[i]);
    37         for (int i = 1; i <= tmp2[0]; i ++) tmp2[i] = r(tmp2[i]);
    38         return ask(mid + 1, r, k - sum);
    39     }
    40     else {
    41         for (int i = 1; i <= tmp1[0]; i ++) tmp1[i] = l(tmp1[i]);
    42         for (int i = 1; i <= tmp2[0]; i ++) tmp2[i] = l(tmp2[i]);
    43         return ask(l, mid, k);
    44     }
    45 }
    46 
    47 int query(int l, int r, int k) {
         //查询区间第k小
    48     tmp1[0] = tmp2[0] = 0;
    49     for (int i = l - 1; i > 0; i -= lb(i)) tmp1[++ tmp1[0]] = rt[i];
    50     for (int i = r;     i > 0; i -= lb(i)) tmp2[++ tmp2[0]] = rt[i];
    51     return ask(1, MAXN, k);
    52 }
    53 
    54 int main(){
    55     int t; char op[5];
    56     for (cin >> t; t --; ) {
    57         cin >> n >> m; tot = 0;
    58         for (int i = 1; i <= n; i ++) cin >> a[i], rt[i] = 0;
    59         for (int i = 1; i <= n; i ++) modify(i, a[i], 1);
    60         for (int i, j, k; m --; ) {
    61             cin >> op >> i >> j;
    62             if (op[0] == 'C') modify(i, a[i], -1), modify(i, a[i] = j, 1);
    63             else cin >> k, printf("%d\n", query(i, j, k));
    64         }
    65     }
    66     return 0;
    67 }

其他做法我参考了一下，很难与上述两种做法并肩，就不做讨论了

如果有的话欢迎告诉我

**拓展1.初始数列每个位置都是一个空队列，修改变成了区间\[l,r\]的每个队列末尾都push一个数x**

**查询某个区间所有数字中的第K大**

解法:其实还是个整体二分的简单题目，用线段树维护即可，复杂度依然是O(nlog2n)

转载于:https://www.cnblogs.com/ytytzzz/p/11603435.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230808/2f2f534383474731a235d9717ad06207.png