CDQ分治 + 树状数组 ---- C. Goodbye Souvenir（三维偏序+思维）

83 阅读 0 评论 55 点赞

我是靠谱客的博主痴情皮卡丘，这篇文章主要介绍CDQ分治 + 树状数组 ---- C. Goodbye Souvenir（三维偏序+思维），现在分享给大家，希望可以做个参考。

题目链接

题目大意：

给定长度为 $n$ 的数组, 定义数字 $X$ 在 $[l, r]$ 内的值为数字 $X$ 在 $[l, r]$ 内最后一次出现位置的下标减去第一次出现位置的下标
给定 $m$ 次询问, 每次询问有三个整数 $a, b, c$ 询问规则如下:
当 $a = 1$ 时, 将数组内第 $b$ 个元素更改为 $c$
当 $a = 2$ 时, 求区间 $[b, c]$ 所有数字的值的和

解题思路：

我有想到CDQ分治，但是不知道怎么转化？
我们对于这种最后一次出现的位置 $-$ 第一次出现的位置,这里面两个线段树都不好维护！！
对于这个我们可以把这个式子拆了考虑拆贡献，把最后一次的下标减去第一次的下标的和拆成每一个点与和它数字相同的上一个点的差的和，也就是 $\sum i - p r e [i]$
那么每次询问就变成了 $sum_{i=l}^{r}i-pre[i](pre[i]leq l)$
现在我们看一下就是 $i > p r e [i] \geq l$ 那么上面的公式可以这么写
$sum_{i=1}^{r}i-pre[i](pre[i]ge l)(ileq r)$
然后我们加上操作的时间戳 $t$ 那么我们看一下这就变成了三维偏序问题了

$t_ileq t_j$
$i \leq r$
$p r e [i] \geq l$
每个偏序的贡献是 $i - p r e [i]$
那么上CDQ分治：

AC code

实现细节

对于查询操作我们变成 $(t, r, l, 0)$
对于初始的点我们变成 $(t, i, p r e [i], i - p r e [i])$
对于修改操作：我们先加入一个时间戳 $(t, i, p r e [i], - (i - p r e [i]))$
然后再加入新的点 $(t, n o w, p r e [n o w], n o w - p r e [n o w])$
这里有很多细节就是你修改一个点，你会影响到4个点
5.1你的后继节点的 $p r e$ 值
5.2你的前驱节点的 $n x t$ 值
5.3就是你修改后的 $n x t$ 和 $p r e$
5.4这里你要对每个点开个 $s e t$ 去维护动态前驱和后继
CDQ的时候可以直接归并排序对于 $p r e$ 的维度，把 $i$ 插到树状数组里面查询
注意答案输出的顺序和位置，因为被重排了要按时间排序后再输出

复制代码

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl 'n'
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 9;
const int maxn = 7e5 + 10;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x) {
   x = 0;char ch = getchar();ll f = 1;
   while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
   while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
   read(first);
   read(args...);
}
int arr[maxn], pre[maxn], nxt[maxn], whp[maxn], whn[maxn];
int n, m;
struct node {
	int tim, l, r;// (t,i,pre[i])
	ll w;//(i-pre[i])
	int op;
	bool operator < (const node & a) const {
		return tim < a.tim;
	}	
}Node[maxn];
int Qnum;
vector<node> backup;
set<int> S[maxn];

void debug() {
	for(int i = 1; i <= n; ++ i)
	cout << arr[i] <<" n"[i==n];
	for(int i = 1; i <= n; ++ i)
	cout << pre[i] << " n"[i==n];
	for(int i = 1; i <= n; ++ i)
    cout << nxt[i] << " n"[i==n];
	cout << endl;
}

