Reku
0%

莫队算法

Posted on Edited on In Views: Valine:

唉，拖延症好严重啊。 其实分块的写法还是很简单的，高中不太懂，看了一堆什么最小曼哈顿生成树，感觉被吓尿，现在感觉也不是太难。 就是说如果区间查询可以离线，并且相邻的区间可以通过较快的时间复杂度进行转移，这种题目就是典型的莫队题啦。

先来一道例题 小Z的袜子

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
#include<bits/stdc++.h>
using namespace std;
#define N 50010
typedef long long LL;
int n,m,pos[N],c[N];
LL s[N],ans;
LL sq(LL x)
{
	return x*x;
}
struct query{
	int l,r,id;
	LL a,b;
} q[N];
bool cmp(query x,query y)
{
	if(pos[x.l]==pos[y.l]) return x.r<y.r;
	return x.l<y.l;
}
bool cmp2(query x,query y)
{
	return x.id<y.id;
}
void update(int p,int add)
{
	ans-=sq(s[c[p]]);
	s[c[p]]+=add;
	ans+=sq(s[c[p]]);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
	}
	int block=int(sqrt(n));
	for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	for(int i=1,l=1,r=0;i<=m;i++)
	{
		for(;r<q[i].r;r++)
			update(r+1,1);
		for(;r>q[i].r;r--)
			update(r,-1);
		for(;l<q[i].l;l++)
			update(l,-1);
		for(;l>q[i].l;l--)
			update(l-1,1);
		if(q[i].l==q[i].r)
		{
			q[i].a=0; q[i].b=1;
			continue;
		}
		q[i].a=ans-(q[i].r-q[i].l+1);
		q[i].b=(LL)(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
		int k=__gcd(q[i].a,q[i].b);
		q[i].a/=k; q[i].b/=k;
	}
	sort(q+1,q+m+1,cmp2);
	for(int i=1;i<=m;i++)
		printf("%lld/%lld\n",q[i].a,q[i].b);
	return 0;
}

http://codeforces.com/contest/86/problem/D 这个东西倒是很裸的莫队，但是这个常数确实卡的很厉害。。。

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
#include<bits/stdc++.h>
using namespace std;
#define N 2000010
typedef long long LL;
int n,m,pos[N];
int c[N];
int s[N];
LL ans;
LL u[N];
struct query{
	int l,r,id;
} q[N];
bool cmp(query x,query y)
{
	if(pos[x.l]==pos[y.l]) return x.r<y.r;
	return pos[x.l]<pos[y.l];
}
void add(LL x)  
{  
    s[x]++;  
    ans += x*(s[x]*s[x] - (s[x]-1)*(s[x]-1));  
}  
  
void del(LL x)  
{  
    s[x]--;  
    ans -= x*((s[x]+1)*(s[x]+1) - (s[x])*(s[x]));  
} 
int main()
{
	scanf("%d%d",&n,&m);
	double block=sqrt(n*1.0);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
		pos[i]=i/block;
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	for(int i=1,l=1,r=0;i<=m;i++)
	{
		while(r < q[i].r) add(c[++r]);  
        while(r > q[i].r) del(c[r--]);  
        while(l < q[i].l) del(c[l++]);  
        while(l > q[i].l) add(c[--l]);  
		u[q[i].id]=ans;
	}
	for(int i=1;i<=m;i++)
		printf("%lld\n",u[i]);
	return 0;
}

