Don't let your dreams be dreams.

WELCOME——一只蒟蒻的幻想

| 笔记, 主席树, 坑, 题解

一道题目引发的惨案

这是一个因为插比利而发生的惨案，进而引出了一堆坑。_(:з」∠)_

一切罪恶的根源啊呸没有罪恶BZOJ3236
事情是怎么样发生的呢。。。当时我听到比利和qiancl在讨论3236，大概的题目是一个序列，求l，r间属于[a,b]的颜色种数。当时我这道题目是用莫队套分块过去的，复杂度是$O(N\cdot \sqrt{N})$的。然后这道题目想一想应该是可以用树套树什么的$log^2N$做的，但是时间和编程复杂度不一定比莫队优。

这个时候比利就开始口胡了，说有一只$log$的做法，他说可以把询问区间插成前缀和，排序后就可以一只$log$维护答案了。一听感觉有点道理，但是好像维护的是颜色种类不满足减法，妈的智障。

然后比利又开始口胡，既然拆区间拆不了可以把询问的颜色范围拆成两个，然后前缀和，现在总满足减法了吧。突然感觉好有道理。然后细想询问排序之后的插入还是需要一个数据结构维护，所以复杂度还是两只$log$的。妈的智障，并没有什么区别。

事情还并没有结束，晚自修的时候，比利走过来和我说他在PoPoQQQ的blog上看到了一只$log$的做法，好像是用主席树在线维护区间颜色种类。感觉很高端的样子，一翻BZOJ翻出来一堆类似的题目。(:з」∠)

我看到这些题目的第一反应就是，奥这道题目啊不是莫队吗，奥这个不是带修改莫队吗，奥这道题我好像以前是用莫队水过去的。。(:з」∠)

感觉我数据结构能力缺失得有点严重，还是补一下比较好。

所以上面写了一堆废话，让我们来总结一下这篇博文的主题是什么。

用主席树求区间颜色种类的在线带修改算法。（怎么这么绕呢）

如果不会主席树可以去这里学习。

序幕：离线求不带修改区间颜色种类

例题：1878: [SDOI2009]HH的项链
（很多题解里都提到了这道题的树状数组离线做法，然而我一点印象都没有，后来才发现我写的是莫队，妈的智障）
这道题主要的问题是要求区间的颜色种数，一种颜色只能被计算一次。我们可以对序列预处理一下，处理出每一个点之前的第一个与他相同的点的位置，记为next[i]。然后对于一个区间[l,r]里只出现一次的点，显然满足next<l。
然后我们把询问离线，按照r排序，按照顺序插入节点，树状数组维护next小于l的数量，就可以在log的时间内处理问题了。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 1000010;
using namespace std;
int S[N],val[N],head[N],next[N],n,m,now,ans[N];
struct data{int x,y,id;} q[N];
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
int lowbit(int x){return x&-x;}
int Query(int pos){
	int res = 0;
	for (int i=pos;i;i-=lowbit(i)) res+=S[i];
	return res;
}
void Update(int pos,int val) {for (int i=pos;i<=n+2;i+=lowbit(i)) S[i]+=val;}
bool cmp(data a,data b){return a.y<b.y;}
int main(){
	n = read();
	for (int i=1;i<=n;i++) {
		val[i] = read();
		next[i] = head[val[i]];
		head[val[i]] = i;
	}
	m = read();
	for (int i=1;i<=m;i++) q[i].x = read(),q[i].y = read(),q[i].id = i;
	sort(q+1,q+1+m,cmp);
	for (int i=1;i<=m;i++) {
		while (now<q[i].y) {
			now++;
			Update(next[now]+1,1);
			Update(now+1,-1);
		}
		ans[q[i].id] = Query(q[i].x);
	}
	for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
}

发展：在线求不带修改区间颜色种类