//..........................................................
inline void init() {
	read(n,m);
	for(int i = 1; i <= n; ++ i) read(arr[i]), whp[i] = 0, whn[i] = n + 1;
	for(int i = 1; i <= n; ++ i) pre[i] = whp[arr[i]], whp[arr[i]] = i;
	for(int i = n; i >= 1; -- i) nxt[i] = whn[arr[i]], whn[arr[i]] = i;
	for(int i = 1; i <= n; ++ i) {
		if(pre[i]) Node[++Qnum] = (node){Qnum,i,pre[i],i-pre[i],0};
		S[arr[i]].insert(i);
	}
    for(int i = 1; i <= m; ++ i) {
		int op, l, r;
		read(op,l,r);
		if(op == 1) {
			if(pre[l]) nxt[pre[l]] = nxt[l], Node[++Qnum] = (node){Qnum,l,pre[l],-(l-pre[l]),0};
			if(nxt[l]!=n+1) pre[nxt[l]] = pre[l], Node[++Qnum] = (node){Qnum,nxt[l],l,-(nxt[l]-l),0};
			if(nxt[l]!=n+1&&pre[l]) Node[++Qnum] = (node){Qnum,nxt[l],pre[l],nxt[l]-pre[l],0};
			S[arr[l]].erase(l);
			arr[l] = r;
			auto it  = S[arr[l]].lower_bound(l);
			
			if(it != S[arr[l]].end()) nxt[l] = *it, pre[*it] = l;
		    else nxt[l] = n + 1;
			// cout << (*it) << endl;
			if(it != S[arr[l]].begin()) it --,pre[l] = *it, nxt[*it] = l;
			else pre[l] = 0;
		
			if(pre[l]) Node[++Qnum] = (node){Qnum,l,pre[l],l-pre[l],0};
			if(nxt[l]!=n+1) Node[++Qnum] = (node){Qnum,nxt[l],l,nxt[l]-l,0};
			if(nxt[l]!=n+1&&pre[l]) Node[++Qnum] = (node){Qnum,nxt[l],pre[l],-(nxt[l]-pre[l]),0};
			S[arr[l]].insert(l);
			// debug();
		} else Node[++Qnum] = (node){Qnum,r,l,0,1};
	}
}
//..........................................................
struct BIT {
	ll tr[maxn];
	inline void add(int x, int val) {
		while(x < maxn) {
			tr[x] += val;
			x += lowbit(x);
		}
	}
	inline ll sum(int x) {
		ll res = 0;
		while(x) {
			res += tr[x];
			x -= lowbit(x);
		}
		return res;
	}
}sgt;
//..........................................................
void CDQ(int l, int r) {
	if(l == r) return;
	CDQ(l,mid);
	CDQ(mid+1,r);
	int L = l, R = mid+1;
	// 统计【L,mid】对【mid+1,R】里面查询的影响 
	while(L <= mid && R <= r) {
		if(Node[L].r >= Node[R].r) {
			if(!Node[L].op) sgt.add(Node[L].l,Node[L].w);
			backup.push_back(Node[L++]);
		} else {
			if(Node[R].op) Node[R].w += sgt.sum(Node[R].l); 
			backup.push_back(Node[R++]);
		}
	}
	while(L <= mid) {
		if(!Node[L].op) sgt.add(Node[L].l,Node[L].w);
		backup.push_back(Node[L++]);
	}
	while(R <= r) {
		if(Node[R].op) Node[R].w += sgt.sum(Node[R].l);
		backup.push_back(Node[R++]);		
	}
	for(int i = l; i <= mid; ++ i) // 恢复树状数组
	  if(!Node[i].op)  
	    sgt.add(Node[i].l,-Node[i].w);

for(int i = l; i <= r; ++ i)
	  Node[i] = backup[i-l];
	backup.clear();
}

