bzoj3809 Gty的二逼妹子序列

bzoj3809 Gty的二逼妹子序列

/2018/03/01/bzoj3809/
Description

Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。

对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。

为了方便，我们规定妹子们的美丽度全都在[1,n]中。

给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=1000000)次询问“l,r,a,b”，每次输出sl…sr中，权值∈[a,b]的权值的种类数。
Input

第一行包括两个整数n,m(1<=n<=100000,1<=m<=1000000),表示数列s中的元素数和询问数。

第二行包括n个整数s1…sn(1<=si<=n)。

接下来m行,每行包括4个整数l,r,a,b(1<=l<=r<=n,1<=a<=b<=n),意义见题目描述。

保证涉及的所有数在C++的int内。

保证输入合法。
Output

对每个询问，单独输出一行，表示sl…sr中权值∈[a,b]的权值的种类数。

Sample Input

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
Sample Output

2
0
0
2
1
1
1
0
1
2
HINT

样例的部分解释：

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。

建议使用输入/输出优化。
这题还卡内存 卡时间 ..树套树就不行了
有个显然的做法 是莫队套上树状数组/线段树可以 但是会tle..
于是学习下题解 针对权值分块 每次查询的时候先把莫队的区间调整好 然后同时对权值的分块进行更新 统计答案的时候在这个权值范围内 暴力sqrt(n)统计即可

#include<cmath>
#include<cstdio>
#include<algorithm>
#define N 100010
#define M 1000010
using namespace std;
inline char gc(){static char now[1<<16],*S,*T;if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}return *S++;
}
inline int read(){int x=0,f=1;char ch=gc();while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();return x*f;
}
struct node{int l,r,id,a,b;
}qr[M];
int sum[500],n,m,nn,ans[M],b[N],c[N],a[N];
bool visit[N];
inline bool cmp(const node &aa,const node &bb){return b[aa.l]==b[bb.l]?aa.r<bb.r:b[aa.l]<b[bb.l];
}
inline void update(int x){if (visit[x]){--c[a[x]];if (!c[a[x]]) --sum[b[a[x]]];}else{++c[a[x]];if (c[a[x]]==1) ++sum[b[a[x]]];}visit[x]^=1;
}
inline int query(int l,int r){int tmp=0;if (b[l]==b[r]){for (int i=l;i<=r;++i) if (c[i])tmp+=1;return tmp;}for (int i=l;i<=b[l]*nn;++i) if (c[i]) ++tmp;for (int i=(b[r]-1)*nn+1;i<=r;++i) if (c[i]) ++tmp;for (int i=b[l]+1;i<=b[r]-1;++i) tmp+=sum[i];return tmp;
}
int main(){freopen("bzoj3809.in","r",stdin);n=read();m=read();nn=sqrt(n);for (int i=1;i<=n;++i) a[i]=read(),b[i]=(i-1)/nn+1;for (int i=1;i<=m;++i){qr[i].l=read();qr[i].r=read();qr[i].a=read();qr[i].b=read();qr[i].id=i;}sort(qr+1,qr+m+1,cmp);int cl=1,cr=0;for (int i=1;i<=m;++i){int l=qr[i].l,r=qr[i].r;while(l<cl) update(--cl);while(l>cl) update(cl++);while(r<cr) update(cr--);while(r>cr) update(++cr);ans[qr[i].id]=query(qr[i].a,qr[i].b);}for (int i=1;i<=m;++i) printf("%dn",ans[i]);return 0;
}