例题：1878: [SDOI2009]HH的项链 （找不到强制在线的模板题了，可以把它当成在线做(:з」∠)）
和上一道题目的想法相似，稍微改变一下next[i]为一个点之后与他相同的点的位置，然后也是可以显然的知道在区间[l,r]之间只出现一次的点的next>r。然后我们可以发现这个东西是满足区间减法的。
于是可以想到用主席树求解。对于第i颗线段树在next[i]的位置+1。这样我们就可以容易地求出1~x中next>y的点的数量（在第x颗线段树上对y+1~n+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
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 100010;
using namespace std;
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
struct Tree{int ls,rs,sum;} tree[3000010];
int next[1000010],head[1000010],val[N],x,y,n,m,treesize,root[N];
void Update(int l,int r,int x,int &y,int val){
	y = ++treesize;tree[y].sum = tree[x].sum+1;
	if (l==r) return;
	int mid = (l+r)>>1;
	tree[y].ls = tree[x].ls;tree[y].rs = tree[x].rs;
	if (val<=mid) Update(l,mid,tree[x].ls,tree[y].ls,val);
	else Update(mid+1,r,tree[x].rs,tree[y].rs,val);
}
int Query(int L,int R,int pos,int l,int r){
	if (L==l && R==r) return tree[pos].sum;
	int mid = (L+R)>>1;
	if (r<=mid) return Query(L,mid,tree[pos].ls,l,r);
	else if (l>mid) return Query(mid+1,R,tree[pos].rs,l,r);
	else return Query(L,mid,tree[pos].ls,l,mid)+Query(mid+1,R,tree[pos].rs,mid+1,r);
}
int main(){
	n = read();
	for (int i=1;i<=n;i++) val[i] = read();
	for (int i=n;i;i--) {
		if (head[val[i]]==0) next[i] = n+1;
		else next[i] = head[val[i]];
		head[val[i]] = i;
	}
	for (int i=1;i<=n;i++) Update(1,n+1,root[i-1],root[i],next[i]);
	m = read();
	for (int i=1;i<=m;i++) {
		x = read();y = read();
		printf("%d\n",Query(1,n+1,root[y],y+1,n+1)-Query(1,n+1,root[x-1],y+1,n+1));
	}
}



一道相似的题目BZOJ4026: dC Loves Number Theory
题面是求一段区间内数乘积的$\varphi$，考虑$\varphi$的值，设$n=p_1^{q_1}\cdot p_2^{q_2}\ldots p_k^{q_k}$,$\varphi(n)=n\cdot \Pi_{i=1}^{k} \frac {p_i-1}{p_i}$
我们发现只与不相同的素数有关，就转化成了求一段区间内的不相同素数的$\frac {p_i-1}{p_i}$的值的积了。因为是对1e6+777取模，所以数的范围很小，可以直接暴力分解质因数，然后类似上一题的用主席树维护。（注意因为这个是乘积，所以要初始化第一棵树）。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
const int RXD = 1e6+777;
const int N = 1000010;
using namespace std;
int inv[RXD+10],prime[RXD+10],vis[RXD+10],a[N],S[N],A[N],L[N],R[N],n,m,treesize,cnt,l,r,ans,last,tot,head[N],next[N],root[N];
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
struct Tree{int ls,rs,val;} tree[5000010];
void Prep(){
	inv[0] = inv[1] = 1;
	for (int i=2;i<=RXD;i++) inv[i] = ((1ll*RXD-RXD/i)*inv[RXD%i]+RXD)%RXD;
	for (int i=2;i<=RXD;i++){
		if (!vis[i]) prime[++tot] = i;
		for (int j=1;j<=tot && prime[j]*i<=RXD;j++) {
			vis[prime[j]*i] = 1;
			if (i%prime[j]==0) break;
		}
	}
}
void Build(int pos,int l,int r){
	tree[pos].val = 1;if (l==r) return; int mid = (l+r)>>1;
	tree[pos].ls = ++treesize;tree[pos].rs = ++treesize;
	Build(tree[pos].ls,l,mid);Build(tree[pos].rs,mid+1,r);
}
void Update(int l,int r,int x,int &y,int val,int w){
	y = ++treesize;
	tree[y].val = 1ll*tree[x].val*(w-1)%RXD*inv[w]%RXD;
	if (l==r) return;
	int mid = (l+r)>>1; 
	tree[y].ls = tree[x].ls;tree[y].rs = tree[x].rs;
	if (val<=mid) Update(l,mid,tree[x].ls,tree[y].ls,val,w);
	else Update(mid+1,r,tree[x].rs,tree[y].rs,val,w);
}
int Query(int L,int R,int pos,int l,int r){
	if (L==l && R==r) return tree[pos].val;
	int mid = (L+R)>>1;
	if (r<=mid) return Query(L,mid,tree[pos].ls,l,r);
	else if (l>mid) return Query(mid+1,R,tree[pos].rs,l,r);
	else return 1ll*Query(L,mid,tree[pos].ls,l,mid)*Query(mid+1,R,tree[pos].rs,mid+1,r)%RXD;
}
int main(){
	n = read();m = read();Prep();S[0] = 1;
	for (int i=1;i<=n;i++) A[i] = read(),S[i] = (1ll*S[i-1]*A[i])%RXD;
	for (int i=1;i<=n;i++) {
		L[i] = cnt+1;int x = A[i];
		for (int j=1;j<=tot && prime[j]*prime[j]<=x;j++)
			if (x%prime[j]==0) {a[++cnt] = prime[j];while (x%prime[j]==0) x/=prime[j];}
		if (x!=1) a[++cnt] = x;
		R[i] = cnt;
	}
	n = cnt;
	for (int i=n;i;i--) {
		if (head[a[i]]==0) next[i] = n+1;
		else next[i] = head[a[i]];
		head[a[i]] = i;
	}
	treesize = 1;root[0] = 1;
	Build(1,1,n+1);
	for (int i=1;i<=n;i++) Update(1,n+1,root[i-1],root[i],next[i],a[i]);
	for (int i=1;i<=m;i++){
		int l = read()^last,r = read()^last;
		ans = 1ll*S[r]*inv[S[l-1]]%RXD;
		l = L[l];r = R[r];
		last=(1ll*ans*Query(1,n+1,root[r],r+1,n+1)%RXD*inv[Query(1,n+1,root[l-1],r+1,n+1)]%RXD);
		printf("%d\n",last);
	}
}

