一些奇怪的莫队技巧

最近想填一下以前学莫队时候留下来的坑,就是回滚莫队和二次离线莫队啦

回滚莫队

适用范围:

  • 问题可以莫队。(询问可以离线,不带修改)
  • 区间伸长的时候很好维护信息
  • 区间缩短的时候不太好维护信息(如最大值,删除以后不知道次大值是多少)

怎么做呢?

  • 首先,我们把询问按照莫队的顺序排序
  • 这样询问被分成了若干个段落。每段内,询问的左端点在同一个块,右端点递增。
  • 我们分段来处理:(设这一段的左端点为L[i],右端点是R[i]
  • 每一段开始时,$l\leftarrow R[i]+1,r\leftarrow R[i]$,表示初始的空区间。
  • 若左右端点都在这个块内的询问,我们直接暴力,显然$O(\sqrt n)$
  • 现在,我们可以假定对于所有询问,均有$Q[j].r>R[i]$
  • 每处理一个询问,我们先将r移动到该询问的右端点,保存下来此时的信息。
  • 将l移动到询问的左端点,此时可以求出答案。
  • $l\leftarrow R[i]+1$,用刚才保存的信息来恢复现场。

每段内,右端点单调递增,移动的时间复杂度$O(n)$,一共有$\sqrt n$段。左端点在同一块内,移动时间复杂度$O(\sqrt n)$,一共有n个左端点。暴力处理小段询问复杂度$O(\sqrt n)$。所以总的时间复杂度为$O(n\sqrt n)$,不变。而且可以看到,所有的操作都是在扩张区间,避免了收缩区间的麻烦,可以更方便地维护信息。

例题:AtCoder 1219 历史研究
代码在这里~

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 <cstdio>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <algorithm>

using std::sort;
using std::unique;
using std::lower_bound;

const int maxn=2e5+100;

int a[maxn],b[maxn];
int L[maxn],R[maxn],blo[maxn];

struct Qry
{
int l,r,id;
bool operator< (const Qry& q){return blo[l]==blo[q.l]?r<q.r:l<q.l;}
}Q[maxn];

template<class T>inline T max(T a,T b){return a<b?b:a;}
template<class T>inline T min(T a,T b){return a<b?a:b;}

int cnt[maxn];
int64_t tmp;

inline void add(int x,int val=1)
{
cnt[a[x]]+=val;
tmp=max(tmp,(int64_t)cnt[a[x]]*b[a[x]]);
}

inline int64_t brute_force(int l,int r)
{
static int c[maxn];
int64_t ans=0;
for (int i=l;i<=r;++i) ++c[a[i]];
for (int i=l;i<=r;++i) ans=max(ans,(int64_t)c[a[i]]*b[a[i]]);
for (int i=l;i<=r;++i) --c[a[i]];
return ans;
}

int main()
{
int n,q;
scanf("%d%d",&n,&q);
for (int i=1;i<=n;++i)
scanf("%d",a+i),b[i]=a[i];
for (int i=1;i<=q;++i)
scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
sort(b+1,b+n+1);
int tot=unique(b+1,b+n+1)-b-1;
// for (int i=1;i<=tot;++i) printf("%d ",b[i]);
// putchar('\n');
// printf("%d\n",tot);
for (int i=1;i<=n;++i)
a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
int T=sqrt(n),bl=n/T;
for (int i=1;i<=bl;++i)
L[i]=R[i-1]+1,R[i]=L[i]+T-1;
if (R[bl]<n) ++bl,L[bl]=R[bl-1]+1,R[bl]=n;
for (int i=1;i<=n;++i)
blo[i]=(i-1)/T+1;
sort(Q+1,Q+q+1);
static int64_t ans[maxn];
for (int i=1,lp=1,r=0,l=0;i<=bl;++i)
{
memset(cnt,0,sizeof(cnt));
r=R[i];
tmp=0;
// for (l=L[i];l<=R[i];++l) add(l,-1);
while (blo[Q[lp].l]==i)
{
l=R[i]+1;
if (Q[lp].r-Q[lp].l<=T)
{
ans[Q[lp].id]=brute_force(Q[lp].l,Q[lp].r);
++lp;
continue;
}
while (Q[lp].r>r) add(++r);
int64_t now=tmp;
while (l>Q[lp].l) add(--l);
ans[Q[lp].id]=tmp;
tmp=now;
while (l<=R[i]) --cnt[a[l++]];
++lp;
}
}
for (int i=1;i<=q;++i) printf("%lld\n",ans[i]);
}

二次离线莫队

适用范围:

  • 可以莫队
  • 更新答案的时间不是O(1)(一个数对答案的贡献与区间中别的数有关,例如比一个数小的数有多少)

二次离线莫队,通过扫描线,再次将更新答案的过程离线处理,降低时间复杂度。假设更新答案的复杂度为$O(k)$,它将莫队的复杂度从$O(nk\sqrt n)$降到了$O(nk + n\sqrt n)$,大大简化了计算。
设x对区间[l..r]的贡献为$\mathrm f(x,[l,r])$
我们考虑区间端点变化对答案的影响:
以$[l..r]$ 变成 $[l..(r+k)]$为例
$$\forall x \in [r+1,r+k]$$

$$\mathrm f(x,[l,x-1])$$
我们可以进行差分:
$$\mathrm f(x,[l,x-1])=f(x,[1,x-1])-f(x,[1,l-1])$$

这样转化为了一个数对一个前缀的贡献。保存下来所有这样的询问,从左到右扫描数组计算就可以了。
但是这样做,空间是$O(n\sqrt n)$的,不太优秀,而且时间常数巨大。。
这样的贡献分为两类:

  1. 减号左边的贡献永远是一个前缀 和它后面一个数的贡献。这可以预处理出来。
  2. 减号右边的贡献对于一次移动中所有的x来说,都是不变的。我们打标记的时候,可以只标记左右端点。
    这样,减小时间常数的同时,空间降为了$O(n)$级别。是一个很优秀的算法了。

例题:第十四分块(前体)

处理前缀询问的时候,我们利用异或运算的交换律,即$a \mathrm{xor} b=c \Longleftrightarrow a \mathrm{xor} c=b$
开一个桶t,t[i]表示当前前缀中与i异或有k个数位为1的数有多少个。
则每加入一个数a[i],对于所有$\mathrm{popcount}(x)==k$的x,$++t[a[i] \mathrm{xor} x]$即可。

代码:

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
#include <cstdio>
#include <cmath>
#include <cstdint>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <utility>
#include <tuple>

using std::tuple;
using std::make_pair;
using std::vector;
using std::sort;
using std::sort;
using std::pair;
using std::get;

const int maxn=1e5+100;

int blo[maxn],a[maxn];

struct Qry
{
int l,r,id;
int64_t ans;
inline bool operator< (const Qry& q){return blo[l]==blo[q.l]?r<q.r:l<q.l;}
}Q[maxn];

vector<tuple<int,int,int>> v[maxn];

int main()
{
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
if (k>14)
{
for (int i=1;i<=m;++i) puts("0");
return 0;
}
for (int i=1;i<=n;++i)
scanf("%d",a+i);
for (int i=1;i<=m;++i)
scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
vector<int> buc;
for (int i=0;i<16384;++i)
if (__builtin_popcount(i)==k) buc.push_back(i);
// for (auto x:buc)
// fprintf(stderr,"%d ",x);
int T=sqrt(n);
for (int i=1;i<=n;++i) blo[i]=(i-1)/T+1;
sort(Q+1,Q+m+1);

/***************/
/* L右移:l正r负 *\
/* l左移:l负r正 *\
/* r右移:r正l负 *\
/* r左移:r负l正 *\
/***************/
static int t[maxn];
static int pref[maxn];
for (int i=1;i<=n;++i)
{
for (auto x:buc) ++t[a[i]^x];
pref[i]=t[a[i+1]];
}
memset(t,0,sizeof(t));
// 预处理前缀贡献
for (int i=1,L=1,R=0;i<=m;++i)
{
int l=Q[i].l,r=Q[i].r;
if (L<l) v[R].emplace_back(L,l-1,-i);
while (L<l) {Q[i].ans+=pref[L-1];++L;}
if (L>l) v[R].emplace_back(l,L-1,i);
while (L>l) {Q[i].ans-=pref[L-2];--L;}
if (R<r) v[L-1].emplace_back(R+1,r,-i);
while (R<r) {Q[i].ans+=pref[R];++R;}
if (R>r) v[L-1].emplace_back(r+1,R,i);
while (R>r) {Q[i].ans-=pref[R-1];--R;}
}
//模拟莫队,算出来第一类贡献,对第二类贡献打上标记
static int64_t ans[maxn];
for (int i=1,id,l,r;i<=n;++i)
{
for (auto x:buc) ++t[a[i]^x];
for (const auto& x:v[i])
{
std::tie(l,r,id)=x;
// if (i>=l) fprintf(stderr,"%d %d\n",i,l);
for (int j=l,tmp=0;j<=r;++j)
{
tmp=t[a[j]];
if (j<=i && k==0) --tmp;// 这里(按我的蒟蒻写法)k==0的时候需要特判,因为x^x永远是0,但自己对自己不能产生贡献。
if (id<0) Q[-id].ans-=tmp;
else Q[id].ans+=tmp;
}
}
}
for (int i=1;i<=m;++i) Q[i].ans+=Q[i-1].ans;
for (int i=1;i<=m;++i) ans[Q[i].id]=Q[i].ans;
for (int i=1;i<=m;++i) printf("%lld\n",ans[i]);
}

莫队真是个好东西,可惜我不会…