牛客小白月赛15-H-分块/主席树/技巧二分

题目
题目意思很简单，方法很多，就做个解法集合。
1.分块：
分块也是挺好写的。（写的少，出了好多细节问题）
刚开始想每块用个map维护的，然后超内存了，还是老老实实用vector。
坑点，l,r的大小不一定。
顺便分享一个stl函数，equal_range()，返回有序容器中valu对应的区间，返回的是一个pair(好东西!)

#include<bits/stdc++.h>
using namespace std;
int blo = 1000;
const int N = 1e5+5;
int a[N], l[N], r[N], bl[N];
int n, m;
vector<int>v[110];
int query(int L, int R, int x) {
  int num = 0;
  for(int i = L; i <= min(r[bl[L]], R); i++) {
    if(a[i] == x) num++;
  }
  if(bl[L] != bl[R]) {
    for (int i = l[bl[R]]; i <= R; i++) {
      if(a[i] == x) num++;
    }
    for(int i = bl[L]+1; i < bl[R]; i++) {
      auto p = equal_range(v[i].begin(), v[i].end(), x);
      num += p.second - p.first;
    }
  }
  return num;
}
void build() {
  int num = n/blo;
  if(n % blo) num++;
  for (int i = 1; i <= num; i++) {
    l[i] = (i - 1) * blo + 1;
    r[i] = i * blo;

  }
  r[num] = n;
  for (int i = 1; i <= n; i++) {
    bl[i] = (i - 1) / blo + 1;
  }
}
int main() {
  scanf("%d%d", &n, &m);
  build();
  for(int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    v[bl[i]].push_back(a[i]);
  }
  for (int i = 1; i <= bl[n]; i++) {
    sort(v[i].begin(), v[i].end());
  }
  int L, R, L1, R1, x;
  while(m--) {
    scanf("%d%d%d%d%d", &L, &R, &L1, &R1, &x);
    if(L > R) swap(L, R);if(L1 > R1) swap(L1, R1);
    int p1 = query(L,R,x);
    int p2 = query(L1,R1,x);
    printf("%d\n%d\n%lld\n", p1, p2, (p1*1ll*p2)%20180623);
  }
}

2.技巧二分。通过观察发现a[i]很小，把每个值为依据，把他们出现的位置存入vector，再二分找就可以，好写多了；

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
vector<int>v[N];
int main() {
  int n, m, a;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a);
    v[a].push_back(i);
  }
  int l ,r, L, R, x;
  while(m--) {
    scanf("%d%d%d%d%d", &l, &r, &L, &R, &x);
    if(l > r) swap(l ,r);if(L > R) swap(L, R);
    int p1 = (upper_bound(v[x].begin(), v[x].end(), r) - v[x].begin()) - (lower_bound(v[x].begin(), v[x].end(), l) - v[x].begin());
    int p2 = (upper_bound(v[x].begin(), v[x].end(), R) - v[x].begin()) - (lower_bound(v[x].begin(), v[x].end(), L) - v[x].begin());
    printf("%d\n%d\n%lld\n", p1, p2, (p1*1ll*p2)%20180623);
  }
}

3.主席树
还省去了离散化QAQ

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int cnt, root[N];
struct node{int l,r,sum;}T[N*20];
void update(int l, int r, int &x, int y, int pos) {
  T[++cnt] = T[y]; T[cnt].sum++;x = cnt;
  if(l == r) return ;
  int mid = (l + r) / 2;
  if(pos <= mid) update(l, mid, T[x].l, T[y].l, pos);
  else update(mid+1, r, T[x].r, T[y].r, pos);
}
int query(int l, int r, int x, int y, int w) {
  if(l == r) {
    return T[y].sum - T[x].sum;
  }
  int mid = (l + r) / 2;
  if(w <= mid) return query(l, mid, T[x].l, T[y].l, w);
  else return query(mid+1, r, T[x].r, T[y].r, w);
}
int main() {
  int n, m, Max = 0, x, L, R, l, r;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    Max = max(Max, x);
    update(1, 10000, root[i], root[i-1], x);
  }
  for (int i  = 1; i <= m; i++) {
    scanf("%d%d%d%d%d", &l, &r, &L, &R, &x);
    if(x > Max) {
      printf("0\n0\n0\n");continue;
    }
    if(l > r) swap(l ,r);if(L > R) swap(L, R);
    int p1 = query(1, 10000, root[l-1], root[r], x);
    int p2 = query(1, 10000, root[L-1], root[R], x);
    printf("%d\n%d\n%lld\n", p1, p2, (p1*1ll*p2)%20180623);
  }
}