高潮：在线求带修改区间颜色种数

例题：2120: 数颜色
推广到带修改的问题上的方法和一般的主席树一样，主要使用主席树前缀相减的思想，用树状数组套权值线段树。每次询问的时候就在树状数组节点的线段树上询问，然后合并答案。修改需要修改所有包含该节点的线段树。因为这道题权值位置是在next的位置上，所以还需要记录前驱后继，可以直接用一个set维护信息。

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
#define N 20010
#define M 800010
set <int> col[N];
set <int> :: iterator it;
struct xy{int x,y;char ctrl[3];}q[N];
int a[N],san[N],next[N],v[N],pre[N],c[N],L[N],R[N],root[N];
int ls[M],rs[M],sum[M];
int n,m,ne,cnt,tot,numa,numb;
char ch;
void read(int &x){
   while (ch = getchar(),ch < '0' || ch > '9');
   x = ch - '0';
   while (ch = getchar(),ch >= '0' && ch <= '9') x = x * 10 + ch - '0';
}
inline void update(int lson,int rson,int x,int k){
   sum[++ tot] = sum[x] + k,ls[tot] = lson,rs[tot] = rson;
}
inline int change(int x,int l,int r,int y,int k){
   if (l == r) {update(0,0,x,k);return tot;}
   int m = l + r >> 1;
   if (y <= m) ne = change(ls[x],l,m,y,k),update(ne,rs[x],x,k);
   else ne = change(rs[x],m + 1,r,y,k),update(ls[x],ne,x,k);
   return tot;
}
inline void bitup(int x,int p,int k){
   for (;x <= n;x += x & -x)
       c[x] = change(c[x],1,n + 1,p,k);
}
int ask(int *a,int numa,int *b,int numb,int k){
   int ans = 0,l = 1,r = n + 1,m;
   while (l < r){
       m = l + r >> 1;
       if (k >= m) {
           for (int i = 0;i < numa;i ++) a[i] = rs[a[i]];
           for (int i = 0;i < numb;i ++) b[i] = rs[b[i]];
           l = m + 1;
       }else{
           for (int i = 0;i < numa;i ++) ans -= sum[rs[a[i]]];
           for (int i = 0;i < numb;i ++) ans += sum[rs[b[i]]];
           for (int i = 0;i < numa;i ++) a[i] = ls[a[i]];
           for (int i = 0;i < numb;i ++) b[i] = ls[b[i]];
           r = m;
       }
   }
   for (int i = 0;i < numa;i ++) ans -= sum[a[i]];
   for (int i = 0;i < numb;i ++) ans += sum[b[i]];
   return ans;
}
int query(int x,int y){
   numa = numb = 0;
   int k = y;
   L[numa ++] = root[x];
   for (;x;x -= x & -x) L[numa ++] = c[x];
   R[numb ++] = root[y];
   for (;y;y -= y & -y) R[numb ++] = c[y];
   return ask(L,numa,R,numb,k);
}
int main(){
   read(n);read(m);
   for (int i = 1;i <= n;i ++) read(a[i]),san[++ cnt] = a[i];
   for (int i = 1;i <= m;i ++){
       scanf("%s",q[i].ctrl);
       read(q[i].x);read(q[i].y);
       if (q[i].ctrl[0] == 'R') san[++ cnt] = q[i].y;
   }
   sort(san + 1,san + 1 + cnt);
   cnt = unique(san + 1,san + 1 + cnt) - san - 1;
   for (int i = 1;i <= n;i ++) a[i] = lower_bound(san + 1,san + 1 + cnt,a[i]) - san;
   for (int i = 1;i <= n;i ++){
       next[i] = n + 1;
       if (!v[a[i]])
           v[a[i]] = i;
       else {
           next[v[a[i]]] = i;
           pre[i] = v[a[i]];
           v[a[i]] = i;
       }
       col[a[i]].insert(i);
   }
   for (int i = 1;i <= n;i ++) root[i] = change(root[i - 1],1,n + 1,next[i],1),c[i] = root[0];
   for (int i = 1;i <= m;i ++){
       if (q[i].ctrl[0] == 'Q')
           printf("%d\n",query(q[i].x - 1,q[i].y));
       else{
           int pos = q[i].x,val = lower_bound(san + 1,san + 1 + cnt,q[i].y) - san;
           if (pre[pos]){
               bitup(pre[pos],pos,-1);
               next[pre[pos]] = next[pos];
               bitup(pre[pos],next[pos],1);
           }
           if (next[pos] < n + 1)
               pre[next[pos]] = pre[pos];
           bitup(pos,next[pos],-1);
           col[a[pos]].erase(pos);
           
           a[pos] = val;
           it = col[val].upper_bound(pos);
           if (*it > pos){
               next[pos] = *it;
               pre[*it] = pos;
           }else next[pos] = n + 1;
           bitup(pos,next[pos],1);
           if (it != col[val].begin()){
               it --;
               bitup(*it,next[*it],-1);
               next[*it] = pos;
               pre[pos] = *it;
               bitup(*it,next[*it],1);
           }else pre[pos] = 0;
           col[val].insert(pos);
       }
   }
   return 0;
}

