Chlience

【题解】区间第 K 小
Problem给定长度为 $n$ 的序列,所有元素满足 $x\in [1,n]$有 $m$ 个询问,每次询问 $[...
扫描右侧二维码阅读全文
15
2019/03

【题解】区间第 K 小

Problem

给定长度为 $n$ 的序列,所有元素满足 $x\in [1,n]$

有 $m$ 个询问,每次询问 $[l,r]$ 区间内的第 $k$ 小值,若某个数出现次数大于一个常数 $w$ ,则该数视为 $n+1$

强制在线

Thought

先考虑离线做法:

发现将次数大于常数 $w$ 的值看做 $n+1$ 这个条件非常的尴尬,那么可能需要维护当前序列中每个元素的值,或者是维护其变化情况(在恰好等于 $w$ 的时候和减小到 $w$ 以下的时候),所以原本的主席树就直接 $GG$ 了

如果考虑维护每个数的变化情况的话,当然优先选择莫队算法,同时还需要维护某个数据结构,支持查询区间第 $k$ 大,可以使用线段树

但是由于修改一共有 $n\sqrt n$ 个,查询只有 $m$ 个,那么线段树 $O(\log n)$ 的查询与修改不如改为使用分块 $O(1)$ 的修改和 $O(\sqrt n)$ 的查询,总复杂度 $O(n\sqrt n)$

再考虑在线做法:

强行在线之后,原本的莫队算法已经不能继续使用,尽管有强制在线莫队这种黑科技,但是其复杂度已经不能满足我们的要求

那么,如何取得区间 $[l,r]$ 中的块呢?

发现如果我们将序列进行分块,存下序列第 $i​$ 到第 $j​$ 个块中的权值块的答案,那么便可以很简单的取出 $[l,r]​$ 的所有块

并且,在求得 $i$ 到 $j$ 中权值块的和时,我们便可以同时处理出那些出现大于 $w$ 次的数,对于散块,暴力判断是否出现大于 $w​$ 次即可

至于如何求第 $i$ 到第 $j$ 个块中的权值块的和,可以确定左端点块,然后扫过去,加入答案,每次扫过去复杂度 $O(n)$ ,共扫 $\sqrt n$ 次,总复杂度 $O(n\sqrt n)$

取出块后,我们能够确定答案的区间,但是无法计算具体的位置

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
const int M = 340;
int n, m, w, a[N];
int bel[N], siz, num;
int f[M][M][M];
int t[N];
int g[M][N];

int now[N];
int sta[N], top;
int K[M];

int cal(int l, int r, int k) {
    while(top) {
        now[sta[top]] = 0;
        sta[top --] = 0;
    }
    for(int i = 1; i <= num; ++ i)
        K[i] = 0;
    for(int i = l; i <= min(bel[l] * siz, r); ++ i) {
        if(!now[a[i]]) sta[++ top] = a[i];
        ++ now[a[i]];
    }
    if(bel[l] != bel[r])
        for(int i = (bel[r] - 1) * siz + 1; i <= r; ++ i) {
            if(!now[a[i]]) sta[++ top] = a[i];
            ++ now[a[i]];
        }
    if(bel[l] + 1 <= bel[r] - 1) {
        for(int i = 1; i <= num; ++ i)
            K[i] = f[bel[l] + 1][bel[r] - 1][i];
        for(int i = 1; i <= top; ++ i) {
            int sum = g[bel[r] - 1][sta[i]] - g[bel[l]][sta[i]];
            if(sum <= w) {
                if(sum + now[sta[i]] > w)
                    K[bel[sta[i]]] -= sum;
                else
                    K[bel[sta[i]]] += now[sta[i]];
            }
        }
        for(int i = 1; i <= num; ++ i) {
            if(K[i] >= k) {
                for(int j = (i - 1) * siz + 1; j <= min(i * siz, n); ++ j) {
                    int sum = now[j] + g[bel[r] - 1][j] - g[bel[l]][j];
                    if(sum > w) continue;
                    if(sum >= k) return j;
                    else k -= sum;
                }
            }
            else k -= K[i];
        }
        return n + 1;
    }
    else {
        for(int i = 1; i <= top; ++ i)
            if(now[sta[i]] <= w)
                K[bel[sta[i]]] += now[sta[i]];
        for(int i = 1; i <= num; ++ i) {
            if(K[i] >= k) {
                for(int j = (i - 1) * siz + 1; j <= min(i * siz, n); ++ j) {
                    int sum = now[j];
                    if(sum > w) continue;
                    if(sum >= k) return j;
                    else k -= sum;
                }
            }
            else k -= K[i];
        }
        return n + 1;
    }
}
int main() {
    n = read(); m = read(); w = read();
    siz = sqrt(n);
    for(int i = 1; i <= n; ++ i) bel[i] = (i - 1) / siz + 1;
    for(int i = 1; i <= n; ++ i) a[i] = read();
    num = bel[n];
    for(int i = 1; i <= num; ++ i) {
        memset(t, 0, sizeof(t));
        for(int j = i; j <= num; ++ j) {
            for(int k = 1; k <= num; ++ k)
                f[i][j][k] = f[i][j - 1][k];
            for(int k = siz * (j - 1) + 1; k <= min(siz * j, n); ++ k) {
                ++ f[i][j][bel[a[k]]]; ++ t[a[k]];
                if(t[a[k]] == w + 1)
                    f[i][j][bel[a[k]]] -= w + 1;
                else if(t[a[k]] > w + 1)
                    f[i][j][bel[a[k]]] -= 1;
            }
        }
    }
    for(int i = 1; i <= num; ++ i) {
        for(int j = 1; j <= n; ++ j)
            g[i][j] = g[i - 1][j];
        for(int j = (i - 1) * siz + 1; j <= min(i * siz, n); ++ j)
            ++ g[i][a[j]];
    }
    int ans = 19260817;
    for(int i = 1; i <= m; ++ i) {
        int l = read() ^ ans, r = read() ^ ans, k = read() ^ ans;
        ans = cal(l, r, k);
        printf("%d\n", ans);
    }
    return 0;
}
Last modification:March 15th, 2019 at 08:42 pm

Leave a Comment