浅谈区间在线去重k小
关于讨论
https://www.luogu.com.cn/discuss/509205
本文将描述一种分块做法以及讨论中提出的各种 \(O(n \ \text{polylog}(n))\) 做法。
给定一个长度为 \(n\) 的序列 \(a\)。有 \(q\) 次形如 \((l,r,k)\) 的询问，查询下标在 \([l,r]\) 区间内元素去重后的第 \(k\) 小值。去重操作不实际进行。
强制在线。
\(n,q,a_i \le 10^5\)。
考虑分块。
首先考虑一个朴素的分块。设块长为 \(B\)，值域为 \(L\)。
我们在每两块间建一个值域分块，插入左边块左端点到右边块右端点间所有元素。值域分块采用 \(O(1)\) 修改 \(O(\sqrt L)\) 查询的写法，需要 \(O(L + \sqrt L)\) 的空间。这样总共会建 \(O\left(\left(\frac nB\right)^2\right)\) 个值域分块。然而我们发现每个值域分块的空间过大，无法整块处理。因此考虑将值域分块拆分。
放出值域分块代码以便理解
struct sqrt_technology {
int bll[N], lpl[B], rpl[B], bllL;
int cntblk[B], cntpts[N];
void init() {
sql = pow(L, 0.5);
rep(i,1,L) {
bll[i] = (i - 1) / sql + 1;
if (bll[i] != bll[i-1]) rpl[bll[i-1]] = i-1, lpl[bll[i]] = i;
} bllL = bll[L];
rpl[bllL] = L;
}
void insert(int pos) {
cntpts[pos] ++;
if (cntpts[pos] == 1) cntblk[bll[pos]] ++;
}
void erase(int pos) {
cntpts[pos] --;
if (cntpts[pos] == 0) cntblk[bll[pos]] --;
}
int findkth(int k) {
int ptr = 1;
while (ptr <= bllL and k - cntblk[ptr] > 0) k -= cntblk[ptr], ++ ptr;
if (ptr > bllL) return -1;
int rpos = rpl[ptr]; ptr = lpl[ptr];
while (ptr <= rpos and k - (cntpts[ptr] > 0) > 0) k -= (cntpts[ptr] > 0), ++ ptr;
if (ptr > rpos) return -1;
return ptr;
}
} st;
我们的值域分块共有两个部分。
第一部分是记录每个元素的出现次数，这部分的信息满足可减性。因此我们可以将这部分处理为块的前缀和，需要 \(O(LB)\) 的空间。
第二部分是记录每个值域块内出现次数大于 \(1\) 的元素的个数，这部分不满足可减性。然而我们可以发现，两块间的信息只需要 \(O(\sqrt L)\) 的空间存储，因此这部分可以全部存下来。需要 \(O(L B^2)\) 的空间。
对于查询，我们首先剥离出整块的值域块信息，随后可以通过前缀和获取每个值的信息。这样我们就得到了区间内整块信息。按照如上的方式就可以将散块信息加入当前获得的值域分块中。
取 \(B = \sqrt n\)，我们有时间复杂度 \(O(n\sqrt n)\)，空间复杂度 \(O(n \sqrt n)\)。
code
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define rep(i,a,b) for (register int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define pre(i,a,b) for (register int i = (a), i##_ = (b) - 1; i > i##_; --i)
const int N = 1e5 + 10, B = 350;
int n, q, L, l, r, kth, sq, a[N], bl[N], lp[N], rp[N];
int cnt[B][N];
int bll[N], lpl[B], rpl[B], bllL, sql;
int cntpts[N], nblk[B], cntblk[B][B][B], pref[B][N];
signed main() {
cin >> n >> q;
rep(i,1,n) cin >> a[i], L = max(L, a[i]);
sql = sqrt(L);
rep(i,1,L) {
bll[i] = (i - 1) / sql + 1;
if (bll[i] != bll[i-1]) rpl[bll[i-1]] = i-1, lpl[bll[i]] = i;
} bllL = bll[L];
rpl[bllL] = L;
sq = sqrt(n);
rep(i,1,n){
bl[i] = (i-1) / sq + 1;
if (bl[i] != bl[i-1]) rp[bl[i-1]] = i-1, lp[bl[i]] = i;
} rp[bl[n]] = n;
rep(i,1,bl[n]){
rep(j,i,bl[n]) {
rep(k,lp[j],rp[j]) {
cntpts[a[k]] ++;
if (cntpts[a[k]] == 1) cntblk[i][j][bll[a[k]]] ++;
}
if (j < bl[n]) rep(k,1,bllL) cntblk[i][j + 1][k] = cntblk[i][j][k];
}
rep(k,lp[i],n) cntpts[a[k]] = 0;
}
rep(i,1,bl[n]) {
rep(j,lp[i],rp[i]) {
pref[i][a[j]] ++;
}
if (i < n) rep(j,1,L) pref[i+1][j] += pref[i][j];
}
rep(i,1,q) {
int ans = 0;
cin >> l >> r >> kth;
int bl_l = bl[l], bl_r = bl[r];
ans = 1;
if (bl_l + 1 >= bl_r - 1) {
rep(j,l,r) {
cntpts[a[j]] ++;
if (cntpts[a[j]] == 1) nblk[bll[a[j]]] ++;
}
while (ans <= bllL and kth - nblk[ans] > 0) kth -= nblk[ans], ++ ans;
if (ans > bllL) ans = -1;
else {
int rpos = rpl[ans]; ans = lpl[ans];
while (ans <= rpos and kth - (cntpts[ans] > 0) > 0) kth -= (cntpts[ans] > 0), ++ ans;
if (ans > rpos) ans = -1;
}
rep(j,l,r) {
cntpts[a[j]] = 0;
nblk[bll[a[j]]] = 0;
}
} else {
rep(j,1,bllL) nblk[j] = cntblk[bl_l+1][bl_r-1][j];
rep(j,l,rp[bl_l]) {
cntpts[a[j]] ++;
if (cntpts[a[j]] == 1 and pref[bl_r-1][a[j]] - pref[bl_l][a[j]] == 0) nblk[bll[a[j]]] ++;
}
rep(j,lp[bl_r],r) {
cntpts[a[j]] ++;
if (cntpts[a[j]] == 1 and pref[bl_r-1][a[j]] - pref[bl_l][a[j]] == 0) nblk[bll[a[j]]] ++;
}
while (ans <= bllL and kth - nblk[ans] > 0) kth -= nblk[ans], ++ ans;
if (ans > bllL) ans = -1;
else {
int rpos = rpl[ans]; ans = lpl[ans];
while (ans <= rpos and kth - (cntpts[ans] + pref[bl_r-1][ans] - pref[bl_l][ans] > 0) > 0) kth -= (cntpts[ans] + pref[bl_r-1][ans] - pref[bl_l][ans] > 0), ++ ans;
if (ans > rpos) ans = -1;
}
rep(j,l,rp[bl_l]) {
cntpts[a[j]] = 0;
}
rep(j,lp[bl_r],r) {
cntpts[a[j]] = 0;
}
rep(j,1,bllL) nblk[j] = 0;
} cout << ans << '\n';
}
}
[能不能再给力一点啊？]
题面相同。
\(n,q,a_i \le 10^5\)。需要 \(O(n\ \text{polylog}(n))\)。
考虑二分答案转化为判定。
这样我们其实将问题转化为了区间去重排名问题。
然后我们可以将判定问题转化成二维数点，即，维护每个值前第一个出现的位置 \(\text{pre}\)，则我们所需要求的即所有 \(i\) 满足 \(l\le i \le r\)、\(\text{pre} < l\)，\(a_i \le mid\)。可以首先将信息加入一个二维结构后维护判定。
可以发现这个二维结构能做到 \(O(n\log^2n)\) 预处理 \(O(\log^2n)\) 查询，于是我们做到了 \(O(n \log^2n + q \log^3n)\)。
[能不能再给力一点啊？]
题面相同。
\(n,q,a_i \le 3\times 10^5\)。需要 \(O(n\ \text{polylog}(n))\)。
我们发现我们其实不需要二分答案。
我们首先在值域上开一棵权值线段树。我们只需要维护左端点内满足条件数的个数，就可以在线段树上二分得到答案了。
考虑内层维护一棵主席树，\(rt\) 维开在下标上，值域维开在 \(\text{pre}\) 上。
加入元素 \((a_i, pre)\) 时，在外层权值线段树对应的 \(O(\log n)\) 个节点中插入这个元素。插入时，复制 \(rt_{i-1}\) 的信息到 \(rt_i\) 上，随后在 \(rt_i\) 中插入元素 \(pre\)。容易发现这样只会新增 \(O(\log^2 n)\) 个节点，因此预处理的总时间复杂度为 \(O(n\log^2 n)\)。
在实现上，为避免在每个节点开 \(n\) 长度的 \(rt\) 数组，我们可以转而使用vector维护节点的所有 rt。由于我们是按下标顺序插入，我们可以直接查找当前节点 vector 的最后一个值 \(prev(i)\)，使用 \(rt_{prev(i)}\) 作为原本复制信息到 \(rt_i\) 上。
由于每次插入会带来 \(O(\log n)\) 个权值线段树节点，\(O(\log n)\) 个 vector 节点，\(O(\log^2 n)\) 个主席树节点，因此空间复杂度为 \(O(n\log^2 n)\)。
查询第 \((l,r,k)\) 小值时，在外层权值线段树上二分。
我们只需要查看左侧区间内有多少个满足条件的点，即 \(l\le rt_p \le r\) 的 \(rt\) 段中满足 \(pre < l\) 的节点的数量。
这点可以首先从节点对应 vector 中查询 \(l,r\) 的 bound 得到 \(rt\)，信息相减后查询小于 \(pre\) 的节点数量即可。
每层需要从 vector 中查询一次，从主席树中查询一次，而共需 \(O(\log n)\) 次查询，因此得到时间复杂度 \(O(\log^2 n)\)。
这部分的时间复杂度为 \(O(q\log^2 n)\)。
综上，我们得到了一种 \(O(n \log^2 n+ q\log^2 n)\) 的做法。
这份代码比较吃空间
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
namespace Fread { const int SIZE = (1 << 18); char buf[SIZE], *p1 = buf, *p2 = buf; inline char getchar() {return (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, SIZE, stdin), p1 == p2) ? EOF : *p1++);} }
namespace Fwrite { const int SIZE = (1 << 18); char buf[SIZE], *S = buf, *T = buf+SIZE; inline void flush(){ fwrite(buf, 1, S-buf, stdout), S = buf; } struct NTR{ ~NTR() { flush(); } }ztr;inline void putchar(char c){ *S++ = c; if(S == T) flush(); } }
#ifdef ONLINE_JUDGE
#define getchar Fread::getchar
#define putchar Fwrite::putchar
#endif
namespace Fastio{
struct Reader{ template <typename T> Reader & operator >> (T & x) {char c = getchar(); bool f = false;while (c < '0' or c > '9') { if (c == '-') f = true;c = getchar();} x = 0;while(c >= '0' and c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} if (f) x = -x;return *this;}Reader&operator>>(char&c){ c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){ int len=0;char c=getchar(); while(c=='\n'||c==' '||c=='\r')c=getchar(); while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar(); str[len]='\0'; return *this;}Reader(){}}cin;
struct Writer{ template <typename T> Writer & operator << (T x) {if(x == 0) return putchar('0'), *this;if(x < 0) putchar('-'), x = -x;static int sta[45], top = 0; while (x) sta[++top] = x %10, x /= 10; while (top) putchar(sta[top] + '0'), --top; return *this;} Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}Writer(){}}cout;
} const char el = '\n'; const char sp = ' ';
#define cin Fastio :: cin
#define cout Fastio :: cout
#define rep(i,a,b) for (register int i = (a), i##_ = (b) + 1; i < i##_; ++i)
#define pre(i,a,b) for (register int i = (a), i##_ = (b) - 1; i > i##_; --i)
const int N = 1e5 + 10;
int n, m, rge, l, r, k, a[N], buk[N], lst[N];
namespace hjt_tree {
#define ls(n) tr[n].lson
#define rs(n) tr[n].rson
#define sum(n) tr[n].sum
int mlc;
struct SegmentCitrus {
int lson, rson, sum;
SegmentCitrus & operator = (const SegmentCitrus & b) {
lson = b.lson; rson = b.rson; sum = b.sum;
return *this;
}
} tr[N * 320];
inline int mirize(int proto, int l, int r, int pos) {
int kage = ++mlc;
tr[kage] = tr[proto];
sum(kage) ++;
int mid = l + r >> 1;
if (l < r) {
if (pos <= mid) ls(kage) = mirize(ls(proto), l, mid, pos);
else rs(kage) = mirize(rs(proto), mid+1, r, pos);
} return kage;
}
inline int qry(int lf, int rt, int l, int r, int L, int R) {
if (L <= l and r <= R) return sum(rt) - sum(lf);
int mid = l + r >> 1;
return (L <= mid ? qry(ls(lf), ls(rt), l, mid, L, R) : 0) + (mid < R ? qry(rs(lf), rs(rt), mid + 1, r, L, R) : 0);
}
#undef ls
#undef rs
#undef sum
} ; using namespace hjt_tree;
struct SegmentRange {
#define ls (p << 1)
#define rs (p << 1 | 1)
#define st(p) seg[p]
#define itl(p) ((-- lower_bound(st(p).begin(), st(p).end(), vn( L, 0 ) ) ) -> rt)
#define itr(p) ((-- upper_bound(st(p).begin(), st(p).end(), vn( R, 0 ) ) ) -> rt)
struct vn {
int pos, rt;
vn() = default;
vn(int _p, int _rt) : pos(_p), rt(_rt) {}
bool operator < (const vn & b) const {
return pos < b.pos;
}
} ; vector <vn> seg[N << 2];
void build(int p, int l, int r) {
st(p).emplace_back( 0, 0 );
if (l == r) return;
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid+1, r);
}
void insert(int p, int l, int r, int pos, int val) {
st(p).emplace_back( pos, mirize(st(p).back().rt, 0, n, val) );
if (l == r) return;
int mid = l + r >> 1;
if (a[pos] <= mid) insert(ls, l, mid, pos, val);
else insert(rs, mid+1, r, pos, val);
}
int query(int p, int l, int r, int L, int R, int k) {
if (l == r) return (k == qry(itl(p), itr(p), 0, n, 0, L - 1) ? l : -1) ;
int cnt = qry(itl(ls), itr(ls), 0, n, 0, L - 1), mid = l + r >> 1;
if (k <= cnt) return query(ls, l, mid, L, R, k);
else return query(rs, mid+1, r, L, R, k - cnt);
}
#undef ls
#undef rs
#undef st
#undef itl
#undef itr
} T;
signed main() {
cin >> n >> m;
rep(i,1,n) cin >> a[i], lst[i] = buk[a[i]], buk[a[i]] = i, rge = max(rge, a[i]);
T.build(1, 1, rge);
rep(i,1,n) T.insert(1, 1, rge, i, lst[i]);
rep(i,1,m) {
cin >> l >> r >> k;
cout << T.query(1, 1, rge, l, r, k) << '\n';
}
}
关于“能不能再给力一点啊？”这件事，先咕着。
