_WA自动机的blog

过期高中生。

一些奇怪的莫队技巧

发表于 更新于 阅读次数： Valine：

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

回滚莫队

适用范围：

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

怎么做呢？

  • 首先，我们把询问按照莫队的顺序排序
  • 这样询问被分成了若干个段落。每段内，询问的左端点在同一个块，右端点递增。
  • 我们分段来处理：（设这一段的左端点为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]);
}

莫队真是个好东西，可惜我不会...