Eternity

Until The End

莫队

发表于 更新于 分类于 ，
本文字数： 33k 阅读时长 ≈ 30 分钟

“迷旋交错的尖针，在不同的时间流速之中，下一秒，又会指向何方？”

莫队实际上是一种优化暴力的离线算法，其收集所有的询问，并统一处理。

给出文章的宏定义：

$n$ 为数列长度，$m$ 为询问个数。

暴力莫队

这是一个不可过的算法，时间复杂度 $\mathcal O(nm)$ 。

其实现在于：

离线后用一种方式为询问排序，一次处理，并使用 $i-1$ 区间的答案转移至 $i$ 区间。通俗的讲，就是类似于记忆化，用已经得到的答案来处理当前询问。

转移

对于当前指针 $i,j$ 表示 $[l_{k-1},r_{k-1}]$ 的区间，那么，移动 $j$ 从 $r_{k-1}$ 至 $r_k$ ，并每一次加入当前数 $x_j$ ，并更新答案；然后移动 $i$ 指针至 $l_{k-1}$ ，以此更新答案直到到达区间 $[l_k,r_k]$ 。

这种转移方式类似于双指针算法。

分析

这样的时间复杂度依然是 $\mathcal O(nm)$ ，对于每一询问，$i,j$ 的移动次数都是 $n$ 级的。

基础莫队

我们需要把 $\mathcal O(nm)$ 优化到 $\mathcal O(n\sqrt n)$ ，而对于带根号的时间，就肯定会想到分块。

分析

更改排序方式为：

以 $bel[l]$ 为第一关键字，$r$ 为第二关键字，从小到大。
通俗的讲，首先排左指针的块编号，然后单调右指针。

此时的复杂度也是可以计算的：

右指针 $r$ 最多移动 $\mathcal O(n\sqrt n)$ 次，

而对于左指针：

  • 在块内，最多移动 $\mathcal O(\sqrt n)$ 次，共 $\mathcal O(m\sqrt n)$ 次；
  • 块与块之间，共 $\mathcal O(2\sqrt n)$ 次，共 $\mathcal O(2n)$ 次。

由此，时间复杂度为 $\mathcal O(m\sqrt n)$ 次。

可以证明，当块长为 $\frac{n}{\sqrt m}$ 时，时间复杂度最优。

其分析可见 $\text{OI-Wiki}$ 。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline void Move(int pos,int val)
{
	//update res
}
inline void Solve()
{
    std::sort(Que+1,Que+1+M,cmp);
    for(int i=1,l=0,r=0;i<=M;++i)
    {
        const Query &q=Que[i];
        while(l>q.l) Move(--l,1);
        while(r<q.r) Move(r++,1);
        while(l<q.l) Move(l++,-1);
        while(r>q.r) Move(--r,-1);
        ans[q.id]=res;
    }
}

如果觉得 val 的定义不够明确，也可以使用下列方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
inline void Move(int pos,int val)
{
	//update res
}
inline void Solve()
{
    std::sort(Que+1,Que+1+M,cmp);
    for(int i=1,l=0,r=0;i<=M;++i)
    {
        const Query &q=Que[i];
        while(l>q.l) add(--l);
        while(r<q.r) add(r++);
        while(l<q.l) del(l++);
        while(r>q.r) del(--r);
        ans[q.id]=res;
    }
}

例题

HH 的项链

给出一个长度为 $n$ 的数列 $a$ 和 $m$ 个询问：

每次询问一个区间 $[l,r]$ ，求 $[a_l,a_r]$ 中不同数字的个数。

其中 $n\leq 10^5,m\leq 2\times10^5$ 。

其实洛谷上是有这道题的，但数据经过了加强，使普通莫队无法通过，变成了主席树的练习题，但魔改莫队算法可以过（之后会提及）。

因为 Solve() 是一样的，所以这里只给出 Move() 的写法。

1
2
3
4
5
6
inline void Move(int pos,int val)
{
    if(!Cnt[pos]&&val==1) ++res;
   	Cnt[pos]+=val;
    if(!Cnt[pos]) --res; 
}

P1494

背到了莫队的板子之后，就只需要考虑填充 add() 和 del() 就好了。（就像是学会了树链剖分就又回到了线段树一样）

对于区间 $[i,i]$ ，答案显然是 $1$ ，然后就从当前区间推进到下一区间。

定义当前颜色为 $Col[i]$ ，第 $i$ 种颜色出现的次数为 $Cnt[i]$ ，$res$ 为当前答案。

增长区间时，更新答案 $res+=C^2_{Cnt[Col[k]]+1}-C^2_{Cnt[Col[k]]}$ ；

缩短区间时，更新答案 $res-=C^2_{Cnt[Col[k]]}-C^2_{Col[Cnt[k]]-1}$ 。

询问答案为 $\frac{res}{C^2_{r-l+1}}$

其中 $C^2_{r-l+1}=\frac{(r-l)\times(r-l+1)}{2}$ 。

