「Gty」Gty的二逼妹子序列

发表于 | 分类于 | | 浏览量： 次

莫队？分块？两个一起来。

传送门

洛谷P4867

题解

看到这种题目，很显然，是一个莫队。

但是这道题的每一个询问有两个限制区间。

所以，还需要再来一个分块来统计答案。

然后就好了，注意常数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005,maxm=1000005;
int n,m,S,A[maxn],Area[maxn],ans[maxm],cnt[400],hsh[maxn];
struct FastIO
{
	static const int S=131072;
	char buf[S],*L,*R;int stk[20],Top;
	~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}
	inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}
	FastIO& operator >> (int& ret)
	{
		ret=0;int f=1;char ch=nc();
		while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}
		while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}
		return *this;
	}
	FastIO& operator << (int x)
	{
		if(x<0){pc('-');x=-x;}
		do{stk[++stk[0]]=x%10;x/=10;}while(x);
		while(stk[0]) pc('0'+stk[stk[0]--]);
		return *this;
	}
	FastIO& operator << (char ch){pc(ch);return *this;}
}fin,fout;
struct Query
{
	int L,R,a,b,id;
	bool operator < (const Query& b)const{return Area[L]<Area[b.L]||(Area[L]==Area[b.L]&&((Area[L]&1)?R<b.R:R>b.R));}
}Q[maxm];
inline void inc(int x){if(!hsh[x]++) cnt[Area[x]]++;}
inline void dec(int x){if(!--hsh[x]) cnt[Area[x]]--;}
inline int Calc(int L,int R)
{
	int ret=0;
	if(Area[R]-Area[L]<=1)
	{
		for(int i=L;i<=R;i++) if(hsh[i]) ret++;
		return ret;
	}
	for(int i=L;Area[i]==Area[L];i++) if(hsh[i]) ret++;
	for(int i=Area[L]+1;i<Area[R];i++) ret+=cnt[i];
	for(int i=R;Area[i]==Area[R];i--) if(hsh[i]) ret++;
	return ret;
}
inline void Solve()
{
	int L=1,R=0;
	for(int i=1;i<=m;i++)
	{
		while(R<Q[i].R) inc(A[++R]);
		while(L>Q[i].L) inc(A[--L]);
		while(R>Q[i].R) dec(A[R--]);
		while(L<Q[i].L) dec(A[L++]);
		ans[Q[i].id]=Calc(Q[i].a,Q[i].b);
	}
}
int main()
{
	fin>>n>>m;S=sqrt(n)+1e-10;
	for(int i=1;i<=n;i++) fin>>A[i];
	for(int i=1;i<=n;i++) Area[i]=(i-1)/S+1;
	for(int i=1;i<=m;i++)
	{
		fin>>Q[i].L>>Q[i].R>>Q[i].a>>Q[i].b;
		Q[i].id=i;
	}
	sort(Q+1,Q+1+m);
	Solve();
	for(int i=1;i<=m;i++)
		fout<<ans[i]<<'\n';
	return 0;
}