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

题目链接

题目大意：

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

解题思路：

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

• $t_i\le t_j$
• $i\le r$
• $pre[i]\ge l$
• 每个偏序的贡献是$i-pre[i]$
  那么上CDQ分治：

AC code

实现细节

1. 对于查询操作我们变成$(t,r,l,0)$
2. 对于初始的点我们变成$(t,i,pre[i],i-pre[i])$
3. 对于修改操作：我们先加入一个时间戳$(t,i,pre[i],-(i-pre[i]))$
4. 然后再加入新的点$(t,now,pre[now],now-pre[now])$
5. 这里有很多细节就是你修改一个点，你会影响到4个点
   5.1你的后继节点的$pre$值
   5.2你的前驱节点的$nxt$值
   5.3就是你修改后的$nxt$和$pre$
   5.4这里你要对每个点开个$set$去维护动态前驱和后继
6. CDQ的时候可以直接归并排序对于$pre$的维度，把$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


 */

最后

以上就是痴情皮卡丘为你收集整理的CDQ分治 + 树状数组 ---- C. Goodbye Souvenir（三维偏序+思维）的全部内容，希望文章能够帮你解决CDQ分治 + 树状数组 ---- C. Goodbye Souvenir（三维偏序+思维）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。