且有 $C^2_{a+1}-C^2_{a}=a$ ，所以 $C^2_{Cnt[Col[ik]+1}-C^2_{Cnt[Col[k]]}=Cnt[Col[k]]$ 。

AC Code 
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
121
122
123
124
125
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=5e4+10;
int N,M,Unit;
int Col[MAXN],Cnt[MAXN];
ll res,ans[2][MAXN];
struct Query
{
    int l,r,id;
    bool operator<(const Query &x) const
    {
        if(l/Unit!=x.l/Unit) return l<x.l;
        return (l/Unit)&1?r<x.r:r>x.r;
    }
}Que[MAXN];
inline void add(int pos)
{
    res+=Cnt[pos];++Cnt[pos];
}
inline void del(int pos)
{
    --Cnt[pos];res-=Cnt[pos];
}
ll Gcd(ll a,ll b)
{
    return b==0?a:Gcd(b,a%b);
}
inline void Solve()
{
    std::sort(Que+1,Que+1+M);
    for(int i=1,l=1,r=0;i<=M;++i)
    {
        auto q=Que[i];
        if(q.l==q.r)
        {
            ans[0][q.id]=0,ans[1][q.id]=1;
            continue;
        }
        while(l>q.l) add(Col[--l]);
        while(r<q.r) add(Col[++r]);
        while(l<q.l) del(Col[l++]);
        while(r>q.r) del(Col[r--]);
        ans[0][q.id]=res;
        ans[1][q.id]=1ll*(r-l+1)*(r-l)/2;
    }
    return ;
}
int main()
{
    // freopen("mo-algo.in","r",stdin);
    // freopen("mo-algo.out","w",stdout);
    read(N,M);
    Unit=sqrt((double)N*N/(double)M);
    for(int i=1;i<=N;++i) read(Col[i]);
    for(int i=1;i<=M;++i)
    {
        read(Que[i].l,Que[i].r);
        Que[i].id=i;
    }
    Solve();
    for(int i=1;i<=M;++i)
    {
        if(ans[0][i])
        {
            ll g=Gcd(ans[0][i],ans[1][i]);
            ans[0][i]/=g,ans[1][i]/=g;
        }
        else ans[1][i]=1;
        write(ans[0][i]),putchar('/'),
        write(ans[1][i]),puts("");
    }
    return 0;
}
/*
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6
*/

P2709

常规莫队板子，转移方程是平方差公式，应该都会：$a^2-(a-1)^2=2a-1$

AC Code 
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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=5e4+10;
int N,M,K,Uni;
int Val[MAXN],Cnt[MAXN],res;
struct Query
{
    int l,r,id;
    bool operator<(const Query &x) const
    {
        if(l/Uni!=x.l/Uni) return l<x.l;
        return (l/Uni)&1?r<x.r:r>x.r;
    }
}Q[MAXN];
int ans[MAXN];
inline void add(int pos)
{
    ++Cnt[pos];
    res+=(Cnt[pos]*2-1);
}
inline void del(int pos)
{
    res-=(Cnt[pos]*2-1);
    --Cnt[pos];
}
inline void Solve()
{
    std::sort(Q+1,Q+1+M);
    for(int i=1,l=2,r=1;i<=M;++i)
    {
        auto q=Q[i];
        while(l>q.l) add(Val[--l]);
        while(r<q.r) add(Val[++r]);
        while(l<q.l) del(Val[l++]);
        while(r>q.r) del(Val[r--]);
        ans[q.id]=res;
    }
}
int main()
{
    // freopen("mo-algo.in","r",stdin);
    // freopen("mo-algo.out","w",stdout);
    read(N,M,K);
    Uni=std::sqrt((double)N*N/(double)M);
    for(int i=1;i<=N;++i) read(Val[i]);
    for(int i=1;i<=M;++i)
    {
        read(Q[i].l,Q[i].r);
        Q[i].id=i;
    }
    Solve();
    for(int i=1;i<=M;++i) write(ans[i]),puts("");
    return 0;
}
/*
6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6
*/

奇偶化排序

我们已经知道了，当 $Uni=\frac{n}{\sqrt m}$ 时，莫队的复杂度应该是最优秀的。但是，仅仅从块长和单调两方面来排序的话，也是很有可能被卡掉的。

这个优化的意思是，在处理第奇数个问题时，将 $r$ 从小到大排序，而对于第偶数个问题，$r$ 从大到小，这样的话，我们在处理完一个问题时，可以到达的下一个问题的右指针是对于当前问题而言较近的。而不是为了全局最优而去舍掉局部最优。这个思路就有点像反悔贪心。用多个次优解顶替最优解。

后来这个优化被证明是正确的，其优化了 $r$ 的移动次数，在一般情况下，能够使莫队的时间复杂度降低 $30\%$ 左右。

有以下两种写法：

1
2
3
4
5
6
7
8
9
int Uni;
struct Query
{
    int l,r,id;
    bool operator<(const Query &x) const
    {
        return l/Uni==x.l/Uni?(r==x.r?0:((l/Uni)&1)^(r<x.r)):l<x.l;
    }
}Que[MAXN];
1
2
3
4
5
6
7
8
9
struct Query
{
    int l,r,id;
    bool operator<(const Query &x) const
    {
        if(l/Uni!=x.l/Uni) return l<x.l;
        return (l?Uni)&1?r<x.r:r>x.r;
    }
}Q[MAXN];

注意：这里 $r$ 和 $x.r$ 比较任何地方都不能取等，如果没有 r==x.r 的特判的话，因为不可以出现 $a>b$ 和 $a<b$ 同时成立的情况，否则会 $\text{RE}$ 。

后话

莫队的板子实际上比较简单，但是，里面有一个非常重要的易错点，即四个 while 的位置。

对于 l-- ，r-- ，l++ ，r++ 四个的排列，一共 $24$ 种，而实际上正确的只有 $6$ 种，其他的方式都会出锅。所以，建议读者在理解了其中一种之后就直接背熟，然后不要更改其顺序了。

带修莫队

也可以称作是可持久化莫队。

带修莫队，全称是支持修改的莫队算法。

实现

因为这是一个离线算法，而我们知道的是，对于第 $i$ 个询问，只有 $[1,i-1]$ 中的修改与该询问有关，而对于从 $k-1$ 到 $k$ 的转移，其编号不定。

那么，原本的莫队算法维护的是一个一维的数列，那么，我们拓展一维时间戳，使当前数列变成一个二维矩阵，其中 $(x,k)$ 表示 $val[x]$ 在第 $k$ 次操作之后的值。

接着，我们把询问中的 $[l,r]$ 升维成 $[l,r,time]$ ，并把原来 $4$ 个 while 加上 $2$ 个：

  • $[l,r,time+1]$ ;
  • $[l,r,time-1]$ 。

而到达我们需要的时间戳。

而对于询问的排序，除了原来的不变以外，计入第三关键字 $time$ ，从小到大。

再加入各种玄学的块长优化，奇偶化排序等，带修莫队的期望复杂度为 $\mathcal O(n^{\frac{5}{3}})$ 。

这里设块长为 $n^{\frac{2}{3}}$ ，共 $n^{\frac{1}{3}}$ ，第一关键字为 $l$ 指针所在块，第二关键字为 $r$ 指针所在块，第三关键字为 $time$ 。

分析

左右端点所在块不变时，时间在排序后单调右移，复杂度为 $\mathcal O(n)$ ；

左右段改变，时间移动不超过 $n$ 次，复杂度 $\mathcal O(n)$ ；

左端点极块 $n^{\frac{1}{3}}$ ，右端点一样，共 $n^{\frac{1}{3}}\times n^{\frac{1}{3}}=n^{\frac{2}{3}}$ 种，每次移动的最大复杂度为 $\mathcal O(n)$ ，则带修莫队的期望复杂度为 $\mathcal O(n^{\frac{5}{3}})$ 。

例题

P1903

对于第一个操作，就是莫队板子。

然后添上第二个操作，就用上述说到的时间戳即可。

对于每一次时间位移，我们就可以交换当前 $val[x]$ 和需要修改的 $ch[k].c$ ，然后更新答案，如果再次便利，则再次交换即可。

对于带修莫队，离谱的是，因为 $\mathcal O(n^{\frac{5}{3}})$ 的复杂度本来就吃紧，你如果还是大常数选手，那得寄上天。（比如我）

因为几道题的值域都较高，所以我用的都是 std::map ，然后就 $\text{T}$ 飞了。（因为每一次扫描的时间从 $\mathcal O(1)$ 上升到了 $\mathcal O(\log n)$）

所以，离散化吧，少年！

这道题因为数据过水其实开数组是过的了的。

AC Code 
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=2e5+10;
const int MAXS=1e6+10;
int N,M,Uni,Mq,Mc;
int Val[MAXN],Cnt[MAXS],ans[MAXN];
struct Que
{
    int id,l,r,t;
    bool operator<(const Que &x) const
    {
        if(l/Uni!=x.l/Uni) return l<x.l;
        if(r/Uni!=x.r/Uni) return r<x.r;
        return t<x.t;
    }
}Q[MAXN];
struct Modify
{
    int p,c;
}Ch[MAXN];
int res;
inline void add(int x)
{
    if(!Cnt[x]) ++res;
    ++Cnt[x];
}
inline void del(int x)
{
    --Cnt[x];
    if(!Cnt[x]) --res;
}
inline void Solve()
{
    std::sort(Q+1,Q+1+Mq);
    for(int i=1,l=2,r=1,t=0;i<=Mq;++i)
    {
        auto q=Q[i];
        while(l>q.l) add(Val[--l]);
        while(r<q.r) add(Val[++r]);
        while(l<q.l) del(Val[l++]);
        while(r>q.r) del(Val[r--]);
        while(t<q.t)
        {
            ++t;
            if(Ch[t].p>=l&&Ch[t].p<=r)
            {
                del(Val[Ch[t].p]);
                add(Ch[t].c);
            }
            std::swap(Val[Ch[t].p],Ch[t].c);
        }
        while(t>q.t)
        {
            if(Ch[t].p>=l&&Ch[t].p<=r)
            {
                del(Val[Ch[t].p]);
                add(Ch[t].c);
            }
            std::swap(Val[Ch[t].p],Ch[t].c);
            --t;
        }
        ans[q.id]=res;
    }
}
int main()
{
    // freopen("modify-mo-algo.in","r",stdin);
    // freopen("modify-mo-algo.out","w",stdout);
    read(N,M);
    for(int i=1;i<=N;++i) read(Val[i]);
    for(int i=1;i<=M;++i)
    {
        char opt[2];
        int a,b;
        scanf("%s",opt+1);
        read(a,b);
        if(opt[1]=='Q') Q[++Mq]={Mq,a,b,Mc};
        else Ch[++Mc]={a,b};
    }
    Uni=std::pow((double)N,2.0/3);
    Solve();
    for(int i=1;i<=Mq;++i) write(ans[i]),puts("");
    return 0;
}
/*
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
*/

P2464

《std::map ，然后 $\text{T}$ 飞》。

果然还是离散化更好，结果因为巨大的常数以及莫队的玄学时间复杂度，然后还是 $\text{T}$ 了一个点，还好吸氧过了。

AC Code 
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=4e5+10;
int N,M,Uni,Mq,Mc;
int Val[MAXN],ans[MAXN],Cnt[MAXN];
struct Que
{
    int id,l,r,t,k;
    bool operator<(const Que &x) const
    {
        if(l/Uni!=x.l/Uni) return l<x.l;
        if(r/Uni!=x.r/Uni) return r<x.r;
        return t<x.t;
    }
}Q[MAXN];
struct Modify
{
    int p,c;
}Ch[MAXN];
std::vector<int>Nums;
inline void Solve()
{
    std::sort(Q+1,Q+1+Mq);
    for(int i=1,l=2,r=1,t=0;i<=Mq;++i)
    {
        auto q=Q[i];
        while(l>q.l) ++Cnt[Val[--l]];
        while(r<q.r) ++Cnt[Val[++r]];
        while(l<q.l) --Cnt[Val[l++]];
        while(r>q.r) --Cnt[Val[r--]];
        while(t<q.t)
        {
            ++t;
            if(Ch[t].p>=l&&Ch[t].p<=r)
            {
                --Cnt[Val[Ch[t].p]];
                ++Cnt[Ch[t].c];
            }
            std::swap(Val[Ch[t].p],Ch[t].c);
        }
        while(t>q.t)
        {
            if(Ch[t].p>=l&&Ch[t].p<=r)
            {
                --Cnt[Val[Ch[t].p]];
                ++Cnt[Ch[t].c];
            }
            std::swap(Val[Ch[t].p],Ch[t].c);
            --t;
        }
        ans[q.id]=Cnt[q.k];
    }
}
int main()
{
    // freopen("modify-mo-algo.in","r",stdin);
    // freopen("modify-mo-algo.out","w",stdout);
    read(N,M);
    for(int i=1;i<=N;++i)
    {
        read(Val[i]);
        Nums.push_back(Val[i]);
    }
    for(int i=1;i<=M;++i)
    {
        char opt[2];
        int a,b;
        scanf("%s",opt);
        read(a,b);
        if(opt[0]=='Q')
        {
            int k;read(k);
            Q[++Mq]={Mq,a,b,Mc,k};
            Nums.push_back(k);
        }
        else
        {
            Ch[++Mc]={a,b};
            Nums.push_back(b);
        }
    }
    Uni=std::pow((double)N,2.0/3);
    std::sort(Nums.begin(),Nums.end());
    Nums.erase(std::unique(Nums.begin(),Nums.end()),Nums.end());
    for(int i=1;i<=N;++i)
        Val[i]=std::lower_bound(Nums.begin(),Nums.end(),Val[i])-Nums.begin();
    for(int i=1;i<=Mc;++i)
        Ch[i].c=std::lower_bound(Nums.begin(),Nums.end(),Ch[i].c)-Nums.begin(); 
    for(int i=1;i<=Mq;++i)
        Q[i].k=std::lower_bound(Nums.begin(),Nums.end(),Q[i].k)-Nums.begin(); 
    Solve();
    for(int i=1;i<=Mq;++i) write(ans[i]),puts("");
    return 0;
}
/*
5 5
1 2 3 4 5
Q 1 3 2
Q 1 3 1
C 2 1
Q 1 3 2
Q 1 3 1
*/

回滚莫队

也可以叫做不删除莫队。

对于一类问题，如果用莫队来做的话，虽然拓展添加答案时很容易，但可能会出现收缩删除时的答案难以在 $\mathcal O(1)$ 内更新。那么我们就需要换一种方法来更新莫队。

分析

不变的是，我们应该依然以 $l$ 的块编号，$r$ 的单调为一二关键字排序。

回滚莫队分为可添加不删除莫队和可删除不添加莫队两种，实现方式大同小异。

其实现方式在于使用回滚来代替无法实现的操作，时间复杂度为 $\mathcal O(n\sqrt m)$ 。

可以证明，当块长为 $b$ 时，时间复杂度为 $\mathcal O(mb+\frac{n^2}{b})$ ，所以，当 $b=\frac{n}{\sqrt m}$ 时，时间复杂度期望为 $\mathcal O(n\sqrt m)$ 。

实现

如上述所言，对询问区间 $[l,r]$ ，以 $l$ 所在的块编号为第一关键字，$r$ 升序为第二关键字排序。

然后按顺序处理询问：（设当前询问为 $[l,r]$ ，$l$ 所属块为 $B$）

  1. 如果当前询问的 $l$ 所属块与上一个询问不同，则将 $l$ 赋值为 $Nxt[B]+1$ ，即下一个块的左端点，并将 $r$ 赋值为 $Nxt[B]$ ，使其交错。
  2. 如果 $Bel[l]=Bel[r]$ ，则暴力扫描，可以知道此时的时间复杂度不超过 $\mathcal O(\frac{n}{\sqrt m})$ 。
  3. 如果 $Bel[l]\neq Bel[r]$ ，则：
    • 如果 $r>q.r$ ，则扩展右端点直到 $r=q.r$ ；
    • 扩展 $l$ 直到 $l=q.l$ ；
    • 统计答案；
    • 撤销左端点改动，回滚至 $l=Nxt[B]+1$ 。

这里就已经说的很明白了，所谓的回滚操作，就是撤销 $l$ 的拓展。

直接令改动之前的答案为 $backup$ ，再统计完之后再把 $res$ 赋回 $backup$ 。

例题

AT1219

因为有 $v_{i}=cnt[i]\times i$ ，所以，每次拓展时就直接计算就好了。

AC Code 
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
121
122
123
124
125
126
127
128
129
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
#define int long long
const int MAXN=1e5+10;
int N,M,Uni;
ll Val[MAXN],ans[MAXN],Cnt[MAXN];
struct Que
{
    int id,l,r;
    bool operator<(const Que&x) const
    {
        if(l/Uni!=x.l/Uni) return l<x.l;
        return r<x.r;
    }
}query[MAXN];
std::vector<int>Nums;
inline void add(int pos,ll &res)
{
    ++Cnt[pos];
    res=std::max(res,1ll*Cnt[pos]*Nums[pos]);
}
inline int get(int x)
{
    return x/Uni;
}
inline void Solve()
{
    std::sort(query,query+M);
    for(int i=0;i<M;)
    {
        int j=i;
        while(j<M&&get(query[j].l)==get(query[i].l)) ++j;
        int right=get(query[i].l)*Uni+Uni-1;
        while(i<j&&query[i].r<=right)
        {
            ll res=0;
            auto q=query[i];
            for(int k=q.l;k<=q.r;++k) add(Val[k],res);
            ans[q.id]=res;
            for(int k=q.l;k<=q.r;++k) --Cnt[Val[k]];
            ++i;
        }
        ll res=0;
        int l=right,r=right+1;
        while(i<j)
        {
            auto q=query[i];
            while(l<q.r) add(Val[++l],res);
            ll backup=res;
            while(r>q.l) add(Val[--r],res);
            ans[q.id]=res;
            while(r<right+1) --Cnt[Val[r++]];
            res=backup;
            ++i;
        }
        memset(Cnt,0,sizeof(Cnt));
    }
}
signed main()
{
    // freopen("back-mo-algo.in","r",stdin);
    // freopen("back-mo-algo.out","w",stdout);
    read(N,M);
    Uni=std::sqrt(N);
    for(int i=1;i<=N;++i) read(Val[i]),Nums.push_back(Val[i]);
    std::sort(Nums.begin(),Nums.end());
    Nums.erase(std::unique(Nums.begin(),Nums.end()),Nums.end());
    for(int i=1;i<=N;++i) Val[i]=std::lower_bound(Nums.begin(),Nums.end(),Val[i])-Nums.begin();
    for(int i=0;i<M;++i)
    {
        read(query[i].l,query[i].r);
        query[i].id=i;
    }
    Solve();
    for(int i=0;i<M;++i) write(ans[i]),puts("");
    return 0;
}
/*
8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8
*/

P5906

对于这道题而言，除非我们记录每一个数第二次出现的位置，否则删除操作会十分麻烦，而且我们也不知道当前的 $res$ 是否与我们删除的数有关，所以考虑回滚莫队。

记录每一个数第一次出现的位置为 $St[x]$ 和最后一次出现的位置 $Nxt[x]$ 。

根据块编号计算答案，通过块编号单增。

对于询问 $[l,r]$ 在同一块中时，直接暴力统计答案；

如果当前左端点比上一个询问的左端点大，直接在上一次的基础上统计答案。否则回滚，重新从 $l=Nxt[B]+1,r=Nxt[B]$ 统计。

需要注意的是，回滚莫队并不能使用奇偶性优化，且部分的回滚莫队会得到 $q.id>M$ 的情况，此时，在本地评测的时候，并不会出现任何问题，但是，提交上之后就会玄学 $\text{WA}$ 掉，而不是因为数组越界而 $\text{RE}$ ，所以，在询问的时候，不嫌麻烦的话，可以尽量多地加上边界。

在此，感谢帮我调了一个晚上 $+$ 一个上午的 $\text{LuckyLeaves}$ 巨佬和调了一个下午帮我找出错误的分块之神 $\text{Dyd}$ 。

AC Code 
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<assert.h>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+48);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=2e5+100,Uni=320;
int N,M,Val[MAXN],Cnt;
int Lst[MAXN],Nxt[MAXN],ans[MAXN],St[MAXN];
inline int get(int x)
{
    return (x/Uni)+1;
}
struct query
{
    int l,r,id;
    bool operator<(const query &x) const
    {
        if(get(l)!=get(x.l)) return l<x.l;
        return r<x.r;
    }
}Q[MAXN];
int Ch[MAXN],Tot,Nums[MAXN];
inline int calc(int l,int r)
{
    // assert(l >= 1 && l <= r && r <= N);
    int res=0;
    for(int i=l;i<=r;++i) Lst[Val[i]]=0;
    for(int i=l;i<=r;++i)
        if(!Lst[Val[i]]) Lst[Val[i]]=i;
        else res=std::max(res,i-Lst[Val[i]]);
    return res;
}
inline void Solve()
{
    std::sort(Q+1,Q+1+M);
    for(int i=1,j=1;j<=Cnt;++j)
    {
        int br=std::min(N,j*Uni),l=br+1,r=l-1,res=0;
        Tot=0;
        for(;i<=M&&get(Q[i].l)==j;++i)
        {
            auto q=Q[i];
            /*if (q.id == 0)
            {
                std::cerr << q.l << " " << q.r << "\n";
                std::cerr << i << "\n";
                exit(0);
            }*/
            if(get(q.r)==j)
            {
                ans[q.id]=calc(q.l,q.r);
                continue;
            }
            while(r<q.r)
            {
                ++r;Nxt[Val[r]]=r;
                if(!St[Val[r]]) St[Val[r]]=r,Ch[++Tot]=Val[r];
                res=std::max(res,r-St[Val[r]]);
            }
            int backup=res;
            while(l>q.l)
            {
                --l;
                if(Nxt[Val[l]]) res=std::max(res,Nxt[Val[l]]-l);
                else Nxt[Val[l]]=l;
            }
            ans[q.id]=res;
            // if (q.id == 1) std::cout << res << "\n";
            while(l<=br)
            {
                if(Nxt[Val[l]]==l) Nxt[Val[l]]=0;
                ++l;
            }
            res=backup;
        }
        for(int i=1;i<=Tot;++i) Nxt[Ch[i]]=St[Ch[i]]=0;
    }
}
int main()
{
    // freopen("backup_mo_algo.in","r",stdin);
    // freopen("backup_mo_algo.out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i) read(Val[i]),Nums[i]=Val[i];
    std::sort(Nums+1,Nums+1+N);
    int len=std::unique(Nums+1,Nums+1+N)-Nums-1;
    for(int i=1;i<=N;++i) Val[i]=std::lower_bound(Nums+1,Nums+1+len,Val[i])-Nums;
    // for (int i = 1; i <= N; ++i) assert(Val[i] > 0 && Val[i] <= N);
    read(M);
    // exit(0);
    // Uni=std::sqrt(N);
    Cnt=(N-1)/Uni+1;
    for(int i=1;i<=M;++i)
    {
        read(Q[i].l,Q[i].r);
        Q[i].id=i;
    }
    Solve();
    for(int i=1;i<=M;++i) write(ans[i]),puts("");
    return 0;
}
/*
8
1 6 2 2 3 3 1 6
5
1 4
2 5
2 8
5 6
1 7
*/

