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
题意概述：给出一个序列，每次询问问序列区间[L,R]中的元素里权值在[a,b]中的不同元素种类数。
总的一句话：所有可以用O(1)时间（总之就是代价很小）把区间[l,r]的询问转化到区间[l+1,r],[l,r-1]的询问的可离线问题都可以用莫队干掉！
观察这个问题，可以发现如果你维护一个维护元素的数据结构，那么显然可以在你移动区间左右指针的时候做到快速修改答案，这正符合了莫队算法的用途。
使用分块来做这个维护元素的数据结构，因为它支持O(1)修改啊！每一次查询的时候时间复杂度和移动指针的时间代价是几乎相同的。
时间复杂度O((2N+M)*sqrt(N))
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
5 #include<algorithm>
6 #include<cmath>
7 #include<queue>
8 #include<
set>
9 #include<map>
10 #include<vector>
11 #include<cctype>
12 using namespace std;
13 const int MAXN=
100005;
14 const int MAXQ=
1000005;
15 const int size=
205;
16
17 int N,M,S[MAXN],ans[MAXQ];
18 struct que{
19 int id,l,r,a,b;
20 friend
bool operator <
(que a,que b){
21 return a.l/size<b.l/size||a.l/size==b.l/size&&a.r<
b.r;
22 }
23 }q[MAXQ];
24 struct BLOCK{
25 static const int maxn=
100005;
26 static const int SIZE=
500;
27 static const int maxm=
205;
28 int c[maxn],kind[maxm],lef[maxm],rig[maxm],cnt,belong[maxn];
29 BLOCK(){ cnt=
1; }
30 void build(
int n){
31 int p=
1;
32 while(p+SIZE<n+
1){
33 lef[cnt]=p,rig[cnt]=p+SIZE,p+=SIZE,cnt++
;
34 for(
int i=lef[cnt-
1];i<rig[cnt-
1];i++) belong[i]=cnt-
1;
35 }
36 lef[cnt]=p,rig[cnt]=n+
1;
37 for(
int i=lef[cnt];i<rig[cnt];i++) belong[i]=
cnt;
38 }
39 void update(
int p,
int v){
40 if(c[p]&&c[p]+v==
0) kind[belong[p]]--
;
41 if(!c[p]&&c[p]+v==
1) kind[belong[p]]++
;
42 c[p]+=
v;
43 }
44 int query(
int L,
int R){
45 int re=
0,p=
L;
46 if(belong[L]==
belong[R]){
47 for(
int i=L;i<=R;i++)
if(c[i]) re++
;
48 return re;
49 }
50 for(
int i=L;i<rig[belong[L]];i++)
if(c[i]) re++
;
51 for(
int i=lef[belong[R]];i<=R;i++)
if(c[i]) re++
;
52 for(
int i=belong[L]+
1;i<belong[R];i++) re+=
kind[i];
53 return re;
54 }
55 }block;
56
57 void _scanf(
int &
x)
58 {
59 x=
0;
60 char c=
getchar();
61 while(c<
'0'||c>
'9') c=
getchar();
62 while(c>=
'0'&&c<=
'9') x=x*
10+c-
'0',c=
getchar();
63 }
64 int out_cnt,
out[
15];
65 void _printf(
int x)
66 {
67 out[++out_cnt]=x%
10,x/=
10;
68 while(x)
out[++out_cnt]=x%
10,x/=
10;
69 while(out_cnt) putchar(
'0'+
out[out_cnt--
]);
70 putchar(
'\n');
71 }
72 void data_in()
73 {
74 _scanf(N);_scanf(M);
75 for(
int i=
1;i<=N;i++
) _scanf(S[i]);
76 for(
int i=
1;i<=M;i++
){
77 _scanf(q[i].l);_scanf(q[i].r);
78 _scanf(q[i].a);_scanf(q[i].b);
79 q[i].id=
i;
80 }
81 }
82 void movep(
int &i,
int j,
int t)
83 {
84 while(i<
j){
85 if(!t) block.update(S[i++],-
1);
86 else block.update(S[++i],
1);
87 }
88 while(i>
j){
89 if(!t) block.update(S[--i],
1);
90 else block.update(S[i--],-
1);
91 }
92 }
93 void work()
94 {
95 sort(q+
1,q+M+
1);
96 block.build(N);
97 int l=
1,r=
1;
98 block.update(S[
1],
1);
99 for(
int i=
1;i<=M;i++
){
100 movep(r,q[i].r,
1);
101 movep(l,q[i].l,
0);
102 ans[q[i].id]=
block.query(q[i].a,q[i].b);
103 }
104 for(
int i=
1;i<=M;i++
) _printf(ans[i]);
105 }
106 int main()
107 {
108 data_in();
109 work();
110 return 0;
111 }
转载于:https://www.cnblogs.com/KKKorange/p/8596952.html
相关资源：n个整数的序列：a1，a2，...，an，求最大子段和
