Steven_MengのBlog

洛古

GDOI

首先,看见$“权值\in [a,b]的权值的种类数。”$这样的话就要想到莫队。

我们有一个比较显然的树状数组做法,每次加进一个数,如果没有出现,那么加进树状数组,删除也是类似,最后前缀和相减统计一下即可。

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
79
#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 1000005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int a[MAXN],cnt[MAXN];
namespace BIT{
int c[MAXN];
#define lowbit(x) (x&-x)
inline void upd(int pos,int val){
for (register int i=pos;i<MAXN;i+=lowbit(i)){
c[i]+=val;
}
}
inline int qry(int pos){
int ans=0;
for (register int i=pos;i>0;i-=lowbit(i)){
ans+=c[i];
}
return ans;
}
}
using namespace BIT;

int pos[MAXN];
struct Query{
int l,r,a,b,id;
}q[MAXM];
inline bool operator < (const Query &a,const Query &b){
return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));
}
int Ans[MAXM];
int main(){
int n=read(),m=read();
int Size=sqrt(n);
for (register int i=1;i<=n;++i){
a[i]=read();
pos[i]=(i-1)/Size+1;
}
for (register int i=1;i<=m;++i){
q[i].l=read(),q[i].r=read(),q[i].a=read(),q[i].b=read(),q[i].id=i;
}
sort(q+1,q+1+m);
int l=1,r=0;
for (register int i=1;i<=m;++i){
while (l<q[i].l){
if (--cnt[a[l]]==0) upd(a[l],-1);
++l;
}
while (l>q[i].l){
--l;
if (++cnt[a[l]]==1) upd(a[l],1);
}
while (r<q[i].r){
++r;
if (++cnt[a[r]]==1) upd(a[r],1);
}
while (r>q[i].r){
if (--cnt[a[r]]==0) upd(a[r],-1);
--r;
}
Ans[q[i].id]=qry(q[i].b)-qry(q[i].a-1);
}
for (register int i=1;i<=m;++i){
printf("%d\n",Ans[i]);
}
}

这样的做法在洛古上面能过,但是$\rm GDOI$上面过不了,为什么呢?

时间复杂度太高了,为$O(n \sqrt n\log n)$

考虑我们莫队算法的特性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
while (l<q[i].l){
if (--cnt[a[l]]==0) upd(a[l],-1);
++l;
}
while (l>q[i].l){
--l;
if (++cnt[a[l]]==1) upd(a[l],1);
}
while (r<q[i].r){
++r;
if (++cnt[a[r]]==1) upd(a[r],1);
}
while (r>q[i].r){
if (--cnt[a[r]]==0) upd(a[r],-1);
--r;
}
Ans[q[i].id]=qry(q[i].b)-qry(q[i].a-1);

直观感受一下,一个循环里面,修改操作改了这么多次,但是查询只有一次。

所以我们适当降低修改操作的时间复杂度,提高查询操作的时间复杂度,可能可以达到提高程序效率的功能。

所以,我们使用分块,修改复杂度$O(1)$,查询复杂度$O(\sqrt n)$,就可以提高程序效率。

再仔细考虑一下,莫队整个算法也和分块密切相关,它的时间复杂度为$O(n \sqrt n)$,说明一次循环里面,$l,r$指针移动的次数是$O(\sqrt n)$级别,所以使用分块,前面修改复杂度为$O(1 \times \sqrt n)$,后面修改复杂度为$O(\sqrt n \times 1)$,合起来算一下,时间复杂度为$O(n \sqrt n)$,少了一个$\log $,是正确的。


总结:莫队和分块取长补短,可以达到降低时间复杂度的效果。

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
#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 1000005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int a[MAXN],Size;
static int pos[MAXN],cnt[MAXN],val[MAXN];//块内所有数之和
namespace Divide_Into_Blocks{
inline int Calc(int l,int r){
int ans=0;
for (register int i=l;i<=r;++i) ans+=cnt[i]>0;
return ans;
}
inline int GetAns(int a,int b){
int L=pos[a],R=pos[b];
if (L==R) return Calc(a,b);
int ans=0;
for (register int i=L+1;i<=R-1;++i) ans+=val[i];
return ans+Calc(a,L*Size)+Calc((R-1)*Size+1,b);
}
}
using namespace Divide_Into_Blocks;
struct Query{
int l,r,a,b,id;
}q[MAXM];
inline bool operator < (const Query &a,const Query &b){
return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));
}
inline void Add(int x){
if (++cnt[x]==1) ++val[pos[x]];
}
inline void Del(int x){
if (--cnt[x]==0) --val[pos[x]];
}
int Ans[MAXM];
int main(){
int n=read(),m=read();
Size=sqrt(n);
for (register int i=1;i<=n;++i){
a[i]=read();
pos[i]=(i-1)/Size+1;
}
for (register int i=1;i<=m;++i){
q[i].l=read(),q[i].r=read(),q[i].a=read(),q[i].b=read(),q[i].id=i;
}
sort(q+1,q+1+m);
int l=1,r=0;
for (register int i=1;i<=m;++i){
while (l<q[i].l) Del(a[l++]);
while (l>q[i].l) Add(a[--l]);
while (r<q[i].r) Add(a[++r]);
while (r>q[i].r) Del(a[r--]);
Ans[q[i].id]=GetAns(q[i].a,q[i].b);
}
for (register int i=1;i<=m;++i){
printf("%d\n",Ans[i]);
}
}

 评论