树上莫队

顾名思义，莫队算法在树型结构上的应用。

欧拉序列

树上莫队的实现基于一种思考：将树上问题转换成区间问题，即将树转换为一个序列。这里的序列指的就是欧拉序列。

欧拉序列是一种树的序列表示法，对于一棵有 $n$ 个结点的树，它的欧拉序列的长度为 $2n$ 。

欧拉序列的构造在于：对整棵树进行 $\text{dfs}$ ，每遍历到一个结点就将其加入到序列中，当这个结点的所有边都遍历完之后，再将该结点加入序列。所以，在欧拉序列中，每一个结点会出现两次。

有性质：

  1. 记录第 $u$ 个结点两次出现的位置为 $fir_u,lst_u$ ，则区间 $[fir_u,lst_u]$ 属于 $u$ 的子树。
  2. 如果 $fir_u=lst_u+1$ ，则 $u$ 是叶结点。
  3. 如果 $fir_u=1,lst_u=2n$ ，则 $u$ 为根结点。

欧拉序列查找 LCA

这里令两个点 $x,y$ ，满足 $fir_x<fir_y$ 。

当 $lca(x,y)=x$ 时，则区间内 $[fir_x,fir_y]$ 中只出现过一次的结点在路径 $(x,y)$ 上。
当 $lca(x,y)=y$ 时同理。

