题意
给定一个序列，每次询问求：
在区间 \([l, r]\) 中，大小在 \([a, b]\) 中数的个数与种类数。
Sol
对于第一问直接离线跑树状数组二维偏序。
第二问考虑莫队，发现只需要维护莫队那个表示种类的数组的区间和就行了。
要求 \(O(1)\) 修改的话，写个值域分块？
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <tuple>
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
const int N = 1e5 + 5, M = 605;
array <int, N> s;
namespace Bit {
array <int, N> edge;
int lowbit(int x) {
return x & -x;
}
void modify(int x, int y, int n) {
if (!x) return;
while (x <= n) {
edge[x] += y;
x += lowbit(x);
}
return;
}
int query(int x) {
int ans = 0;
while (x) {
ans += edge[x];
x -= lowbit(x);
}
return ans;
}
struct Node {
int l, r, id, k;
bool operator <(const Node &t) const {
return l < t.l;
}
};
}
namespace Cpt {
int bsi = 332;
struct Node {
int l, r, x, y, id;
bool operator < (const Node &t) const {
if (l / bsi != t.l / bsi) return l < t.l;
return (l / bsi) & 1 ? r < t.r : r > t.r;
}
};
namespace Blk {
array <int, N> cur;
array <int, M> bk;
int calc(int x) {
return (x - 1) / bsi + 1;
}
int query(int x, int y) {
int ans = 0;
if (calc(x) == calc(y)) {
for (int i = x; i <= y; i++)
ans += (cur[i] && 1);
return ans;
}
for (int i = x; i <= calc(x) * bsi; i++)
ans += (cur[i] && 1);
for (int i = calc(x) + 1; i < calc(y); i++)
ans += bk[i];
for (int i = (calc(y) - 1) * bsi + 1; i <= y; i++)
ans += (cur[i] && 1);
return ans;
}
}
void add(int x) {
Blk::cur[s[x]]++;
if (Blk::cur[s[x]] == 1)
Blk::bk[Blk::calc(s[x])]++;
}
void del(int x) {
Blk::cur[s[x]]--;
if (Blk::cur[s[x]] == 0)
Blk::bk[Blk::calc(s[x])]--;
}
}
array <Bit::Node, N * 4> isl;
array <Cpt::Node, N> qrl;
array <int, N> ans1, ans2;
using Cpt::add; using Cpt::del;
int main() {
int n = read(), m = read();
for (int i = 1; i <= n; i++)
s[i] = read();
int cnt = 0;
for (int i = 1; i <= m; i++) {
int l = read(), r = read(), x = read(), y = read();
qrl[i].l = l, qrl[i].r = r, qrl[i].x = x, qrl[i].y = y;
qrl[i].id = i;
cnt++; isl[cnt].l = r, isl[cnt].r = y, isl[cnt].id = i, isl[cnt].k = 1;
cnt++; isl[cnt].l = l - 1, isl[cnt].r = y, isl[cnt].id = i, isl[cnt].k = -1;
cnt++; isl[cnt].l = r, isl[cnt].r = x - 1, isl[cnt].id = i, isl[cnt].k = -1;
cnt++; isl[cnt].l = l - 1, isl[cnt].r = x - 1, isl[cnt].id = i, isl[cnt].k = 1;
}
sort(isl.begin() + 1, isl.begin() + 1 + cnt);
int tp = 0;
for (int i = 0; i <= n; i++) {
Bit::modify(s[i], 1, 100000);
while (isl[tp + 1].l == i && tp + 1 <= cnt) {
tp++;
ans1[isl[tp].id] += isl[tp].k * Bit::query(isl[tp].r);
}
}
/* for (int i = 1; i <= m; i++) */
/* write(ans1[i]), putchar(32); */
/* puts(""); */
sort(qrl.begin() + 1, qrl.begin() + 1 + m);
int l = 1, r = 0;
for (int i = 1; i <= m; i++) {
int x = qrl[i].l, y = qrl[i].r;
while (l > x) l--, add(l);
while (r < y) r++, add(r);
while (l < x) del(l), l++;
while (r > y) del(r), r--;
ans2[qrl[i].id] = Cpt::Blk::query(qrl[i].x, qrl[i].y);
}
for (int i = 1; i <= m; i++) {
write(ans1[i]), putchar(32);
write(ans2[i]), puts("");
}
return 0;
}