莫队总结

orz，自从艾教的集训回来之后就一直很颓废，迎新也差点把命给送掉了，回家之后更是颓废……不管了，先总结一下在艾教那的收获吧，这次最大的收获我觉得就是莫队算法了……

关于莫队
以前一直在听说莫队算法很神，说能处理一切区间问题，就感觉这个算法肯定很难很难，也就一直没动……结果这次听艾教讲完，发现莫队是个非常友好的算法，很简单也很好写，套个板子基本就解决了……

莫队的思想在于分块，在两个查询的区间变化不大的情况下直接继承上次查询的结果进行微调。一般将一整个大区间分为根号块，每块长度为根号，不过不同题目具体分法也不一定相同。莫队本身就是个乱搞算法，很多时候都是钻了数据的空子才能过的，所以分法也就多种多样。

首先，莫队是一个离线算法，根据查询来决定访问。
步骤大概如下
1.读入所有查询，将查询进行排序，排序的第一关键字为左边界所在的块，第二关键字为右边界。
2.暴力得出第一个查询所要的答案，作为基本答案
3.根据上次查询的答案，移动左边界与右边界并更新答案，直到现在的区间与下次查询区间一致。
4.重复3直到所有查询的答案都已得出
5.根据查询的输入顺序输出答案

关于莫队算法的复杂度
对于每一个块，右指针最多走n步，所以右指针的最坏情况是n根号n。左指针的话，在一个块内，每查一次最多走根号n步，所以左指针总复杂度为m根号n，m为查询总数。
所以莫队的总复杂度大约在n*根号n。

讲的可能不太清楚，放几个题目看看代码就明白了

hdu 5145 NPY and girls
这题是一个求排列数的题目，中间用到了逆元，逆元当时也是现学现卖……

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
114
115
116
117
118
119
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
int nn;
long long mod=1000000007;
long long inv[30004];
long long jiecheng[30004];
long long pp(long long a,long long b)  
{  
    long long ans = 1;  
    a %= mod;  
    while(b)  
    {  
        if(b & 1)  
        {  
            ans = ans * a % mod;  
            b--;  
        }  
        b >>= 1;  
        a = a * a % mod;  
    }  
    return ans;  
}  
struct node 
{
	int l,r,id;
	long long ans;
};
int cmp1(node a,node b)
{
	if(b.l/nn==a.l/nn)return a.r<b.r;
	 else return a.l/nn<b.l/nn;
}
int cmp2(node a,node b)
{
  return a.id<b.id;	
}
int main()
{  
   int i,j,k,m,n;
   long long a[30004];
   node b[30004];
   int cnt[30004];
   int t;
   for(long long i=1;i<=30000;i++)inv[i]=pp(i,mod-2);
   jiecheng[0]=1;
   for(long long i=1;i<=30000;i++)jiecheng[i]=jiecheng[i-1]*i%mod;
   //printf("%d\n",10*inv[5]%mod);
   scanf("%d",&t);
   while(t--)
   {memset(b,0,sizeof(b));
    memset(cnt,0,sizeof(cnt)); 
   	scanf("%d%d",&n,&m);
   	nn=sqrt(n);
   	for(int i=1;i<=n;i++)
	   {scanf("%lld",a+i);
        //cnt[a[i]]++;
	   }
   	for(int i=1;i<=m;i++)
   	{
   		node temp;
   		scanf("%d%d",&temp.l,&temp.r);
   		temp.id=i;
   		b[i]=temp;
	}
	sort(b+1,b+1+m,cmp1);
	//printf("sort yes\n");
	long long ans=1;
	ans=ans*jiecheng[b[1].r-b[1].l+1]%mod;
	//printf("ans  %lld\n",ans);
	for(int i=b[1].l;i<=b[1].r;i++)
	 {
	 	cnt[a[i]]++;
	 	//printf("%d:inv:%lld\n",i,inv[cnt[a[i]]]%mod);
	 	ans=ans*inv[cnt[a[i]]]%mod;
	 }
	 b[1].ans=ans;  
	for(int i=2;i<=m;i++)
	{  int l=b[i-1].l;
	   int r=b[i-1].r;
	   int ll=b[i].l;
	   int rr=b[i].r;
	   while(r<rr)
	   {r++;cnt[a[r]]++;
	   	 ans=ans*(r-b[i-1].l+1)%mod*inv[cnt[a[r]]]%mod;
	   }
	   while(r>rr)
	   {
	    ans=ans*inv[r-b[i-1].l+1]%mod*(cnt[a[r]])%mod;
		cnt[a[r]]--;	
		r--;
	   }
	   while(l<ll)
	   {
		 ans=ans*inv[r-l+1]%mod*cnt[a[l]]%mod;	
		 cnt[a[l]]--; 
		  l++;
	   }
	   while(l>ll)
	   { l--;
	     cnt[a[l]]++;
		ans=ans*(r-l+1)%mod*inv[cnt[a[l]]]%mod;   
		}	
	   b[i].ans=ans;	
	}   
	sort(b+1,b+1+m,cmp2);
	for(int i=1;i<=m;i++)printf("%lld\n",b[i].ans);   
   }	
   return 0;
}