操作

那么，在将整棵树转换为欧拉序列之后，如何进行添加和删除操作就是关键所在。

我们用 $cnt[u]$ 表示 $u$ 结点出现了奇数次还是偶数次。每一次进行 cnt[u]^=1 即可。

如果 $u$ 出现了偶数次，说明 $u$ 不在路径上，则不统计答案，否则统计答案。

然后最后特判其 $\operatorname{lca}$ 即可。

例题

SP10707

给出询问路径 $(u,v)$ ，求出该路径内不同权值的个数。

不考虑树的话，这就是个莫队的板子。
然后考虑了树的话，这就是树上莫队的板子。

将整道题分为五步：

  1. 权值离散化，时间复杂度 $\mathcal O(n\log n)$ ；
  2. 求欧拉序列，时间复杂度 $\mathcal O(n)$ ；
  3. 求 $\operatorname{lca}$ ，时间复杂度 $\mathcal O(\log n)$ ；
  4. 将树上询问转换成区间询问，时间复杂度 $\mathcal O(m)$ ；
  5. 使用莫队统计答案，时间复杂度 $\mathcal O(n\sqrt n)$ 。

因为有欧拉序这个特殊的条件存在，所以，在 add() 中，既充当了原来 add 的作用，也有 del() 的作用。

而实际上，我们是在树型结构上进行分块操作，所以一般块长开 $\sqrt{2n}$ 左右即可。（也好像可以取到 $n^{0.6}$）