http://codeforces.com/problemset/problem/617/E 其实用到的就是异或的很简单的性质。。。 但是我却想了半天都没想到，真是好菜啊。。。 设\(sum[i]\)为异或的前缀和，\(sum[i-1] \otimes sum[j]=k\)就是\(i\)到\(j\)的异或值为\(k\)的条件，然后拿莫队简单处理一下就好了，还是比较简单的。

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
#include<bits/stdc++.h>
using namespace std;
#define N 3000010
typedef long long LL;
int n,m,k,pos[N],c[N];
LL s[N],ans;
LL fa[N];
struct query{
	int l,r,id;
} q[N];
bool cmp(query x,query y)
{
	if(pos[x.l]==pos[y.l]) return x.r<y.r;
	return x.l<y.l;
}
void update(int p,int add)
{
	if(add==-1)
	{
		s[c[p]]--;
		ans-=s[c[p]^k];
	}
	else
	{
		ans+=s[c[p]^k];
		s[c[p]]++;
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
	}
	for(int i=1;i<=n;i++)
	{
		c[i]^=c[i-1];
	}
	int block=int(sqrt(n));
	for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].l--;
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	for(int i=1,l=0,r=-1;i<=m;i++)
	{
		for(;r<q[i].r;r++)
			update(r+1,1);
		for(;r>q[i].r;r--)
			update(r,-1);
		for(;l<q[i].l;l++)
			update(l,-1);
		for(;l>q[i].l;l--)
			update(l-1,1);
		fa[q[i].id]=ans;
		
	}
	for(int i=1;i<=m;i++)
		printf("%I64d\n",fa[i]);
	return 0;
}

http://codeforces.com/contest/700/problem/D 这个题我觉得还是很强的。 其实这个题目的难点完全不在莫队算法的设计上啊orz。 用莫队来维护每个值出现的次数，出现次数相同的值再丢到同一个数组下标中来维护。 比较精髓的地方是哈夫曼树的构造，这个地方竟然可以分块。 对于出现次数小于\(\sqrt N\)的值，我们可以一路枚举推过去。 对于出现次数大于\(\sqrt N\)的值，一定不会太多，我们可以正常的用优先队列来进行维护。 然后总的复杂度就是\(O(N\sqrt NlogN)\)

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;
#define N 3000010
#define pb push_back
typedef long long LL;
int n,m,k,pos[N],c[N];
int num[N];
int cnt[N];
int num1[N];
int u[N];
LL fa[N];
int block;
vector<int> t;
struct query{
	int l,r,id;
} q[N];
bool cmp(query x,query y)
{
	if(pos[x.l]==pos[y.l]) return x.r<y.r;
	return x.l<y.l;
}
void update(int p,int add)
{
	num[u[c[p]]]--;
	u[c[p]]+=add;
	num[u[c[p]]]++;
}
LL cal()
{
	priority_queue<int,vector<int>,greater<int> > q;
	for(auto &i:t)
	{
		if(u[i]>block) q.push(u[i]);
	}
	LL ret=0;
	int pr=0;
	for(int i=1;i<=block;i++)
	{
		num1[i]=num[i];
	}
	for(int i=1;i<=block;i++)
	{
		if(num1[i]==0) continue;
		if(pr)
		{
			num1[i]--;
			if(i+pr<=block) num1[i+pr]++;
			else q.push(i+pr);
			ret+=i+pr;
			pr=0;
		}
		if(num1[i]&1)
		{	
			num1[i]--; pr=i;
		}
		if(i*2>block)
		{
			for(int j=1;j<=num1[i]/2;j++)
			{
				q.push(i*2);
			}
		}
		else num1[i*2]+=num1[i]/2;
		ret+=num1[i]*i;
	}
	if(pr!=0) q.push(pr);
	while(!q.empty())
	{
		int a=q.top(); q.pop();
		if(q.size()==0) break;
		int b=q.top(); q.pop();
		q.push(a+b); ret+=a+b;
	}
	return ret;
}
int main()
{
	scanf("%d",&n);
	block=int(sqrt(n));
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&c[i]);
		cnt[c[i]]++;
		if(cnt[c[i]]==block)
		{
			t.pb(c[i]);
		}
	}
	scanf("%d",&m);
	for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	for(int i=1,l=0,r=-1;i<=m;i++)
	{
		for(;r<q[i].r;r++)
			update(r+1,1);
		for(;r>q[i].r;r--)
			update(r,-1);
		for(;l<q[i].l;l++)
			update(l,-1);
		for(;l>q[i].l;l--)
			update(l-1,1);
		fa[q[i].id]=cal();
		
	}
	for(int i=1;i<=m;i++)
		printf("%I64d\n",fa[i]);
	return 0;
}