hdu 4638 Group
这个题是裸的莫队，比上一道还要简单不少

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
114
115
116
117
118
119
120
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
int nn;
long long mod=1000000007;
long long inv[30004];
long long jiecheng[30004];
long long pp(long long a,long long b)  
{  
    long long ans = 1;  
    a %= mod;  
    while(b)  
    {  
        if(b & 1)  
        {  
            ans = ans * a % mod;  
            b--;  
        }  
        b >>= 1;  
        a = a * a % mod;  
    }  
    return ans;  
}  
struct node 
{
	int l,r,id;
	long long ans;
};
int cmp1(node a,node b)
{
	if(b.l/nn==a.l/nn)return a.r<b.r;
	 else return a.l/nn<b.l/nn;
}
int cmp2(node a,node b)
{
  return a.id<b.id;	
}
int main()
{  
   int i,j,k,m,n;
   long long a[30004];
   node b[30004];
   int cnt[30004];
   int t;
   for(long long i=1;i<=30000;i++)inv[i]=pp(i,mod-2);
   jiecheng[0]=1;
   for(long long i=1;i<=30000;i++)jiecheng[i]=jiecheng[i-1]*i%mod;
   //printf("%d\n",10*inv[5]%mod);
   scanf("%d",&t);
   while(t--)
   {memset(b,0,sizeof(b));
    memset(cnt,0,sizeof(cnt)); 
   	scanf("%d%d",&n,&m);
   	nn=sqrt(n);
   	for(int i=1;i<=n;i++)
	   {scanf("%lld",a+i);
        //cnt[a[i]]++;
	   }
   	for(int i=1;i<=m;i++)
   	{
   		node temp;
   		scanf("%d%d",&temp.l,&temp.r);
   		temp.id=i;
   		b[i]=temp;
	}
	sort(b+1,b+1+m,cmp1);
	//printf("sort yes\n");
	long long ans=1;
	ans=ans*jiecheng[b[1].r-b[1].l+1]%mod;
	//printf("ans  %lld\n",ans);
	for(int i=b[1].l;i<=b[1].r;i++)
	 {
	 	cnt[a[i]]++;
	 	//printf("%d:inv:%lld\n",i,inv[cnt[a[i]]]%mod);
	 	ans=ans*inv[cnt[a[i]]]%mod;
	 }
	 b[1].ans=ans;  
	for(int i=2;i<=m;i++)
	{  int l=b[i-1].l;
	   int r=b[i-1].r;
	   int ll=b[i].l;
	   int rr=b[i].r;
	   while(r<rr)
	   {r++;cnt[a[r]]++;
	   	 ans=ans*(r-b[i-1].l+1)%mod*inv[cnt[a[r]]]%mod;
	   }
	   while(r>rr)
	   {
	    ans=ans*inv[r-b[i-1].l+1]%mod*(cnt[a[r]])%mod;
		cnt[a[r]]--;	
		r--;
	   }
	   while(l<ll)
	   {
		 ans=ans*inv[r-l+1]%mod*cnt[a[l]]%mod;	
		 cnt[a[l]]--; 
		  l++;
	   }
	   while(l>ll)
	   { l--;
	     cnt[a[l]]++;
		ans=ans*(r-l+1)%mod*inv[cnt[a[l]]]%mod;   
		}	
	   b[i].ans=ans;	
	}   
	sort(b+1,b+1+m,cmp2);
	for(int i=1;i<=m;i++)printf("%lld\n",b[i].ans);   
   }	
   return 0;
}

UESTC 1256 昊昊爱运动
莫队应该不是这题的正解，当时比赛的时候用莫队一直超时……结果康宁告诉我最后不排序直接根据标记输出答案就不超时了……orz，只能膜拜

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
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
struct node 
{
	int l,r,id;
	int ans;
}q[10000006];
int nn;
int aa[10000006];
int cmp1(node a,node b)
{
	if(b.l/nn==a.l/nn)return a.r<b.r;
	 else return a.l/nn<b.l/nn;
}
int cmp2(node a,node b)
{
  return a.id<b.id;	
}
int main()
{
	int vis[150];
	int a[2004];
    int i,j,k,m,n,qq;
    while(~scanf("%d%d",&n,&m))
    {   int cnt=0;
         nn=sqrt(n);
        memset(vis,0,sizeof(vis));
    	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    	scanf("%d",&qq);
    	for(int i=1;i<=qq;i++)
    	{
    		int l,r;
    		scanf("%d%d",&l,&r);
    		q[i].l=l;
    		q[i].r=r;
    		q[i].id=i;
		}
		sort(q+1,q+1+qq,cmp1);
		for(int i=q[1].l;i<=q[1].r;i++)
		 {
		 	if(vis[a[i]]==0)
		 	{
		 		cnt++;
			 }
			vis[a[i]]++; 
		 }
		q[1].ans=cnt;
		aa[q[1].id]=cnt;
		for(int i=2;i<=qq;i++)
		{
		  	int l=q[i-1].l;
	        int r=q[i-1].r;
	        int ll=q[i].l;
	        int rr=q[i].r;
		    while(r<rr)
		    {
		      r++;
		      if(vis[a[r]]==0)cnt++;
		      vis[a[r]]++;
			}
			while(r>rr)
			{
				vis[a[r]]--;
				if(vis[a[r]]==0)cnt--;
				r--;
			}
			while(l<ll)
			{
				vis[a[l]]--;
				if(vis[a[l]]==0)cnt--;
				l++;
			}
			while(l>ll)
			{   l--;
				if(vis[a[l]]==0)cnt++;
				vis[a[l]]++;
			}
			q[i].ans=cnt;
			aa[q[i].id]=cnt;
		 }
		 
		 for(int i=1;i<=qq;i++)printf("%d\n",aa[i]); 
	}
	return 0;
}

先这么多吧……感觉在家这一周又要颓废了……