AC Code 
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include<bits/stdc++.h>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=1e5+10;
std::vector<int>Nums;
int N,M,Uni,Val[MAXN];
struct G
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline int get(int x)
{
    return x/Uni;
}
struct query
{
    int id,l,r,ex;
    bool operator<(const query &x) const
    {
        if(get(l)==get(x.l)) return r<x.r;
        return l<x.l;
    }
}Q[MAXN];
inline void addEdge(int u,int v)
{
    Edge[++Total]=(G){Head[u],v};Head[u]=Total;
    Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Fa[MAXN],Son[MAXN],Dep[MAXN],Siz[MAXN];
void dfsTree(int x,int last)
{
    Fa[x]=last,Siz[x]=1,Dep[x]=Dep[last]+1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Siz[x]+=Siz[v];
        if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
    }
}
int Top[MAXN];
void dfsChain(int x,int topf)
{
    Top[x]=topf;
    if(!Son[x]) return ;
    dfsChain(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
        dfsChain(v,v);
    }
}
inline int getLca(int x,int y)
{
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
        x=Fa[Top[x]];
    }
    return Dep[x]>Dep[y]?y:x;
}
int Seq[MAXN],Tot,Fir[MAXN],Lst[MAXN];
void dfsSeq(int x,int last)
{
    Seq[++Tot]=x;
    Fir[x]=Tot;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsSeq(v,x);
    }
    Seq[++Tot]=x;
    Lst[x]=Tot;
}
int Cnt[MAXN],St[MAXN],ans[MAXN],res;
inline void add(int pos)
{
    St[pos]^=1;
    if(!St[pos])
    {
        --Cnt[Val[pos]];
        if(!Cnt[Val[pos]]) --res;
    }
    else
    {
        if(!Cnt[Val[pos]]) ++res;
        ++Cnt[Val[pos]];
    }
}
inline void solve()
{
    std::sort(Q+1,Q+1+M);
    for(int i=1,l=1,r=0;i<=M;++i)
    {
        auto q=Q[i];
        while(r<q.r) add(Seq[++r]);
        while(r>q.r) add(Seq[r--]);
        while(l<q.l) add(Seq[l++]);
        while(l>q.l) add(Seq[--l]);
        if(q.ex) add(q.ex);
        ans[q.id]=res;
        if(q.ex) add(q.ex);
    }
}
int main()
{
    // freopen("tree-mo-algo.in","r",stdin);
    // freopen("tree-mo-algo.out","w",stdout);
    read(N,M);
    for(int i=1;i<=N;++i) read(Val[i]),Nums.push_back(Val[i]);
    std::sort(Nums.begin(),Nums.end());
    Nums.erase(std::unique(Nums.begin(),Nums.end()),Nums.end());
    for(int i=1;i<=N;++i) Val[i]=std::lower_bound(Nums.begin(),Nums.end(),Val[i])-Nums.begin();
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);addEdge(u,v);
    }
    dfsSeq(1,-1),dfsTree(1,0),dfsChain(1,1);
    for(int i=1,u,v;i<=M;++i)
    {
        read(u,v);
        if(Fir[u]>Fir[v]) std::swap(u,v);
        int ex=getLca(u,v);
        if(u==ex) Q[i]=(query){i,Fir[u],Fir[v],0};
        else Q[i]=(query){i,Lst[u],Fir[v],ex};
    }
    Uni=std::sqrt(Tot);
    solve();
    for(int i=1;i<=M;++i) write(ans[i],'\n');
    return 0;
}
/*
8 2
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5
7 8
*/

