好一道卡常数。不仅卡时间，还卡空间。堪称丧心病狂的极致。
首先因为空间小所以得用莫队。然后不知为何树状数组没有直接分块跑得快。
没有救啦。
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <algorithm>
usingnamespacestd;
structqry {
intl, r, a, b, n;
};
int_d_;
#define readInt(_x_) { \
int& _s_ = _x_; \
while(!isdigit(_d_ = getchar())); \
_s_ = 0; \
while((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \
}
constintmaxn = 100009;
constintmaxm = 1000009;
intn, m, bsz, a[maxn], c[maxn], w[maxn], b[maxn], ans[maxm];
qry q[maxm];
inlineboolcmpQry(constqry& a, constqry& b) {
returnw[a. l] < w[b. l] || (w[a. l] == w[b. l] && a. r < b. r);
}
inlinevoidchg(intp, intv) {
b[w[p]] += v;
}
intqry(intl, intr) {
ints = 0;
if(w[l] == w[r]) {
while(l <= r) {
if(c[l])
++ s;
++ l;
}
}
else{
for(inti = l; w[i] == w[l]; ++ i)
if(c[i])
++ s;
for(inti = w[l] + 1; i < w[r]; ++ i)
s += b[i];
for(inti = r; w[i] == w[r]; -- i)
if(c[i])
++ s;
}
returns;
}
intmain() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
readInt(n);
readInt(m);
bsz = (int)sqrt(n / 4) + 1;
for(inti = 1; i <= n; ++ i) {
readInt(a[i]);
w[i] = (i - 1) / bsz + 1;
}
for(inti = 0; i < m; ++ i) {
readInt(q[i]. l);
readInt(q[i]. r);
readInt(q[i]. a);
readInt(q[i]. b);
q[i]. n = i;
}
sort(q, q + m, cmpQry);
memset(b, 0, sizeof(b));
chg(a[1], 1);
c[a[1]] = 1;
for(inti = 0, l = 1, r = 1; i < m; ++ i) {
while(l > q[i]. l) {
-- l;
if(!c[a[l]])
chg(a[l], 1);
++ c[a[l]];
}
while(r < q[i]. r) {
++ r;
if(!c[a[r]])
chg(a[r], 1);
++ c[a[r]];
}
while(l < q[i]. l) {
-- c[a[l]];
if(!c[a[l]])
chg(a[l], -1);
++ l;
}
while(r > q[i]. r) {
-- c[a[r]];
if(!c[a[r]])
chg(a[r], -1);
-- r;
}
ans[q[i]. n] = qry(q[i]. a, q[i]. b);
}
for(inti = 0; i < m; ++ i)
printf("%d\n", ans[i]);
}