尾声：回到3236.

搞完了以上一系列题目以后，然我们回到一切罪恶的源泉啊呸没有罪恶3236.可以发现这是一道不带修改的区间颜色种类询问。但是！！这里的颜色有限制！！！所以。还需要一个数据结构维护，复杂度还是两只log的_(:з」∠)_。我们可以得出结论，比利的口胡能力。太强了。
至于这道题目是写根号还是$log^2$呢。

我强力推荐莫队套分块！！
莫队暴力出奇迹
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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int M = 1000010;
const int N = 100010;
struct data{int l,r,a,b,id;} q[M];
int vis[N],s2[N],pos[N],l[N],r[N],n,m,blk,a[N],ans1[M],s1[N],ans2[M];
int read(){
    int x = 0,f = 1,c = getchar();
    while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
    while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
    return x*f;
}
bool cmp(data a,data b){if (pos[a.l]==pos[b.l]) return a.r<b.r;return a.l<b.l;}
void init(){
    n = read();m = read();blk = sqrt(n/2);
    for (int i=1;i<=n;i++){
        a[i] = read();
        pos[i] = (i-1)/blk+1;
        r[pos[i]] = i;
        if (!l[pos[i]]) l[pos[i]] = i;
    }
    for (int i=1;i<=m;i++){
        q[i].l = read();q[i].r = read();
        q[i].a = read();q[i].b = read();
        q[i].id = i;
    }
    sort(q+1,q+1+m,cmp);
}
int Query1(int x,int y){
    int res = 0;
    if (pos[x]==pos[y]){
        for (int i=x;i<=y;i++) if (vis[i]) res+=vis[i];
        return res;
    }
    else {
        for (int i=pos[x]+1;i<pos[y];i++) res+=s1[i];
        for (int i=x;i<=r[pos[x]];i++) if (vis[i]) res+=vis[i];
        for (int i=l[pos[y]];i<=y;i++) if (vis[i]) res+=vis[i];
        return res;
    }
}
int Query2(int x,int y){
    int res = 0;
    if (pos[x]==pos[y]){
        for (int i=x;i<=y;i++) if (vis[i]) res++;
        return res;
    }
    else {
        for (int i=pos[x]+1;i<pos[y];i++) res+=s2[i];
        for (int i=x;i<=r[pos[x]];i++) if (vis[i]) res++;
        for (int i=l[pos[y]];i<=y;i++) if (vis[i]) res++;
        return res;
    }
}
void Add(int x){if (!vis[x]) s2[pos[x]]++;vis[x]++;s1[pos[x]]++;}
void Del(int x){if (vis[x]==1) s2[pos[x]]--;vis[x]--;s1[pos[x]]--;}
void solve(){
    int l = 1,r = 0;
    for (int i=1;i<=m;i++){
        while (r<q[i].r) r++,Add(a[r]);
        while (r>q[i].r) Del(a[r]),r--;
        while (l<q[i].l) Del(a[l]),l++;
        while (l>q[i].l) l--,Add(a[l]);
        ans1[q[i].id] = Query1(q[i].a,q[i].b);
        ans2[q[i].id] = Query2(q[i].a,q[i].b);
    }
}
void write(int x){
    if (x<0) putchar('-'),write(-x);
    if (x>=10) write(x/10);
    putchar(x%10+'0');
}
int main(){
    init();
    solve();
    for (int i=1;i<=m;i++) write(ans1[i]),printf(" "),write(ans2[i]),puts("");
}

后记：通过了这一系列题目的研究我们知道了口胡的危害

有错误请指出$$\mathcal {FIN}$$