题解 P3834 【【模板】可持久化线段树 1(主席树)】

Juan_feng

2019-03-15 22:03:31

Solution

早就想发一篇纯分块的题解了, 因为各种事情耽误了几个月...... 所以蒟蒻也就不多废话了, 直接进入正题: **值域分块在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); } } ```