WC2013 糖果公园

树上带修莫队，又是一个套娃的集大成者。

每一次的贡献为 $Val[Cnt[Col[x]]]*V[Col[x]]$ 。然后用欧拉序列维护，并记录每一次修改的时间戳，然后按照带修莫队的思路维护三维询问，左端点为第一关键字，右端点为第二关键字，时间戳为第三关键字。然后按照树上莫队的方式来计算即可。

总之就是，就像是教了你番茄炒蛋，教了你土豆烧肉，教了你炖汤，教了你凉拌黄瓜，然后让你炖一锅番茄蛋烧凉拌土豆黄瓜烧肉汤一样。

每一个部分都会的话，打代码慢一点，把每一个部分都想好，然后最后组合一下就好了。

AC Code 
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
#include<bits/stdc++.h>
#define gh() getchar()
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s) putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
const int MAXN=2e5+10;
int N,M,Q,Uni,Val[MAXN],Col[MAXN],V[MAXN];
struct G
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline int get(int x)
{
    return (x/Uni)+1;
}
int cnt1,cnt2,Cc[MAXN];
struct query
{
    int l,r,t,ex,id;
    bool operator<(const query &x) const
    {
        if(get(l)!=get(x.l)) return l<x.l;
        if(get(r)!=get(x.r)) return r<x.r;
        return t<x.t;
    }
}Qe[MAXN];
inline void addEdge(int u,int v)
{
    Edge[++Total]=(G){Head[u],v};Head[u]=Total;
    Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Fa[MAXN],Son[MAXN],Dep[MAXN],Siz[MAXN];
void dfsTree(int x,int last)
{
    Fa[x]=last,Siz[x]=1,Dep[x]=Dep[last]+1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Siz[x]+=Siz[v];
        if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
    }
}
int Top[MAXN];
void dfsChain(int x,int topf)
{
    Top[x]=topf;
    if(!Son[x]) return ;
    dfsChain(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
        dfsChain(v,v);
    }
}
inline int getLca(int x,int y)
{
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
        x=Fa[Top[x]];
    }
    return Dep[x]>Dep[y]?y:x;
}
int Seq[MAXN],Idx,Fir[MAXN],Lst[MAXN];
int pos[MAXN],pre[MAXN],then[MAXN];
void dfsSeq(int x,int last)
{
    Seq[++Idx]=x;
    Fir[x]=Idx;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsSeq(v,x);
    }
    Seq[++Idx]=x;
    Lst[x]=Idx;
}
int Cnt[MAXN],St[MAXN];
ll ans[MAXN],res;
inline void add(int x)
{
    if(St[x]==1)
    {
        res-=1ll*Val[Cnt[Col[x]]]*V[Col[x]];
        --Cnt[Col[x]];
    }
    else
    {
        ++Cnt[Col[x]];
        res+=1ll*Val[Cnt[Col[x]]]*V[Col[x]];
    }
    ++St[x];
}
inline void del(int x)
{
    if(St[x]==2)
    {
        ++Cnt[Col[x]];
        res+=1ll*Val[Cnt[Col[x]]]*V[Col[x]];
    }
    else
    {
        res-=1ll*Val[Cnt[Col[x]]]*V[Col[x]];
        --Cnt[Col[x]];
    }
    --St[x];
}
int Tot,T;
inline void solve()
{
    std::sort(Qe+1,Qe+1+Tot);
    for(int i=1,l=1,r=0,t=0;i<=Tot;++i)
    {
        auto q=Qe[i];
        while(t>q.t)
        {
            if(St[pos[t]]&1)
            {
                del(pos[t]);
                Col[pos[t]]=pre[t];
                add(pos[t]);
            }
            else Col[pos[t]]=pre[t];
            --t;
        }
        while(t<q.t)
        {
            ++t;
            if(St[pos[t]]&1)
            {
                del(pos[t]);
                Col[pos[t]]=then[t];
                add(pos[t]);
            }
            else Col[pos[t]]=then[t];
        }
        while(l>q.l) add(Seq[--l]);
        while(r<q.r) add(Seq[++r]);
        while(l<q.l) del(Seq[l++]);
        while(r>q.r) del(Seq[r--]);
        ans[q.id]=res;
        if(q.ex) ans[q.id]+=1ll*Val[Cnt[Col[q.ex]]+1]*V[Col[q.ex]];
    }
}
int main()
{
    // freopen("tree-modify-mo-algo.in","r",stdin);
    // freopen("tree-modify-mo-algo.out","w",stdout);
    read(N,M,Q);
    for(int i=1;i<=M;++i) read(V[i]);
    for(int i=1;i<=N;++i) read(Val[i]);
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);addEdge(u,v);
    }
    dfsTree(1,0),dfsChain(1,1);
    dfsSeq(1,-1);
    for(int i=1;i<=N;++i) read(Col[i]),Cc[i]=Col[i];
    for(int i=1,opt,x,y;i<=Q;++i)
    {
        read(opt,x,y);
        if(opt==1)
        {
            int lca=getLca(x,y);
            Qe[++Tot].t=T;
            Qe[Tot].id=Tot;
            if(Fir[x]>Fir[y]) std::swap(x,y);
            if(lca==x) Qe[Tot].l=Fir[x],Qe[Tot].r=Fir[y];
            else Qe[Tot].l=Lst[x],Qe[Tot].r=Fir[y],Qe[Tot].ex=lca;
        }
        else
        {
            ++T;
            pos[T]=x,pre[T]=Cc[x];
            Cc[x]=then[T]=y;
        }
    }
    Uni=std::sqrt(Idx);
    solve();
    for(int i=1;i<=Tot;++i) write(ans[i],'\n');
    return 0; 
}
/*
4 3 5
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 1 2
1 4 2
0 2 1
1 1 2
1 4 2
*/

