YNOI题.

Des.

区间$-x$, 区间查询$x$个数.

Sol.

分块, 对每个块维护减法标记和区间最大值, 粗略估计极差, 讨论几种情况:

  • 极差$< x$: 没得减.
  • 极差$\ge x$, 但$< 2x$: 把大于$x$的值都减掉. 这里要加速, 所以并查集维护. 直接把值相同的元素都挂到减后的值上.
  • 极差$\ge 2x$: 给所有$\le x$的加上$x$, 再整体打$x$的标记, 体现在极差上也有所缩小.

小块朴素.

这样询问的时候我们根据极差查数就可以了.

为什么能这么做??找一找这样分阈值的效果和套路.

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
#pragma GCC optimize("inline")
#pragma GCC optimize(3)
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e+5 + 5;
const int maxb = maxn / 650 + 5;

int n, m, a[maxn], blo, bel[maxn];
int mx[maxb], tag[maxb], f[maxb][maxn];
int bkt[maxb][maxn], in[maxb], out[maxb];

inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
int find(int *fa, int x) {
  return fa[x] ? fa[x] = find(fa, fa[x]) : x;
}
inline void modify(const int &l, const int &r, const int &x) {
  int lb = bel[l], rb = bel[r];
  for (register int i = l; i <= r && i <= out[lb]; ++i)
    if (((a[i] = find(f[lb], a[i])) - tag[lb]) > x) {
      bkt[lb][a[i]]--;
      a[i] -= x;
      bkt[lb][a[i]]++;
    }
  for (register int i = lb + 1; i < rb; ++i) {
    if (mx[i] - tag[i] > (x << 1)) {
      for (register int j = 1; j <= x; ++j) {
        f[i][j + tag[i]] = j + tag[i] + x;
        bkt[i][f[i][j + tag[i]]] += bkt[i][j + tag[i]];
      }
      tag[i] += x;
    } else {
      for (register int j = x + 1; j <= mx[i] - tag[i]; ++j) {
        f[i][j + tag[i]] = j + tag[i] - x;
        bkt[i][f[i][j + tag[i]]] += bkt[i][j + tag[i]];
      }
      mx[i] = min(mx[i], x + tag[i]);
    }
  }
  if (lb != rb) {
    for (register int i = in[rb]; i <= r; ++i) {
      if (((a[i] = find(f[rb], a[i])) - tag[rb]) > x) {
        bkt[rb][a[i]]--;
        a[i] -= x;
        bkt[rb][a[i]]++;
      }
    }
  }
}
inline int query(const int &l, const int &r, const int &x) {
  int lb = bel[l], rb = bel[r], ret = 0;
  for (register int i = l; i <= r && i <= out[lb]; ++i)
    if (find(f[lb], a[i]) - tag[lb] == x) ret++;
  for (register int i = lb + 1; i < rb; ++i) {
    if (tag[i] + x <= mx[i]) ret += bkt[i][x + tag[i]];
  }
  if (lb != rb) 
    for (register int i = in[rb]; i <= r; ++i)
      if (find(f[rb], a[i]) - tag[rb] == x) ret++;
  return ret;
}

int main() {
  n = rd(); m = rd();
  blo = 650;
  for (register int i = 1; i <= n; ++i) {
    a[i] = rd();
    bel[i] = (i - 1) / blo + 1;
    bkt[bel[i]][a[i]]++;
    if (!in[bel[i]]) in[bel[i]] = i;
  }
  for (int i = 1; i <= bel[n]; ++i)
    mx[i] = 1e+5, out[i] = i * blo;
  out[bel[n]] = n;
    
  int opt, l, r, x;
  while (m--) {
    opt = rd(); l = rd(); r = rd(); x = rd();
    if (opt == 1) {
      modify(l, r, x);
    } else if (opt == 2) {
      printf("%d\n", query(l, r, x));
    }
  } 
  return 0;
}