bzoj3809:Gty的二逼妹子序列 _序列

【题目描述】
和又在研究Gty的妹子序列了！但他们遇到了一个难题。
对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。
为了方便，我们规定妹子们的美丽度全都在[1,n]中。
给定一个长度为n(1≤n≤)的正整数序列s(1≤si≤n)，对于m(1≤m≤)次询问“l,r,a,b”，每次输出sl...sr中，权值∈[a,b]的权值的种类数。
【bzoj3809:Gty的二逼妹子序列】【输入】
第一行包括两个整数n,m(1≤n≤,1≤m≤),表示数列s中的元素数和询问数。
第二行包括n个整数s1...sn(1≤si≤n) 。
接下来m行,每行包括4个整数l,r,a,b(1≤l≤r≤n,1≤a≤b≤n),意义见题目描述。
保证涉及的所有数在C++的int内。
保证输入合法。
【输出】
对每个询问，单独输出一行，表示sl...sr中权值∈[a,b]的权值的种类数。
【输入样例】
10 104 4 5 1 4 1 5 1 2 15 9 1 23 4 7 94 4 2 52 3 4 75 10 4 43 9 1 11 4 5 98 9 3 32 2 1 68 9 1 4
【输出样例】
2002111012
【提示】
v>样例的部分解释：
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 。
建议使用输入/输出优化。
题解：
莫队，将询问以左端点所处块的位置为第一关键字，右端点位置为第二关键字排序，保证对于左端点在同一块内的所有询问，其右端点单增
然后对权值分块，即可O（1）修改，O（sqrt（n））查询
#include#define MAXN 100005using namespace std;struct qz{int l,r,al,br,num;}q[1000005];int n,m,sz;int arr[MAXN],idx[MAXN],blo[320],cnt[MAXN],ans[1000005];inline int read(){int X=0,w=0; char ch=0;while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X;}inline void write(int x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');}inline bool cmp(qz a1,qz b1){if(idx[a1.l]q[i].r){del(arr[R]);R--;}while(L>q[i].l){L--;add(arr[L]);}while(R
View Code