珂朵莉树

Async #2.0.1

2026-05-10 13:58:57

发布于：浙江

13阅读

0回复

0点赞

注意这是一个暴力算法

1 背景与来源

起源题目：CF 896C Willem, Chtholly and Seniorious
正式名称：Old Driver Tree
本质：基于 set 的区间暴力合并

2 适用条件（非常重要）

2.1 必须满足

$\text{存在大量区间赋值}$

2.2 推荐环境

随机数据
对复杂度要求不严格
比赛 / 快速实现

3 核心思想

3.1 区间表示

数组被划分为若干连续段：

$[l_1,r_1,v_1],[l_2,r_2,v_2],\dots$

相同值合并为一个节点。

3.2 关键直觉

区间赋值会急剧减少段数

期望段数：

$\mathbb{E}[k]=O(\log n)$

4 数据结构定义

struct Node{
	int l,r;
	mutable int v;
};
bool operator<(const Node&a,const Node&b){
	return a.l<b.l;
}
set<Node>s;

5 核心操作

5.1 split（拆分）

auto split(int p){
	auto it=s.lower_bound({p,0,0});
	if(it!=s.end()&&it->l==p)return it;
	it--;
	int l=it->l,r=it->r,v=it->v;
	s.erase(it);
	s.insert({l,p-1,v});
	return s.insert({p,r,v}).first;
}

5.2 assign（区间赋值）

void assign(int l,int r,int v){
	auto er=split(r+1),el=split(l);
	s.erase(el,er);
	s.insert({l,r,v});
}

✅ ODT 的灵魂

6 区间查询

6.1 区间和

long long sum(int l,int r){
	auto er=split(r+1),el=split(l);
	long long res=0;
	for(auto it=el;it!=er;it++){
		res+=1LL*(it->r-it->l+1)*it->v;
	}
	return res;
}

6.2 区间加

void add(int l,int r,int v){
	auto er=split(r+1),el=split(l);
	for(auto it=el;it!=er;it++){
		it->v+=v;
	}
}

6.3 区间 k 小

int kth(int l,int r,int k){
	vector<pair<int,int>>a;
	auto er=split(r+1),el=split(l);
	for(auto it=el;it!=er;it++){
		a.emplace_back(it->v,it->r-it->l+1);
	}
	sort(a.begin(),a.end());
	for(auto [v,c]:a){
		k-=c;
		if(k<=0)return v;
	}
	return -1;
}

6.4 区间幂次和

$\sum_{i=l}^{r} a_i^k \bmod m$

int qp(int a,int b,int m){
	int r=1;
	while(b){
		if(b&1)r=1LL*r*a%m;
		a=1LL*a*a%m;
		b>>=1;
	}
	return r;
}
int powsum(int l,int r,int k,int m){
	auto er=split(r+1),el=split(l);
	int res=0;
	for(auto it=el;it!=er;it++){
		res=(res+1LL*(it->r-it->l+1)*qp(it->v,k,m))%m;
	}
	return res;
}

7 完整可用模板（CF 896C）

#include<bits/stdc++.h>
using namespace std;

struct Node{
	int l,r;
	mutable int v;
};
bool operator<(const Node&a,const Node&b){
	return a.l<b.l;
}
set<Node>s;

auto split(int p){
	auto it=s.lower_bound({p,0,0});
	if(it!=s.end()&&it->l==p)return it;
	it--;
	int l=it->l,r=it->r,v=it->v;
	s.erase(it);
	s.insert({l,p-1,v});
	return s.insert({p,r,v}).first;
}

void assign(int l,int r,int v){
	auto er=split(r+1),el=split(l);
	s.erase(el,er);
	s.insert({l,r,v});
}

void add(int l,int r,int v){
	auto er=split(r+1),el=split(l);
	for(auto it=el;it!=er;it++)it->v+=v;
}

long long sum(int l,int r){
	auto er=split(r+1),el=split(l);
	long long res=0;
	for(auto it=el;it!=er;it++)
		res+=1LL*(it->r-it->l+1)*it->v;
	return res;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		s.insert({i,i,x});
	}

	while(m--){
		int op,l,r,v,k;
		cin>>op>>l>>r>>v;
		if(op==1)add(l,r,v);
		else if(op==2)assign(l,r,v);
		else if(op==3)cout<<sum(l,r)<<'\n';
	}
	return 0;
}