Description
- 给定一个长度为\(n\)的序列\(a\)，有\(m\)次操作：
- (1).把区间\([l,r]\)中大于\(v\)的数减去\(v\)
- (2).查询区间\([l,r]\)中\(v\)的出现次数
- 所有输入均在\([1,100000]\)范围内
Solution
这种神仙题当然是分块- 如果只考虑整块操作，那么处于同一块且相同的数，每次要么一起减\(v\)要么一起不减
- 那么考虑将同一块中相同的数放一起处理
- 维护并查集
- 记\(h[x][y]\)为块\(x\)中，数值\(y\)的第一次出现位置，没有出现则为\(0\)
- \(val[find(x)]\)为\(a[x]\)所在并查集的数值（\(find(x)\)为\(x\)所在并查集的根，也就是\(h[\)\(x\)所在块\(][a[x]]\)）
- \(cnt[find(x)]\)表示这一块与\(a[x]\)相同大小的数有几个，即所在并查集的大小
- 对于两边不完整的块的单点修改，修改后要重新计算整块的信息
- 对于整块修改，记\(mx[x]\)为块\(x\)内的最大值
- 发现\(mx[x]\)的总减少量最多\(100000\)
- 那么考虑用\(O(v)\)的时间复杂度完成一次整块修改
- 如果\(mx[x]<=2v\)，那么枚举需要减\(v\)的数值，最多\(v\)种
- 如果\(mx[x]>2v\)呢？
- 又发现不论如何，小于等于\(v\)的数值总是不超过\(v\)种
- 因此可以将小于等于\(v\)的数加上\(v\)，然后整块减\(v\)
- 需要打标记，记\(tag[x]\)为块\(x\)整块减去的值
- 那么上面的分类讨论改为\(mx[x]-tag[x]\)与\(2v\)比较大小
- 整块修改时也要修改\(h\)，\(cnt\)和\(val\)
- 发现\(mx[x]\)也需要修改
- 如果\(mx[x]>2v\)，执行“将小于等于\(v\)的数加上\(v\)”后，\(mx[x]\)不变
- 否则，\(mx[x]\)必定不增大，那么写一句\(while(!h[x][mx[x]]) mx[x]--;\)就好了
- 查询整块利用\(cnt[v][tag[x]+v]\)即可，注意\(tag[x]+v\)可能会越界
Code
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
template <class t>
inline void read(t & res)
{
char ch;
while (ch = getchar(), !isdigit(ch));
res = ch ^ 48;
while (ch = getchar(), isdigit(ch))
res = res * 10 + (ch ^ 48);
}
const int e = 1e5 + 5, o = 320;
int h[o][e];
int bl[o], br[o], bel[e], f[e], cnt[e], n, m, val[e], mx[o], tag[o], a[e], s;
inline int find(int x)
{
return f[x] == x ? x : f[x] = find(f[x]);
}
inline void merge(int x, int y)
{
cnt[x] += cnt[y];
f[y] = x;
}
inline void build(int x)
{
int l = bl[x], r = br[x], i;
mx[x] = 0;
for (i = l; i <= r; i++) a[i] = val[find(i)];
for (i = l; i <= r; i++)
{
f[i] = i;
cnt[i] = 1;
h[x][a[i]] = 0;
mx[x] = max(mx[x], a[i]);
}
for (i = l; i <= r; i++)
{
int &t = h[x][a[i]];
if (!t)
{
t = i;
val[i] = a[i];
}
else merge(t, i);
}
}
inline void upt(int l, int r, int v)
{
int i, x = bel[l], frm = bl[x], to = br[x];
for (i = frm; i <= to; i++)
{
a[i] = val[find(i)];
h[x][a[i]] = 0;
}
for (i = l; i <= r; i++)
if (a[i] - tag[x] > v) a[i] -= v;
for (i = frm; i <= to; i++)
{
val[i] = a[i];
f[i] = i;
}
build(x);
}
inline void change(int x, int v)
{
if (mx[x] - tag[x] <= v) return;
int i, &t = tag[x], lim = min(mx[x], t + v);
if (mx[x] - t >= 2 * v)
{
for (i = t + 1; i <= lim; i++)
{
int &y = h[x][i];
if (!y) continue;
int &u = h[x][i + v];
if (!u)
{
u = y;
val[y] = i + v;
y = 0;
}
else
{
merge(u, y);
y = 0;
}
}
t += v;
}
else
{
for (i = t + v + 1; i <= mx[x]; i++)
{
int &y = h[x][i];
if (!y) continue;
int &u = h[x][i - v];
if (!u)
{
u = y;
val[y] = i - v;
y = 0;
}
else
{
merge(u, y);
y = 0;
}
}
while (!h[x][mx[x]]) mx[x]--;
}
}
inline void update(int l, int r, int v)
{
int x = bel[l], y = bel[r];
if (x == y)
{
upt(l, r, v);
return;
}
upt(l, br[x], v);
upt(bl[y], r, v);
int i;
for (i = x + 1; i < y; i++) change(i, v);
}
inline int ask(int l, int r, int v)
{
int i, res = 0, x = bel[l];
for (i = l; i <= r; i++)
res += val[find(i)] - tag[x] == v;
return res;
}
inline int qsum(int x, int v)
{
int y = tag[x] + v;
return y <= 1e5 ? cnt[h[x][y]] : 0;
}
inline int query(int l, int r, int v)
{
int x = bel[l], y = bel[r];
if (x == y) return ask(l, r, v);
int i, res = ask(l, br[x], v) + ask(bl[y], r, v);
for (i = x + 1; i < y; i++) res += qsum(i, v);
return res;
}
int main()
{
int i, j, tot = 0, opt, l, r, v;
read(n); read(m);
s = sqrt(n);
for (i = 1; i <= n; i++)
{
read(a[i]);
f[i] = i;
cnt[i] = 1;
val[i] = a[i];
}
for (i = 1; i <= n; i = j + 1)
{
j = min(n, i + s - 1);
bl[++tot] = i;
br[tot] = j;
for (int k = i; k <= j; k++) bel[k] = tot;
}
for (i = 1; i <= tot; i++) build(i);
while (m--)
{
read(opt);
read(l);
read(r);
read(v);
if (opt == 1) update(l, r, v);
else printf("%d\n", query(l, r, v));
}
return 0;
}