Little Elephant and Array - CodeForces220B 题解

据说莫队更简单，然而不会啊

考虑维护一个数组 $D$ ，使得 $D_l,D_{l+1},\dots,D_{r-1},D_r$ 的和为询问 $[l,r]$ 的答案。用线段树或树状数组都行（显然树状数组比较好写）。从左边开始遍历数组，当下标为 $i$ 时，我们应该处理完所有 $r=i$ 的询问。

下面我们用一个最简单的例子来说明这个思路（下标从 1 开始）:

$A:3,3,3,3,3 \\D:0,0,0,0,0$

当 $i=3$ 时，3 这个数第一次出现 3 次，所以我们应让 $D_1+1$ ，这样只有 $[1,3]$ 这个询问才会得到 1。

当 $i=4$ 时，按照刚才的想法，我们应让 $D_2+1$ :

$A:3,3,3,3,3 \\D:1,1,0,0,0$

但这时如果我们有 $[1,4]$ 的询问，那么就会得到 2，但答案应该为 0，所以我们这时应将 $D_1-2$ ：

$A: \quad 3,3,3,3,3 \\D:-1,1,0,0,0$

这样就能正确处理 $[1,4]$ 的询问了。

现在 $i=5$ 了，如果延续刚才的思路，现在应该是这样的：

$A: \quad 3,\enspace 3,3,3,3 \\D:-1,-1,1,0,0$

这样一来， $[1,5]$ 的询问又不对了，所以我们应该让 $D_1+1$ 来抵消第二步。这就是这个题的基本思路。

代码

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define fore(i, l, r) for (int i = (int)(l); i <= (int)(r); ++i)
#define ford(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define endl '\n'
using namespace std;
 
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
 
int n, m, sqn;
const int N = 1e5 + 5;
struct node {
  int l, r, i;
  bool operator<(node a) { return r < a.r; } //按照询问的右边界从小到大排序
} itv[N];
int a[N], res[N], t[N];
int lowbit(int x) { return x & -x; }
void change(int x, int v) {
  for (int i = x; i <= n; i += lowbit(i))
    t[i] += v;
}
int sum(int x) {
  int sum = 0;
  for (int i = x; i; i -= lowbit(i))
    sum += t[i];
  return sum;
}
vector<int> cnt[N];//记录每个数字每次出现时的下标
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for1(i, n) cin >> a[i];
  forn(i, m) {
    int a, b;
    cin >> a >> b;
    itv[i] = node{a, b, i};
  }
  sort(itv, itv + m);
  int l, r;
  int j = 0;
  for1(i, n) {
    int x = a[i];
    if (x <= n) {
      cnt[x].push_back(i);//记录下标
      int cntt = cnt[x].size();//这个数目前出现的次数
      if (cntt >= x) {//对应前面 i=3 时的情况
        change(cnt[x][cntt - x], 1);
        if (cntt > x)//对应 i=4
          change(cnt[x][cntt - x - 1], -2);
        if (cntt > x + 1)//对应 i=5
          change(cnt[x][cntt - x - 2], 1);
      }
    }
    while (j < m && itv[j].r == i) {
      res[itv[j].i] = sum(itv[j].r) - sum(itv[j].l - 1);
      j++;
    }//处理所有 r=i 的询问
  }
  forn(i, m) cout << res[i] << endl;
}