好厉害的数据结构题，时限太吓人了。
最初想写莫队的，但是在数据范围下屈服了。
用可持久化线段树套可持久化线段树来维护可过。虽然跑了97s。本机跑得快得多，虽然有两个点被卡到了18s。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
struct seg {
int v, ls, rs;
};
#define readInt(_s_) {\
_s_ = 0;\
int _d_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
const int maxn = 100009;
const int maxl = 20;
const int maxnd = maxn * maxl * maxl;
seg s[maxnd];
int n, m, t, a[maxn], d[maxn], c[maxn], *r[maxn], sp, rt[maxn];
inline bool cmpP(int* a, int* b) {
return *a < *b;
}
#define vof(p) ((p)?(s[p].v):0)
#define lson(p) ((p)?(s[p].ls):0)
#define rson(p) ((p)?(s[p].rs):0)
int sgtIns(int q, int p0) {
int rt = ++ sp, p = rt;
int l = 0, r = n;
while (l < r) {
s[p]. v = vof(q) + 1;
int mid = (l + r) >> 1;
if (p0 <= mid) {
s[p]. rs = rson(q);
q = lson(q);
s[p]. ls = ++ sp;
p = s[p]. ls;
r = mid;
}
else {
s[p]. ls = lson(q);
q = rson(q);
s[p]. rs = ++ sp;
p = s[p]. rs;
l = mid + 1;
}
}
s[p]. v = vof(q) + 1;
return rt;
}
int psgtIns(int q, int p0, int v0) {
int rt = ++ sp, p = rt;
int l = 1, r = t;
while (l < r) {
s[p]. v = sgtIns(vof(q), v0);
int mid = (l + r) >> 1;
if (p0 <= mid) {
s[p]. rs = rson(q);
q = lson(q);
s[p]. ls = ++ sp;
p = s[p]. ls;
r = mid;
}
else {
s[p]. ls = lson(q);
q = rson(q);
s[p]. rs = ++ sp;
p = s[p]. rs;
l = mid + 1;
}
}
s[p]. v = sgtIns(vof(q), v0);
return rt;
}
void dispNums() {
for (int i = 1; i <= n; ++ i)
r[i - 1] = a + i;
sort(r, r + n, cmpP);
t = 0;
for (int i = 0, l = *r[0] - 1; i < n; ++ i)
if (*r[i] == l)
*r[i] = t;
else {
d[++ t] = *r[i];
l = *r[i];
*r[i] = t;
}
d[++ t] = *r[n - 1] + 1;
memset(c, 0, sizeof(c));
rt[0] = 0;
sp = 0;
for (int i = 1; i <= n; ++ i) {
rt[i] = psgtIns(rt[i - 1], a[i], c[a[i]]);
c[a[i]] = i;
}
}
int sgtQry(int p, int p0) {
int ans = 0;
int l = 0, r = n;
while (l < r && p) {
int mid = (l + r) >> 1;
if (p0 <= mid) {
r = mid;
p = lson(p);
}
else {
l = mid + 1;
ans += vof(lson(p));
p = rson(p);
}
}
if (p)
ans += vof(p);
return ans;
}
void psgtQry(int p, int p0, int v0, int& x, int& y) {
x = 0;
y = 0;
if (p0 == 0)
return;
int l = 1, r = t;
while (l < r && p) {
int mid = (l + r) >> 1;
if (p0 <= mid) {
r = mid;
p = lson(p);
}
else {
x += vof(vof(lson(p)));
y += sgtQry(vof(lson(p)), v0);
l = mid + 1;
p = rson(p);
}
}
if (p) {
x += vof(vof(p));
y += sgtQry(vof(p), v0);
}
}
void query(int l, int r, int a, int b) {
int tt = 0, ct = 0, x, y;
psgtQry(rt[r], b, l - 1, x, y);
tt += x;
ct += y;
psgtQry(rt[r], a - 1, l - 1, x, y);
tt -= x;
ct -= y;
psgtQry(rt[l - 1], b, l - 1, x, y);
tt -= x;
ct -= y;
psgtQry(rt[l - 1], a - 1, l - 1, x, y);
tt += x;
ct += y;
printf("%d %d\n", tt, ct);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
readInt(n);
readInt(m);
for (int i = 1; i <= n; ++ i)
readInt(a[i]);
dispNums();
while (m --) {
int l, r, a, b;
readInt(l);
readInt(r);
readInt(a);
readInt(b);
a = lower_bound(d, d + t, a) - d;
b = upper_bound(d, d + t, b) - d - 1;
if (a > b)
puts("0 0");
else
query(l, r, a, b);
}
}