莫队二次离线

在太阳西斜的这个世界里，置身天上之森。等这场战争结束之后，不归之人与望眼欲穿的众人， 人人本着正义之名，长存不灭的过去、逐渐消逝的未来。我回来了，纵使日薄西山，即便看不到未来，此时此刻的光辉，盼君勿忘。

真的不得不佩服 $\text{lxl}$ 这个人，虽然是我竞争学校（指 $\text{cdqz}$）的一位巨佬，但是，总还是不自觉地就敬佩上了这个人。

他攀到了我永远都无法触及的地方，然后不断地创造我所需要的东西来协助我攀登。当我以为我已经登峰造极之时，会有一座更巍峨的山峰重新屹立在我的眼前。我会重走他们走过的每一条路，或许会倒在他们曾跨过的地方，但，死去的我，也会为下一个走到这里的人竖起丰碑。并不是在历史上刻录的姓名的人才会伟大，每一个走到这里的人，同样伟大。在这里的人，都会在不久的将来，在某一个闲谈的下午茶时光，骄傲地说出：“我，曾经也是一位 $\mathcal{OIer}$ 。”，正因如此，每一位 $\mathcal{OIer}$ 都值得敬佩。

在暮色重现的这个世界里，忘我海蓝之外，等这段使命结束之后，天选之人与逆火而生的新我，众人迎着孤泪赴冢，淡忘毋朽的回忆，砌筑绝望的轮回。我回来了，纵使繁花落尽，即便望不到未来，此时此刻的落日，盼君勿忘。

内容

在有些时候，执行 add() 和 del() 的时候时间复杂度可能并不是 $\mathcal O(1)$ ，而是一个变量，会使莫队算法的时间复杂度大大升高，因为这样计算的话，如果移动一次指针的时间复杂度为 $\mathcal O(k)$ ，那么，普通莫队算法的时间复杂度就会高达 $\mathcal O(nk\sqrt m)$ ，所以会考虑优化。

当 $f(x,l,r)$ ，即 $x$ 对区间 $[l,r]$ 贡献满足以下条件：

  • $f(x,l,r)$ 只与区间 $[l,r]$ 内的元素有关；
  • $f(x,l,r)=f(x,1,r)-f(x,1,l-1)$ ，即满足差分性质。

时，可以考虑莫队二次离线，可以优化到 $\mathcal O(nk+n\sqrt m)$ 。

实现

相关文章