P7447[Ynoi] rgxsxrs 题解
CLZY
·
·
题解
传送门
题意简述
给你一个长为 n 的序列 A_i，再给你 m 次操作，操作有两种类型：
题目分析
大致做法：倍增分块 + 序列线段树 + 底层分块。
稍加考虑就会发现序列上和值域上都必须要用某种数据结构来维护（就是某个数据结构套某个数据结构而且我不会）。
目前蒟蒻只会这种做法（而且还是看了题解，这个倍增分块让蒟蒻大受震撼）。
upd：问了 julao ，其实分块套 splay 也可以做，代码难度应该会低一些如果你没有常数。
因为值域 10^9 非常不好做，考虑特殊的倍增分块，也就是把值为 [B^i,B^{i+1}) 的数分在一个值域块里。
为什么会考虑这种分块呢？
首先考虑比较暴力的做法，建一棵序列线段树，直接维护序列上区间的信息。
这样子时间必然爆炸，因为一个操作可能会被无限细分到叶子。考虑上述做法的复杂度瓶颈，显然是无限细分，考虑对值域进行处理，将值域分成多个块，尽可能降低每个块的细分复杂度。
假如我们已经把值域划分成了 cnt 个块，每个块里都有这么一个序列线段树，但是这个序列线段树只接受值域在该块之内的数的贡献。
对于每一块的线段树我们可以就像上面的 3 个操作一样处理，同样的，考虑细分复杂度，因为此时有多棵线段树，所以细分变成了两个部分：区间打懒标记和从这个块中剔除一个减去 x 就小于值域下界的叶子节点并跌落加入另一个块中。
首先向线段树加入一个数显然是 \log{n} 的。又因为每个数最多跌落 cnt 次（在每一个块依次跌落一遍），所以整体来看跌落的最坏复杂度是 n\times cnt\times \log{n} 的。
那么打懒标记呢？
我们会发现，我们前两种情况复杂度只和分的块数有关，但我们怎么分块并不确定，考虑保证 cnt 较小时让 3 最省时间。
设第三种情况的所在块长为 len，那么这种情况一个数要被减去 x，就最多只能够被减去 cnt\times len/x 次。
我们考虑比较刁钻的情况，就是 x 尽量小，它就是那个块的下界 l，所以我们就要让复杂度 n\times \log{n}\times cnt\times len/l 尽量小，同时 cnt 也尽量小。考虑固定 len/l，设它为 B，那么 cnt 等于 \log_{B}{10^9}，B 在 16 时最优。
那么根据以上柿子，我们发现其实我们可以采用倍增分块的方式，得到优秀的时间。
因为此时 cnt=\log_{B}{10^9}，所以最终时间复杂度为：
O((n+m)\times \log_B{10^9}\times \log{n}+n\times B\times \log{n}\times \log_B{10^9})
于是我们可以按照上述写法开心地~MLE 了。
那怎么办呢？考虑空间复杂度瓶颈，就是线段树。考虑优化。
我们发现对于一棵线段树，最占空间的是比较底层的节点，尤其是叶子。
于是我们可以设置一个常数 K，让线段树 \le K 的区间的处理直接变成下传标记在序列上暴力，之后再上传。我们可以这样很可观地以大常数的时间代价换取空间。
所以所谓的底层分块不就是在底层直接暴力吗。
*******
## 代码及细节
- **注意 long long 和 int**。
- 注意及时在**底层分块与线段树间和线段树内部**下传标记，上传信息。
- 最好加上快读快输。
************
```cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, r, l) for (int i = (r); i >= (l); --i)
#define ls (num << 1)
#define rs (num << 1 | 1)
const int inf = INT_MAX, df = 2e4 + 7, N = 5e5 + 7, B = 16, K = 32 ;/*相对较好的参数*/
int i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z;
long long ma[9][df << 1];
long long tag[9][df << 1];
int mx[9][df << 1], mn[9][df << 1];
int a[N];
long long sum[9][df << 1];
long long lb[9], rb[9]; /*这里是倍增分块的上界和下界*/
/*
ma:区间有几个数
sum:区间和
mx:区间最大值
mn:区间最小值
tag:懒标记
*/
void pushup(int blk, int num)
{
ma[blk][num] = ma[blk][ls] + ma[blk][rs];
sum[blk][num] = sum[blk][ls] + sum[blk][rs];
mx[blk][num] = max(mx[blk][ls], mx[blk][rs]);
mn[blk][num] = min(mn[blk][ls], mn[blk][rs]);
return;
}
/*线段树上传信息*/
void pushdown(int blk, int num)
{
if (!tag[blk][num])
return;
tag[blk][ls] += tag[blk][num] * (ma[blk][ls] != 0), tag[blk][rs] += tag[blk][num] * (ma[blk][rs] != 0);
if (ma[blk][ls])
sum[blk][ls] -= tag[blk][num] * ma[blk][ls], mx[blk][ls] -= tag[blk][num], mn[blk][ls] -= tag[blk][num];
if (ma[blk][rs])
sum[blk][rs] -= tag[blk][num] * ma[blk][rs], mx[blk][rs] -= tag[blk][num], mn[blk][rs] -= tag[blk][num];
tag[blk][num] = 0;
return;
}
/*线段树下传标记*/
int getblk(int x)
{
int now = 1;
while (x > rb[now])
now++;
return now;
}
/*x在第几个值域块*/
void blk_pushdown(int blk, int le, int rig, long long &x)
{
if (!x)
return;
rep(i, le, rig) if (a[i] >= lb[blk] && a[i] <= rb[blk]) a[i] -= x;
x = 0;
return;
}
/*线段树的叶子节点向序列下传标记*/
void blk_pushup(int blk, int le, int rig, int num)
{
ma[blk][num] = 0, sum[blk][num] = 0, mx[blk][num] = 0, mn[blk][num] = inf;
rep(i, le, rig)
{
if (a[i] >= lb[blk] && a[i] <= rb[blk])
{
ma[blk][num]++;
sum[blk][num] += a[i];
mx[blk][num] = max(mx[blk][num], a[i]);
mn[blk][num] = min(mn[blk][num], a[i]);
}
}
return;
}
/*把序列的信息上传到线段树的叶子节点上*/
void insert(int blk, int num, int le, int rig, int p, int x)
{
if (rig - le + 1 <= K)
{
blk_pushdown(blk, le, rig, tag[blk][num]);
a[p] = x;
blk_pushup(blk, le, rig, num);
return;
}
int mid = (le + rig) >> 1;
pushdown(blk, num);
if (p <= mid)
insert(blk, ls, le, mid, p, x);
else
insert(blk, rs, mid + 1, rig, p, x);
pushup(blk, num);
return;
}
/*线段树插入节点*/
void blk_upd(int blk, int le, int rig, int x)
{
rep(i, le, rig) if (a[i] >= lb[blk] && a[i] <= rb[blk] && a[i] > x)
{
a[i] -= x;
if (a[i] < lb[blk])
{
insert(getblk(a[i]), 1, 1, n, i, a[i]);
} /*插入另一个块的线段树*/
}
return;
}
/*块内暴力执行1号操作*/
void blk_qry(int blk, long long &ans, int &maxn, int &minn, int le, int rig, int l, int r)
{
rep(i, max(le, l), min(rig, r))
{
if (a[i] >= lb[blk] && a[i] <= rb[blk])
{
ans += a[i], maxn = max(maxn, a[i]), minn = min(minn, a[i]);
}
}
return;
}
/*块内暴力执行查询*/
void upd(int blk, int num, int le, int rig, int l, int r, int x)
{
if (mx[blk][num] <= x)
return; /*小于就跳过*/
if (rig - le + 1 <= K)
{
blk_pushdown(blk, le, rig, tag[blk][num]);
l = max(l, le), r = min(r, rig);
blk_upd(blk, l, r, x);
blk_pushup(blk, le, rig, num);
return;
} /*到达叶子暴力修改*/
if (le >= l && rig <= r && mn[blk][num] - lb[blk] >= x)
{
sum[blk][num] -= x * ma[blk][num], mn[blk][num] -= x, mx[blk][num] -= x; /*直接打懒标记*/
tag[blk][num] += x;
return;
}
int mid = (le + rig) >> 1;
pushdown(blk, num);
if (l <= mid)
upd(blk, ls, le, mid, l, r, x);
if (r > mid)
upd(blk, rs, mid + 1, rig, l, r, x);
pushup(blk, num);
return;
}
/*线段树上执行操作*/
void qry(long long &ans, int &maxn, int &minn, int blk, int num, int le, int rig, int l, int r)
{
if (le >= l && rig <= r)
{
ans += sum[blk][num], maxn = max(maxn, mx[blk][num]), minn = min(minn, mn[blk][num]);
return;
} /*叶子节点暴力查询*/
if (rig - le + 1 <= K)
{ /*完全包含，直接统计*/
blk_pushdown(blk, le, rig, tag[blk][num]);
blk_qry(blk, ans, maxn, minn, le, rig, l, r);
blk_pushup(blk, le, rig, num);
return;
}
int mid = (le + rig) >> 1;
pushdown(blk, num); /*注意及时下传和上传*/
if (l <= mid)
qry(ans, maxn, minn, blk, ls, le, mid, l, r);
if (r > mid)
qry(ans, maxn, minn, blk, rs, mid + 1, rig, l, r);
pushup(blk, num);
return;
}
inline int read()
{
int x = 0, y = 1;
char ch = getchar();
while (ch > '9' || ch < '0')
y = (ch == '-') ? -1 : 1, ch = getchar();
while (ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x * y;
}
void fwrite(int x)
{
if (x > 9)
fwrite(x / 10);
putchar(x % 10 + '0');
return;
} /*最好加上快读快输*/
void llfwrite(long long x)
{
if (x > 9)
llfwrite(x / 10);
putchar(x % 10 + '0');
return;
}
int main()
{
rep(j, 1, 8) rep(i, 0, df * 2 - 2) mn[j][i] = inf, mx[j][i] = 0;/*初始化*/
n = read(), q = read();
rep(i, 1, 8) lb[i] = rb[i - 1] + 1, rb[i] = lb[i] * B - 1;/*预处理*/
rep(i, 1, n) a[i] = x = read(), insert(getblk(x), 1, 1, n, i, x);
int op = 0, l = 0, r = 0, x = 0, lastans = 0, maxn = 0, minn = 0;
long long ans = 0;
while (q--)
{
op = read(), l = read() ^ lastans, r = read() ^ lastans;
if (op == 1)
{
x = read() ^ lastans;/*强制在线*/
rep(i, 1, 8) if (rb[i] >= x) upd(i, 1, 1, n, l, r, x);
}
else
{
ans = 0, maxn = 0, minn = inf;
rep(i, 1, 8) qry(ans, maxn, minn, i, 1, 1, n, l, r);
llfwrite(ans), putchar(' '), fwrite(minn), putchar(' '), fwrite(maxn), putchar('\n');
lastans = ans % 1048576;
}
}
}
```
**************
## 写在后面
这道题主要妙在它的倍增分块，底层分块，以及对时间复杂度的分析的优（du）秀（liu）技巧，是一道练习数据结构和代码能力的好题。