「突刺贯穿的第二分块」。
和隔壁第一分块差不多吧（
对于一个块，设最大值为 \(k\)，进行参数为 \(x\) 的修改操作。
若 \(k \le 2x\)，则只需要将值域区间 \((x,k]\) 合并到 \([1,k - x]\) 上，那么此时操作完后 \(k\) 至少减小 \(k-x\)，并且需要合并的数值也是 \(O(k-x)\) 种的。
若 \(k > 2x\)，则只需要将值域区间 \([1,x]\) 合并到 \([x,2x]\) 上，再打上区间减 \(x\) 的标记，那么此时操作完后 \(k\) 至少减小 \(x\)，并且需要合并的数值也是 \(O(x)\) 种的。
也即，每次操作后 \(k\) 是不增的，并且需要合并的数值也是减少的值级别的。
也就是最终要合并的数值的种类总共是值域级别的。
那么如何 \(O(1)\) 合并两个值？
并查集即可，同时简单地维护一下每个块内每个值的个数。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
w && (x = -x);
}
const int N = 5e5;
const int BLK = 921;
const int CNT = N / BLK + 1;
int n,m,block;
int a[N + 5],pos[N + 5];
int fa[N + 5],fir[N + 5],mx,tag;
int cnt[N + 5];
inline int get(int x)
{
return !fa[x] ? x : (fa[x] = get(fa[x]));
}
struct s_query
{
int op,l,r,x,ans;
} qry[N + 5];
inline void merge(int x,int y)
{
if(!fir[x])
return ;
a[fir[x]] = y;
if(cnt[x] > cnt[y] || !fir[y])
fir[y] && (fa[fir[y]] = fir[x]),fir[y] = fir[x];
else
fa[fir[x]] = fir[y];
cnt[y] += cnt[x],cnt[x] = fir[x] = 0;
}
void solve(int p)
{
memset(fir,0,sizeof fir),memset(cnt,0,sizeof cnt),mx = tag = 0;
for(register int i = (p - 1) * block + 1;i <= min(p * block,n);++i)
!fir[a[i]] ? (fir[a[i]] = i,fa[i] = 0) : (fa[i] = fir[a[i]]),++cnt[a[i]],mx = max(mx,a[i]);
for(register int i = 1;i <= m;++i)
{
int op = qry[i].op,l = qry[i].l,r = qry[i].r,x = qry[i].x,&ans = qry[i].ans;
if(p == pos[l])
{
if(op == 1)
{
for(register int i = (p - 1) * block + 1;i <= min(p * block,n);++i)
fir[a[i] = a[get(i)]] = 0,--cnt[a[i]];
for(register int i = l;i <= min(p * block,r);++i)
a[i] - tag > x && (a[i] -= x);
mx = 0;
for(register int i = (p - 1) * block + 1;i <= min(p * block,n);++i)
!fir[a[i]] ? (fir[a[i]] = i,fa[i] = 0) : (fa[i] = fir[a[i]]),++cnt[a[i]],mx = max(mx,a[i] - tag);
}
else
for(register int i = l;i <= min(p * block,r);++i)
a[get(i)] - tag == x && ++ans;
}
else if(p == pos[r])
{
if(op == 1)
{
for(register int i = (p - 1) * block + 1;i <= min(p * block,n);++i)
fir[a[i] = a[get(i)]] = 0,--cnt[a[i]];
for(register int i = (p - 1) * block + 1;i <= r;++i)
a[i] - tag > x && (a[i] -= x);
mx = 0;
for(register int i = (p - 1) * block + 1;i <= min(p * block,n);++i)
!fir[a[i]] ? (fir[a[i]] = i,fa[i] = 0) : (fa[i] = fir[a[i]]),++cnt[a[i]],mx = max(mx,a[i] - tag);
}
else
for(register int i = (p - 1) * block + 1;i <= r;++i)
a[get(i)] - tag == x && ++ans;
}
else if(p > pos[l] && p < pos[r])
{
if(op == 1)
{
if(mx <= x * 2)
{
for(register int i = x + tag + 1;i <= mx + tag;++i)
merge(i,i - x);
mx > x && (mx -= x,mx = max(mx,x));
}
else
{
for(register int i = tag + 1;i <= x + tag;++i)
merge(i,i + x);
mx -= x,tag += x;
}
}
else
x + tag <= N && (ans += cnt[x + tag]);
}
}
}
int main()
{
read(n),read(m),block = BLK;
for(register int i = 1;i <= n;++i)
read(a[i]),pos[i] = (i - 1) / block + 1;
for(register int i = 1;i <= m;++i)
read(qry[i].op),read(qry[i].l),read(qry[i].r),read(qry[i].x);
for(register int i = 1;i <= pos[n];++i)
solve(i);
for(register int i = 1;i <= m;++i)
qry[i].op == 2 && printf("%d\n",qry[i].ans);
}