无修改的查询题，分块莫队+树状数组搞之。可这样貌似会Tle……
于是不用树状数组，改成对权值进行分块，使查询的复杂度变成O(n^0.5)，修改则是O(1)。（原树状数组的复杂度：查询O(lgn)，修改O(lgn)）
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define down(i, l, r) for(int i = l; i >= r; i--)
#define N 100005
#define M 1000005
#define ll long long
using namespace std;
struct node{int l, r, id, a, b;} q[M];
int n, m, k[N], pos[N], ans[M], now, s[N], t[1005], bl[1005], br[1005];
inline int read()
{
int x=0, f=1; char ch=getchar();
while (ch<‘0‘ || ch>‘9‘) { if (ch==‘-‘) f=-1; ch=getchar(); }
while (ch>=‘0‘ && ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); }
return x*f;
}
bool cmp(node a, node b) { if (pos[a.l] == pos[b.l]) return a.r < b.r; else return a.l < b.l; }
int Q(int x, int y)
{
int a = 0;
rep(i, pos[x]+1, pos[y]-1) a+=t[i];
if (pos[x] == pos[y])
{
rep(i, x, y) if (s[i]) a++;
}
else
{
rep(i, x, br[pos[x]]) if (s[i]) a++;
rep(i, bl[pos[y]], y) if (s[i]) a++;
}
return a;
}
void del(int x) { s[x]--; if (s[x]==0) t[pos[x]]--; }
void add(int x) { s[x]++; if (s[x]==1) t[pos[x]]++; }
int main()
{
n=read(); m=read();
rep(i, 1, n) k[i]=read();
int block = int(sqrt(n));
rep(i, 1, n) pos[i] = (i-1)/block+1;
rep(i, 1, pos[n]) bl[i] = block*(i-1)+1, br[i] = block*i; br[pos[n]] = n;
rep(i, 1, m) q[i].l=read(), q[i].r=read(), q[i].a=read(), q[i].b=read(), q[i].id=i;
sort(q+1, q+1+m, cmp);
int l = 1, r = 0;
rep(i, 1, m)
{
while (l < q[i].l) del(k[l++]);
while (q[i].r < r) del(k[r--]);
while (q[i].l < l) add(k[--l]);
while (r < q[i].r) add(k[++r]);
ans[q[i].id] = Q(q[i].a, q[i].b);
}
rep(i, 1, m) printf("%d\n", ans[i]);
return 0;
}
原文：http://www.cnblogs.com/NanoApe/p/4328440.html