牛客网-序列-莫队

题目
前几天学了下大名鼎鼎的莫队算法，精辟，也是挺暴力的一种算法，这题就当留个板子吧

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e4+5;
LL a[N], Ans, ans[N], cnt[N], k;
int pos[N], n, m, L, R;
struct node{
  int l, r, id;
  bool operator < (const node &a) const {
    if(pos[l] == pos[a.l] ) return r < a.r;
    return pos[l] < pos[a.l];
  }
}Q[N];
vector<LL>v;
LL getid(LL x) {
  return lower_bound(v.begin(), v.end(), x) - v.begin();
}
void add(LL x) {
  Ans += cnt[a[x]];
  cnt[a[x]]++;
}
void del(int x) {
  cnt[a[x]]--;
  Ans -= cnt[a[x]];
}
int main() {
  int t;
  scanf("%d", &t);
  while(t--) {
    scanf("%d%d%I64d", &n, &m, &k);
    v.clear();
    int sz = sqrt(n);
    L = 1, R = 0, Ans = 0;
    memset(cnt, 0, sizeof(cnt));
    v.push_back(0);
    for(int i = 1; i <= n; i++) {
      scanf("%I64d", &a[i]);
      a[i] = (a[i-1] + a[i]) % k;
      v.push_back(a[i]);
      pos[i] = (i - 1) / sz;
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i = 0; i <= n; i++) {
      a[i] = getid(a[i]);
    }
    for(int i = 1; i <= m; i++) {
      scanf("%d%d", &Q[i].l, &Q[i].r);
      Q[i].id = i;
    }
    sort(Q+1, Q+1+m);
    for(int i = 1; i <= m; i++) {
      while(L < Q[i].l) del(L++);
      while(L > Q[i].l) add(--L);
      while(R < Q[i].r) add(++R);
      while(R > Q[i].r) del(R--);
      ans[Q[i].id] = Ans + cnt[a[Q[i].l-1]];
    }
    for(int i = 1; i <= m; i++) {
      printf("%lld\n", ans[i]);
    }
  }
}