莫队
普通版
前言
莫队是由集训队大佬莫涛提出来的，在此再次膜拜大佬！
思想
普通莫队主要用于离线的区间查询操作，当然，也不是所有的都适用，当一个区间 [l,r] 的答案可以用 O(1) 的时间转化成 [l+1,r],[l−1,r],[l,r+1],[l,r−1] 的答案，我们就可以考虑使用莫队。
具体怎么做呢？其实就是将当前区间的答案通过一次一次移动 l,r 变成另一个区间的答案。
然后就没有了？
当然不是，这样很容易就被卡了，怎么卡呢，只需要将一次询问放在最前，下一次有放在最后，如此循环往复，这样我们每次就会移动 n 次，就足够卡爆这个没加任何优化的方法。
怎么优化呢？我们可以修改每个询问的顺序，尽量让两个询问之间移动次数最少，这里说一种咋看有点玄学的方法，我们把序列分成 n 个块，如果两个点的左端点不在同一块，左端点小的放前面，如果左端点所在块相同，那就比较右端点，右端点小的排前面。
复杂度证明
可以证明，最坏复杂度为 O(nn)。我有一个绝妙的证明方法，可惜这里的空白太小了（分明是作者不会）。
优化
还能优化？没错，我们修改一下排序规则，如果两个点的左端点不在同一块，左端点小的放前面，如果左端点所在块相同，那就比较右端点，如果当前块编号为奇数，右端点小的放前面，否则右端点大的放前面。还想问为什么？应该不需要我放那句话了吧。
小B的询问
题面
小B 有一个长为 n 的整数序列 a，值域为 [1,k]。
他一共有 m 个询问，每个询问给定一个区间 [l,r]，求：
i=1∑kci2
其中 ci 表示数字 i 在 [l,r] 中的出现次数。
小B请你帮助他回答询问。
思路
莫队板子题。问题在于该如何修改呢？其实很简单，当我们将某个点加入当前区间时，设这个点所表示的值在当前区间的值为 x，那么答案会增加 (x+1)2−x2=2x+1，当我们将某个点从当前区间删除时，设这个点所表示的值在当前区间的值为 x，那么答案会减少 x2−(x−1)2=2x−1。
代码
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
| #include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int a[50010];
int b[50010];
int pos[50010];
long long ans[50010];
struct node{
int l,r;
int idx;
}c[50010];
long long cnt=0;
bool cmplr(node a,node b){
if(pos[a.l]!=pos[b.l])return a.l<b.l;
if(pos[a.l]&1)return a.r<b.r;
return a.r>b.r;
}
void pplus(int x){
cnt+=(b[x]*2)+1;
b[x]++;
return;
}
void perase(int x){
cnt-=(b[x]*2)-1;
b[x]--;
return;
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n,m,k;
cin>>n>>m>>k;
int block=n/sqrt(m);
for(int i=1;i<=n;i++){
cin>>a[i];
pos[i]=(i-1)/block+1;
}
for(int i=1;i<=m;i++){
cin>>c[i].l>>c[i].r;
c[i].idx=i;
}
sort(c+1,c+m+1,cmplr);
int l=1,r=0;
for(int i=1;i<=m;i++){
while(l>c[i].l){
l--;
pplus(a[l]);
}
while(r<c[i].r){
r++;
pplus(a[r]);
}
while(l<c[i].l){
perase(a[l]);
l++;
}
while(r>c[i].r){
perase(a[r]);
r--;
}
ans[c[i].idx]=cnt;
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<"\n";
}
cout<<flush;
return 0;
}
|
小Z的袜子
题面
作为一个生活散漫的人，小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小 Z 再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小 Z 把这 N 只袜子从 1 到 N 编号，然后从编号 L 到 R 的袜子中随机选出两只来穿。尽管小 Z 并不在意两只袜子是不是完整的一双，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小 Z，他有多大的概率抽到两只颜色相同的袜子。当然，小 Z 希望这个概率尽量高，所以他可能会询问多个 (L,R) 以方便自己选择。
思路
其实没那么难，设当前区间编号为 i 的袜子有 x 双，根据概率论和一点数学，答案是：
2(r−l+1)×(r−l)∑i=lr2ci×(ci−1)=(r−1+1)×(r−l)∑i=lrci−(r−l+1)。现在会做了吧，就是上一题加一点东西。
代码
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
| #include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int a[50010];
int b[50010];
int pos[50010];
long long aa[50010],bb[50010];
struct node{
int l,r;
int idx;
}c[50010];
long long cnt=0;
bool cmplr(node a,node b){
if(pos[a.l]!=pos[b.l])return a.l<b.l;
if(pos[a.l]&1)return a.r<b.r;
return a.r>b.r;
}
void pplus(int x){
cnt+=(b[x]*2)+1;
b[x]++;
return;
}
void perase(int x){
cnt-=(b[x]*2)-1;
b[x]--;
return;
}
int pgcd(long long a,long b){
return b?pgcd(b,a%b):a;
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
int block=n/sqrt(m);
for(int i=1;i<=n;i++){
cin>>a[i];
pos[i]=(i-1)/block+1;
}
for(int i=1;i<=m;i++){
cin>>c[i].l>>c[i].r;
c[i].idx=i;
}
sort(c+1,c+m+1,cmplr);
long long l=1,r=0;
for(int i=1;i<=m;i++){
while(l>c[i].l){
l--;
pplus(a[l]);
}
while(r<c[i].r){
r++;
pplus(a[r]);
}
while(l<c[i].l){
perase(a[l]);
l++;
}
while(r>c[i].r){
perase(a[r]);
r--;
}
if(l==r){
aa[c[i].idx]=0;
bb[c[i].idx]=1;
}else{
aa[c[i].idx]=cnt-(r-l+1);
bb[c[i].idx]=(r-l+1)*(r-l);
int t=pgcd(aa[c[i].idx],bb[c[i].idx]);
aa[c[i].idx]/=t;
bb[c[i].idx]/=t;
}
}
for(int i=1;i<=m;i++){
cout<<aa[i]<<"/"<<bb[i]<<"\n";
}
cout<<flush;
return 0;
}
|