P4867 Gty的二逼妹子序列
题目描述
Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题
对于一段妹子们，他们想让你帮忙求出这之内美丽度 (in [a,b])的妹子的美丽度的种类数。
为了方便，我们规定妹子们的美丽度全都在 ([1,n]) 中。
给定一个长度为(n(1 le n le 100000)) 的正整数序列(s(1 le si le n))，对于 (m(1 le m le 1000000))次询问l,r,a,b，每次输(s_l cdots s_r)中，权值 (in [a,b]) 的权值的种类数。
输入格式
第一行包括两个整数 (n,m(1 le n le 100000,1 le m le 1000000))，表示数列 (s) 中的元素数和询问数。
第二行包括 (n) 个整数 (s1…sn(1 le si le n))。
接下来 (m) 行,每行包括 (4) 个整数 (l,r,a,b(1 le l le r le n,1 le a le b le n)),意义见题目描述。
保证涉及的所有数在C++的int内。保证输入合法。
输出格式
对每个询问，单独输出一行，表示 (s_l cdots s_r) 权值 (in [a,b]) 的权值的种类数。
输入输出样例
输入 #1
10 10
4 4 5 1 4 1 5 1 2 1
5 9 1 2
3 4 7 9
4 4 2 5
2 3 4 7
5 10 4 4
3 9 1 1
1 4 5 9
8 9 3 3
2 2 1 6
8 9 1 4
输出 #1
2
0
0
2
1
1
1
0
1
2
说明/提示
【样例的部分解释】
5 9 1 2 子序列为4 1 5 1 2
在[1,2]里的权值有1,1,2，有2种，因此答案为2。
3 4 7 9
子序列为5 1 在[7,9]里的权值有5，有1种，因此答案为1。
4 4 2 5
子序列为1
没有权值在[2,5]中的，因此答案为0。
2 3 4 7
子序列为4 5
权值在[4,7]中的有4,5，因此答案为2。
建议使用输入/输出优化。
这题空间好鬼畜啊。没见过这么小气的出题人
首先这道题 询问可以离线，并且询问是关于颜色种类的，你想到了什么？
莫队 OR 分块？。
拿莫队写的话，统计答案比较麻烦，但处理询问的话比较方便。
但你拿分块写的话，虽然答案比较好处理，但却处理不了区间询问的问题。
那怎么办？ 我们把这两个结合起来，搞个莫队套分块（具体来说是莫队套值域分块）。
那怎么操作呢？
我们在移动莫队的指针的时候，顺便维护一下每个权值出现的次数，并且维护一下每个权值所在块的颜色个数。
等到莫队指针与询问区间完全重合，就可以拿分块来统计答案。
实现的细节看代码吧；
注意块的 (L) 和 (R) 这两个数组可以开小点，要卡着开。
答案数组不要开的太小了，（开小了的话会 TLE 又 MLE）
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1e5+10;
int n,m,block;
int c[N],cnt[N],pos[N],sum[N],ans[1000010],L[1010],R[1010];
struct node
{
int l,r,a,b,id;
}q[1000010];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}
return s * w;
}
bool comp(node a,node b)
{
if(pos[a.l] == pos[b.l]) return a.r < b.r;
return pos[a.l] < pos[b.l];
}
void add(int x)
{
cnt[c[x]]++;//维护每个权值出现的次数
if(cnt[c[x]] == 1) sum[pos[c[x]]]++;//第一次出现说明出现了一个新的种类
}
void del(int x)
{
if(cnt[c[x]] == 1) sum[pos[c[x]]]--;//出现次数变为0，说明出现的种类数减1
cnt[c[x]]--;
}
int query(int x,int y)//分块询问区间和
{
int res = 0;
if(pos[x] == pos[y])
{
for(int i = x; i <= y; i++) if(cnt[i] >= 1) res++;
return res;
}
else
{
// cout<<"snkhg"<<endl;
int xx = pos[x], yy = pos[y];
for(int i = x; i <= R[xx]; i++) if(cnt[i] >= 1 ) res++;
for(int i = xx+1; i <= yy-1; i++) res += sum[i];
for(int i = L[yy]; i <= y; i++) if(cnt[i] >= 1) res++;
}
return res;
}
int main()
{
n = read(); m = read(); block = (int) sqrt(n);
for(int i = 1; i <= n; i++)
{
c[i] = read();
pos[i] = (i-1) / block + 1;
L[pos[i]] = 2333333;
}
for(int i = 1; i <= m; i++)
{
q[i].l = read(); q[i].r = read();
q[i].a = read(); q[i].b = read();
q[i].id = i;
}
for(int i = 1; i <= n; i++)
{
L[pos[i]] = min(L[pos[i]],i);
R[pos[i]] = max(R[pos[i]],i);
}
sort(q+1,q+m+1,comp);
int l = 1,r = 0;
for(int i = 1; i <= m; i++)
{
while(l < q[i].l) del(l++);//莫队维护询问区间
while(l > q[i].l) add(--l);
while(r < q[i].r) add(++r);
while(r > q[i].r) del(r--);
ans[q[i].id] = query(q[i].a,q[i].b);//分块统计答案
}
for(int i = 1; i <= m; i++) printf("%d
",ans[i]);
// fclose(stdin); fclose(stdout);
return 0;
}
最近越来越喜欢刷数据结构的题了呢（大雾）