laekov

好厉害的数据结构题，时限太吓人了。

最初想写莫队的，但是在数据范围下屈服了。

用可持久化线段树套可持久化线段树来维护可过。虽然跑了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);

}

}