题解 P3834 【【模板】可持久化线段树 1(主席树)】
Juan_feng
2019-03-15 22:03:31
早就想发一篇纯分块的题解了, 因为各种事情耽误了几个月......
所以蒟蒻也就不多废话了, 直接进入正题:
**值域分块在n sqrt(n)的时间内解决该问题**
那么我们该怎样解决这个问题呢qwq?
我们先把数列分块, 再把值域分块, 然后维护两个数组cnt1, cnt2, cnt1(i, j)表示前i个数列块中第j个值域块的数值出现的次数和, cnt2(i, j)表示前i个块中j这个数字出现的次数。 这两个数组显然可以在n sqrt(n)的时间内处理完成。
那么接下来当我们求l r 区间的第k大的时候, 对于散块, 我们用两个临时数组san, san2 来记录和cnt1 cnt2一样的东西(只不过这个记录的是散块中的信息, 而不是前缀和), 然后对于整块, 因为我们已经处理出了前缀和, 所以可以直接从头开始扫值域块, 累加cnt1+san , 直到这个数量大于我们要查询的k, 这时候就能确定我们要查询的数值再哪一个值域块中了。 下面只要在扫一遍这个值域块中的每一个数, 通过cnt2和san2 就能知道具体要查询的是哪个数了qwqwq。
那么就没啥了啊qwqwq 如果有什么问题的话私信小蒟蒻就好啦qwqwq
**那么代码如下**
```
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#define maxn 200010
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;
int n, m, c, r, t, x, y, k;
int sq, sq2;
int nw[maxn], a[maxn], b1[maxn], b2[maxn], cnt1[500][500], cnt2[480][maxn], q[maxn][4], z[maxn];
int san[500], san2[maxn];
inline void in(re int &x){
x=0;int bl = 1;char c=getchar();
while(c<'0'||c>'9'){
if(c == '-')
bl = -1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
x *= bl;
}
void out(re int a){
if(a < 0) {
putchar('-');
a = -a;
}
if(a>=10)out(a/10);
putchar(a%10+'0');
}
int get_val(int x, int y, int k) {
int res = 0, pd = 0;
FOR(i, x, min(y, b1[x]*sq))
++san[b2[nw[i]]], ++san2[nw[i]];
if(b1[x] != b1[y])
FOR(i, (b1[y]-1)*sq+1, y)
++san[b2[nw[i]]], ++san2[nw[i]];
FOR(i, 1, b2[z[0]]) {
int ld = cnt1[b1[y]-1][i]-cnt1[b1[x]][i];
if(ld < 0) ld = 0;
if(res+(ld+san[i]) < k) {
res += san[i];
if(cnt1[b1[y]-1][i]-cnt1[b1[x]][i] > 0)
res += cnt1[b1[y]-1][i]-cnt1[b1[x]][i];
}
else {
pd = i;
break;
}
}
int anss = -1;
FOR(i, (pd-1)*sq2+1, pd*sq2) {
res += san2[i];
if(cnt2[b1[y]-1][i]-cnt2[b1[x]][i] > 0)
res += cnt2[b1[y]-1][i]-cnt2[b1[x]][i];
if(res >= k) {
anss = z[i];
break;
}
}
FOR(i, x, min(y, b1[x]*sq))
--san[b2[nw[i]]], --san2[nw[i]];
if(b1[x] != b1[y])
FOR(i, (b1[y]-1)*sq+1, y)
--san[b2[nw[i]]], --san2[nw[i]];
return anss;
}
int main() {
in(n), in(m);
sq = sqrt(n);
FOR(i, 1, n)
in(a[i]), b1[i] = (i-1)/sq+1, z[++z[0]] = a[i];
FOR(i, 1, m) {
in(q[i][1]),
in(q[i][2]),
in(q[i][3]);
}
sort(z+1, z+z[0]+1);
z[0] = unique(z+1, z+z[0]+1)-z-1;
sq2 = sqrt(z[0]);
FOR(i, 1, z[0])
b2[i] = (i-1)/sq2+1;
FOR(i, 1, n) {
nw[i] = lower_bound(z+1, z+z[0]+1, a[i])-z; //nw为a排序后的位置,处理cnt1, cnt2
++cnt1[b1[i]][b2[nw[i]]];
++cnt2[b1[i]][nw[i]];
}
FOR(i, 1, b1[n]) { //处理前缀和
FOR(j, 1, b2[z[0]])
cnt1[i][j] += cnt1[i-1][j];
FOR(j, 1, z[0])
cnt2[i][j] += cnt2[i-1][j];
}
FOR(i, 1, m) {
out(get_val(q[i][1], q[i][2], q[i][3]));
putchar(10);
}
}
```