bzoj3809:Gty的二逼妹子序列
【题目描述】
对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。
为了方便，我们规定妹子们的美丽度全都在[1,n]中。
给定一个长度为n(1≤n≤)的正整数序列s(1≤si≤n)，对于m(1≤m≤)次询问“l,r,a,b”，每次输出sl...sr中，权值∈[a,b]的权值的种类数。
【输入】
第一行包括两个整数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 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
【输出样例】
2 0 0 2 1 1 1 0 1 2
【提示】
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 100005 using 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]<idx[b1.l])return true;if(idx[a1.l]==idx[b1.l])if(a1.r<b1.r)return true;return false; } inline int query(int ll,int rr) {int ret=0;if(idx[ll]==idx[rr]){for(register int i=ll;i<=rr;i++)if(cnt[i]!=0)ret++;return ret; }if(ll==(idx[ll]-1)*sz+1&&rr==idx[rr]*sz){for(register int i=idx[ll];i<=idx[rr];i++)ret+=blo[i];return ret; } int lx=idx[ll]*sz,rx=(idx[rr]-1)*sz+1;for(register int i=ll;i<=lx;i++)if(cnt[i]!=0)ret++;for(register int i=rx;i<=rr;i++)if(cnt[i]!=0)ret++;lx=idx[ll]+1;rx=idx[rr]-1; for(register int i=lx;i<=rx;i++)ret+=blo[i];return ret; } inline void del(int p) {cnt[p]--;if(cnt[p]==0)blo[idx[p]]--; } inline void add(int p) {cnt[p]++;if(cnt[p]==1)blo[idx[p]]++; } int main() {n=read();m=read();sz=(int)sqrt(n);for(register int i=1;i<=n;i++)idx[i]=(i-1)/sz+1;for(register int i=1;i<=n;i++)arr[i]=read();for(register int i=1;i<=m;i++){q[i].num=i;q[i].l=read();q[i].r=read();q[i].al=read();q[i].br=read();}sort(q+1,q+1+m,cmp);int L=1,R=0;for(register int i=1;i<=m;i++){while(L<q[i].l){del(arr[L]);L++;}while(R>q[i].r){del(arr[R]);R--;} while(L>q[i].l){L--;add(arr[L]);}while(R<q[i].r){R++;add(arr[R]);} ans[q[i].num]=query(q[i].al,q[i].br); }for(register int i=1;i<=m;i++){write(ans[i]);printf("\n");}return 0; }
View Code