int main() {
	init();
	// for(int i = 1; i <= Qnum; ++ i)
	//   cout << Node[i].tim << " " << Node[i].l << " " << Node[i].r << " " << Node[i].w << " " << Node[i].op << endl;
	CDQ(1,Qnum);
	sort(Node+1,Node+Qnum+1);
	for(int i = 1; i <= Qnum; ++ i)
	  if(Node[i].op)
	    cout << Node[i].w << endl;
	return 0;
}
/*

7 1
1 2 3 1 3 2 1
2 3 6

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
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define Lson rt << 1, l , mid
#define Rson rt << 1|1, mid + 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define log2(a) log(a)/log(2)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define LLF 0x3f3f3f3f3f3f3f3f
#define f first
#define s second
#define endl 'n'
using namespace std;
const int N = 2e6 + 10, mod = 1e9 + 9;
const int maxn = 7e5 + 10;
const long double eps = 1e-5;
const int EPS = 500 * 500;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
template<typename T> void read(T &x) {
   x = 0;char ch = getchar();ll f = 1;
   while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
   while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
   read(first);
   read(args...);
}
int arr[maxn], pre[maxn], nxt[maxn], whp[maxn], whn[maxn];
int n, m;
struct node {
	int tim, l, r;// (t,i,pre[i])
	ll w;//(i-pre[i])
	int op;
	bool operator < (const node & a) const {
		return tim < a.tim;
	}	
}Node[maxn];
int Qnum;
vector<node> backup;
set<int> S[maxn];

void debug() {
	for(int i = 1; i <= n; ++ i)
	cout << arr[i] <<" n"[i==n];
	for(int i = 1; i <= n; ++ i)
	cout << pre[i] << " n"[i==n];
	for(int i = 1; i <= n; ++ i)
    cout << nxt[i] << " n"[i==n];
	cout << endl;
}

//..........................................................
inline void init() {
	read(n,m);
	for(int i = 1; i <= n; ++ i) read(arr[i]), whp[i] = 0, whn[i] = n + 1;
	for(int i = 1; i <= n; ++ i) pre[i] = whp[arr[i]], whp[arr[i]] = i;
	for(int i = n; i >= 1; -- i) nxt[i] = whn[arr[i]], whn[arr[i]] = i;
	for(int i = 1; i <= n; ++ i) {
		if(pre[i]) Node[++Qnum] = (node){Qnum,i,pre[i],i-pre[i],0};
		S[arr[i]].insert(i);
	}
    for(int i = 1; i <= m; ++ i) {
		int op, l, r;
		read(op,l,r);
		if(op == 1) {
			if(pre[l]) nxt[pre[l]] = nxt[l], Node[++Qnum] = (node){Qnum,l,pre[l],-(l-pre[l]),0};
			if(nxt[l]!=n+1) pre[nxt[l]] = pre[l], Node[++Qnum] = (node){Qnum,nxt[l],l,-(nxt[l]-l),0};
			if(nxt[l]!=n+1&&pre[l]) Node[++Qnum] = (node){Qnum,nxt[l],pre[l],nxt[l]-pre[l],0};
			S[arr[l]].erase(l);
			arr[l] = r;
			auto it  = S[arr[l]].lower_bound(l);
			
			if(it != S[arr[l]].end()) nxt[l] = *it, pre[*it] = l;
		    else nxt[l] = n + 1;
			// cout << (*it) << endl;
			if(it != S[arr[l]].begin()) it --,pre[l] = *it, nxt[*it] = l;
			else pre[l] = 0;
		
			if(pre[l]) Node[++Qnum] = (node){Qnum,l,pre[l],l-pre[l],0};
			if(nxt[l]!=n+1) Node[++Qnum] = (node){Qnum,nxt[l],l,nxt[l]-l,0};
			if(nxt[l]!=n+1&&pre[l]) Node[++Qnum] = (node){Qnum,nxt[l],pre[l],-(nxt[l]-pre[l]),0};
			S[arr[l]].insert(l);
			// debug();
		} else Node[++Qnum] = (node){Qnum,r,l,0,1};
	}
}
//..........................................................
struct BIT {
	ll tr[maxn];
	inline void add(int x, int val) {
		while(x < maxn) {
			tr[x] += val;
			x += lowbit(x);
		}
	}
	inline ll sum(int x) {
		ll res = 0;
		while(x) {
			res += tr[x];
			x -= lowbit(x);
		}
		return res;
	}
}sgt;
//..........................................................
void CDQ(int l, int r) {
	if(l == r) return;
	CDQ(l,mid);
	CDQ(mid+1,r);
	int L = l, R = mid+1;
	// 统计【L,mid】对【mid+1,R】里面查询的影响 
	while(L <= mid && R <= r) {
		if(Node[L].r >= Node[R].r) {
			if(!Node[L].op) sgt.add(Node[L].l,Node[L].w);
			backup.push_back(Node[L++]);
		} else {
			if(Node[R].op) Node[R].w += sgt.sum(Node[R].l); 
			backup.push_back(Node[R++]);
		}
	}
	while(L <= mid) {
		if(!Node[L].op) sgt.add(Node[L].l,Node[L].w);
		backup.push_back(Node[L++]);
	}
	while(R <= r) {
		if(Node[R].op) Node[R].w += sgt.sum(Node[R].l);
		backup.push_back(Node[R++]);		
	}
	for(int i = l; i <= mid; ++ i) // 恢复树状数组
	  if(!Node[i].op)  
	    sgt.add(Node[i].l,-Node[i].w);

	for(int i = l; i <= r; ++ i)
	  Node[i] = backup[i-l];
	backup.clear();
}

int main() {
	init();
	// for(int i = 1; i <= Qnum; ++ i)
	//   cout << Node[i].tim << " " << Node[i].l << " " << Node[i].r << " " << Node[i].w << " " << Node[i].op << endl;
	CDQ(1,Qnum);
	sort(Node+1,Node+Qnum+1);
	for(int i = 1; i <= Qnum; ++ i)
	  if(Node[i].op)
	    cout << Node[i].w << endl;
	return 0;
}
/* 

7 1
1 2 3 1 3 2 1
2 3 6


 */