题目
题解
考试的时候想到了莫队套数据结构维护，但是没想到分块……
首先可以把题目简化成二维矩阵的查询，如果去掉查询中$y$坐标的限制，即查询一段区间内不同数的个数，这个显然是可以用莫队搞的；而对于加上$y$的限制，考虑能否用数据结构维护莫队每一步移动对于$y$值域的贡献以及查询
如果用树状数组等数据结构维护，可以做到$O(logM)$的修改和查询，但是这样复杂度就为$O((n\sqrt n + m)logM)$，发现修改操作的复杂度过高，考虑分块，对于$y$值域分块，每次莫队移动相当于对于值域中的某个点$+1$或$-1$，查询的时候直接查询区间内不为$0$的点个数，这样总复杂度就变为$O(n\sqrt n+m\sqrt M)$，其中$M$为最大值域
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX = 1e5 + 5, N = 320;
int n, m, K, M;
int f[MAX], pos[MAX], pox[MAX], val[MAX], Ans[MAX];
int pL[N], pR[N], num[N];
struct p{
int l, r, ly, ry, id;
bool operator< (const p &a)
const {
if(pos[l] != pos[a.l])
return pos[l] < pos[a.l];
return r < a.r;
}
}q[MAX];
int read()
{
int x = 0;
char ch = getchar();
for(; !isdigit(ch); ch = getchar());
for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
return x;
}
void Mem()
{
memset(num, 0, sizeof(num));
memset(val, 0, sizeof(val));
memset(pL, 0, sizeof(pL));
memset(pR, 0, sizeof(pR));
}
void Upt(int x, int v)
{
int px = pox[x];
val[x] += v;
if(!val[x] && v == -1)
-- num[px];
else if(val[x] == 1 && v == 1)
++ num[px];
}
int Ask(int l, int r)
{
int pl = pox[l], pr = pox[r];
int ans = 0;
for(int i = pl + 1; i <= pr - 1; ++ i)
ans += num[i];
for(int i = l; i <= min(pR[pl], r); ++ i)
ans += val[i] ? 1 : 0;
if(pl != pr)
for(int i = pL[pr]; i <= r; ++ i)
ans += val[i] ? 1 : 0;
return ans;
}
int main()
{
int T = read();
while(T --)
{
Mem();
n = read(), m = read(), K = sqrt(n);
for(int i = 1; i <= n; ++ i)
M = max(M, f[i] = read() + 1), pos[i] = (i - 1) / K + 1;
for(int i = 1; i <= m; ++ i)
{
q[i].l = read(), q[i].ly = read() + 1;
q[i].r = read(), q[i].ry = read() + 1;
q[i].id = i;
M = max(M, q[i].ry);
}
sort(q + 1, q + 1 + m);
int Km = sqrt(M);
for(int i = 1; i <= M; ++ i)
{
pox[i] = (i - 1) / Km + 1;
if(!pL[pox[i]])
pL[pox[i]] = i;
pR[pox[i]] = i;
}
for(int i = 1, l = 1, r = 0; i <= m; ++ i)
{
while(l < q[i].l)
Upt(f[l ++], -1);
while(l > q[i].l)
Upt(f[-- l], 1);
while(r < q[i].r)
Upt(f[++ r], 1);
while(r > q[i].r)
Upt(f[r --], -1);
Ans[q[i].id] = Ask(q[i].ly, q[i].ry);
}
for(int i = 1; i <= m; ++ i)
printf("%d\n", Ans[i]);
}
return 0;
}
