莫队 && 洛谷 P1494 [国家集训队]小Z的袜子

传送门

莫队

莫队就是一个优雅的暴力。

莫队就是把询问分块+排序，第一关键字为左端点在第几块，第二关键字为区间右端点。

条件？问题离线，询问的是区间。

名字由来？一个国家队队长发明的=

解题思路

对于区间i...j，成功的概率为:

不必解释了（学过排列组合的都懂，像我一样没学过的也想不懂）

整理一下，就是：

这样对于每个询问，得到分子是多少就可以知道答案。

再进一步整理一下，统计分子，每加入或删除一个数，实际上就是加或者减2*cnt[i]，所以一个一个加，一个一个减，统计着答案，最后排序回去，就AC了。

左端点l每次移动最多sqrt(n)，最多移动m次，总共O(sqrt(n)*m)。

右端点每个块内最多移动n次，一共sqrt(n)个块，总共O(sqrt(n)*n)。

所以最后的时间复杂度为O(sqrt(n)*(n+m))。

AC代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<set>
 9 #include<map>
10 #include<vector>
11 #include<iomanip>
12 #include<ctime>
13 #include<stack>
14 using namespace std;
15 const int maxn=50005;
16 int n,m,id[maxn],cnt[maxn],sq,a[maxn],now=1,cntt;
17 long long sum;
18 struct node{
19     int l,r,id;
20     long long ans;
21 }d[maxn];
22 bool cmp(node a,node b){
23     if(id[a.l]!=id[b.l]) return id[a.l]<id[b.l];
24     return (id[a.l]&1)?a.r<b.r:a.r>b.r;
25 }
26 bool cmp2(node a,node b){
27     return a.id<b.id;
28 }
29 long long gcd(long long a,long long b){
30     if(b==0) return a;
31     return gcd(b,a%b);
32 }
33 void shuchu(long long a,long long b){
34     if(a==0) printf("%d/%d
",0,1);
35     else{
36         int d=gcd(a,b);
37         printf("%lld/%lld
",a/d,b/d);
38     }
39 }
40 int main()
41 {
42     cin>>n>>m;
43     for(int i=1;i<=n;i++) cin>>a[i];
44     int sq=sqrt(n);
45     if(sq*sq<n) sq++;
46     for(int i=1;i<=n;i++){
47         if(cntt==sq){
48             cntt=0;
49             now++;
50         }
51         cntt++;
52         id[i]=now;
53     }
54     for(int i=1;i<=m;i++){
55         cin>>d[i].l>>d[i].r;
56         d[i].id=i;
57     }
58     sort(d+1,d+m+1,cmp);
59     int l=1,r=0;
60      for(int i=1;i<=m;i++){
61         if(d[i].l==d[i].r){
62             d[i].ans=0;
63             continue;
64         }
65         while(l>d[i].l){
66             l--;
67             sum+=2*cnt[a[l]];
68             cnt[a[l]]++;
69         }
70         while(r<d[i].r){
71             r++;
72             sum+=2*cnt[a[r]];
73             cnt[a[r]]++;
74         }
75         while(l<d[i].l){
76             cnt[a[l]]--;
77             sum-=2*cnt[a[l]];
78             l++;
79         }
80         while(r>d[i].r){
81             cnt[a[r]]--;
82             sum-=2*cnt[a[r]];
83             r--;
84         }
85         d[i].ans=sum;
86     }
87     sort(d+1,d+m+1,cmp2);
88     for(int i=1;i<=m;i++) {
89         shuchu(d[i].ans,((long long)(d[i].r-d[i].l+1))*(d[i].r-d[i].l));
90     }
91     return 0;
92 }