[Ynoi2018] 五彩斑斓的世界 题解
人生第一个大分块
题意
《第二分块》
长度为 \(n\) 的序列 \(\{a\}\)，\(m\) 次询问。
写一个数据结构，支持以下操作：
- 区间 \([l,r]\) 中大于 \(x\) 的数减去 \(x\)。
- 区间 \([l,r]\) 中询问 \(x\) 的出现次数。
\(n \le 10^6\)，\(m \le 5 \times 10^5\),\(a_i,x \le 10^5 + 1\)。
分析和题解
首先可以注意到的是，值域很小。操作只会让数字变小，不会变大。
一个小小的想法就是均摊。但是这个属于说起来容易，做起来不容易的那种。不像一些比较显然的题目，想到“均摊”就能直接做的。
那么我们就得先考虑怎么利用值域实现“大于 \(x\) 的减少 \(x\)”。
基于值域的减法
我们可以维护一个并查集。
具体地，\(fa(i)\) 表示的是序列 \(\{a\}\) 中，\(a_i\) 实际上变成的元素的下标。即，如果 \(a_i\) 因为某个减法操作被修改成另一个值，恰好是 \(a_j\)，那么 \(fa(i) = j\)。
之后维护 \(rt(x)\) 表示 \(x\) 这个值在序列 \(\{a\}\) 中第一次出现的下标。即，如果 \(a_i\) 这个值在 \(\{a\}\) 是第一次出现，那么 \(rt(a_i) = i\)。
维护一个逆于 \(rt\) 的映射 \(val\)。即，\(val(rt(a_i)) = a_i\)。
维护 \(sz(x)\) 表示 \(x\) 这个值的出现次数。
这样，我们可以对于所有是同一个值 \(x\) 的元素都直接并进 \(fa(rt(x))\)。
设我们把值为 \(x\) 的合并到值为 \(y\) 的上。
- 如果 \(rt(y)\) 不存在，\(rt(y) = rt(x), val(rt(y)) = y\)。
- 否则，\(fa(rt(x)) = rt(y)\)。
- 不论如何，都计算 \(sz(y) += sz(x)\)，并清空关于 \(x\) 的信息：\(sz(x) = rt(x) = 0\)。
模拟一下：
实现了这一部分之后，我们就可以基于值域进行一个减法运算了。
比如，给 \(k\) 减去 \(x\)，相当于是把 \(k\) 合并到 \(k-x\)。
比如，大于 \(x\) 的减去 \(x\)，相当于是把 \([x + 1 ,maxv]\) 合并到 \([1,maxv - x]\)。
怎么均摊比较合适
我们可以看到，如果只是朴素实现刚才的功能的话，我们花费 \(O(maxv - x)\) 的时间，让值域缩小 \(x\)。
但是，如果每次修改的 \(x\) 均为 \(1\)，那么这种方法就会被卡死。
所以我们需要一个能在花费一定数量时间，就必然缩小至少是相当范围值域的均摊的做法。
人类智慧：操作 \(1\) 相当于是小于等于 \(x\) 的加 \(x\)，再区间减 \(x\)。而区间减相当于对于这个区间整体平移，不会影响到这个区间的极差，也就是说，不会影响值域“范围”。可以打减法标记实现。
我们设块内最大值为 \(maxv\)，分类讨论：
- \(maxv > 2 \times x\)，这个时候我们可以使用人类智慧，把 \([1,x]\) 合并到 \([1 + x,2 \times x]\)。
- \(maxv \le 2 \times x\)，这个时候我们使用原来的方法，把 \([x + 1,maxv]\) 合并到 \([1,maxv - x]\)。
也就是说：
- \(maxv > 2 \times x\)，花费 \(O(x) \times O(\text{ds})\) 的时间把范围缩小 \(O(x)\)。
- \(maxv \le 2 \times x\)，花费 \(O(maxv - x) \times O(\text{ds})\) 的时间把范围缩小 \(O(maxv - x)\)。
这样就可以均摊了。最多是 \(10^5 \times O(\text{ds})\)。
空间
\(\text{lxl}\) 卡了空间。
由于答案可加，我们可以用询问离线化的技巧。
枚举每个块，对于每个块枚举询问，算出这个块对于某一次询问的贡献，存到答案里面。
这样，下一个块就可以接着利用上一个块的空间。
代码
#include
#define DEBUG puts("QAQ")
#define openFile(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
#define NOSYNC ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define FOR(i,j,k) for(int (i) = (j); (i) <= (k); ++ (i))
#define RFOR(i,j,k) for(int (i) = (j); (i) >= (k); -- (i))
#define For(i,j,k) for(int (i) = (j); (i) < (k); ++ (i))
#define RFor(i,j,k) for(int (i) = (j); (i) > (k); -- (i))
#define SC(...) scanf(__VA_ARGS__)
#define PR(...) printf(__VA_ARGS__)
#define max(a,b) (a > b ? a : b)
using namespace std;
const int N = 1e6 + 5;
const int M = 5e5 + 5;
const int V = 1e5 + 5;
const int SQN = 1e3 + 5;
struct query {
int op, ql, qr, qx;
}Q[M]; int ans[M];
int n, m, a[N]; int B;
int fa[N], sz[V], rt[V], val[N];
int L[SQN], R[SQN]; //int bel[N];
int maxv, tag;
//-----------------------------------------------
inline int find(int x)
{
if(x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
inline void merge(int x, int y)
{
if(!rt[y]) rt[y] = rt[x], val[rt[y]] = y;
else fa[rt[x]] = rt[y];
sz[y] += sz[x];
sz[x] = rt[x] = 0;
/* 并查集的合并,把值为 x 的合并到值为 y 的
* fa[i] 表示 a[i] 实际的元素在 {a} 的下标
* rt[x] 表示 x 这个值在 {a} 中第一次出现的下标,即rt[a[i]] = i;
* val[i] 表示 i 这个下标的值，即 val[rt[a[i]]] = a[i];
* sz[x] 表示 x 这个值的出现次数
*/
}
//-----------------------------------------------
inline void build(int x)
{
maxv = tag = 0;
FOR(i,L[x],R[x])
{
maxv = max(maxv, a[i]);
if(rt[a[i]]) fa[i] = rt[a[i]];
else rt[a[i]] = fa[i] = i, val[i] = a[i];
++ sz[a[i]];
}
/* 构建一个整块
* 主要是并查集维护
*/
}
inline void rebuild(int x, int l, int r, int k)
{
FOR(i,L[x],R[x])
{
a[i] = val[find(i)];
rt[a[i]] = sz[a[i]] = 0;
a[i] -= tag;
}
FOR(i,L[x],R[x]) val[i] = 0;
l = max(l, L[x]); r = min(r, R[x]);
FOR(i,l,r) if(a[i] > k) a[i] -= k;
build(x);
/* 对散块 x 进行重构,只重构大区间 [l,r] 和散块 x 的重合部分
* 主要是根据并查集还原了原序列的值,
* 清空并查集对应部分维护的数据
* 减去减法标记
* 之后暴力进行一次操作 1
*/
}
inline void modify(int x)
{
if(maxv - tag <= 2 * x)
{
FOR(i,tag + x + 1,maxv)
if(rt[i]) merge(i,i - x);
maxv = min(maxv, tag + x);
}
/* maxv - tag 获取真实的 maxv, maxv <= 2x 时
* 我们缩小值域,把所有的比 x 大的都减去 x
* 这里由于有减法标记所以 [x + 1,maxv] 变成 [tag + x + 1,maxv]
*/
else
{
FOR(i,tag + 1,tag + x)
if(rt[i]) merge(i, i + x);
tag += x;
}
/* maxv > 2x 时选择转化
* 把所有 <= x 的都加上 x,再打一个减法标记
* 这里由于有减法标记所以事实上 [1,x] 变成 [1 + tag,x + tag]
*/
}
inline void query(int x, int p)
{
int l = Q[p].ql, r = Q[p].qr;
if(tag + Q[p].qx > 1e5 + 1) return;
if(l <= L[x] && r >= R[x]) ans[p] += sz[tag + Q[p].qx];
else
{
l = max(l, L[x]), r = min(r, R[x]);
FOR(i,l,r) if(val[find(i)] == tag + Q[p].qx) ++ ans[p];
}
/* tag + qx > 1e5 + 1,相当于询问的 x 超过了值域，不可能有值与其相等。
* 如果询问的 l <= L[x] <= R[x] <= r 那么这个整块可以直接算贡献
* 否则就暴力加个数
*/
}
int main()
{
SC("%d%d",&n,&m);
FOR(i,1,n) SC("%d",&a[i]);
FOR(i,1,m) SC("%d%d%d%d",&Q[i].op,&Q[i].ql,&Q[i].qr,&Q[i].qx);
B = sqrt(n);
FOR(i,1,B)
{
L[i] = (i - 1) * B + 1;
R[i] = i * B;
}
R[B] = n;
//FOR(i,1,B) FOR(j,L[i],R[i]) bel[j] = i;
//
FOR(i,1,B)
{
memset(rt, 0, sizeof(rt));
memset(sz, 0, sizeof(sz));
build(i);
FOR(j,1,m)
{
if(L[i] > Q[j].qr || R[i] < Q[j].ql) continue;
if(Q[j].op == 1)
{
if(Q[j].ql <= L[i] && Q[j].qr >= R[i]) modify(Q[j].qx);
else rebuild(i, Q[j].ql, Q[j].qr, Q[j].qx);
}
else if(Q[j].op == 2) query(i, j);
}
}
/* 对于每一块分别计算,复用内存,答案累加
* 按顺序枚举询问,看询问是否可以整块处理,不能整块处理就重构
*/
FOR(i,1,m) if(Q[i].op == 2) PR("%d\n",ans[i]);
return 0;
}