暴力数据结构 : 珂朵莉树 (ODT)

前言

珂朵莉树Old Driver Tree (ODT) 是一种十分暴力的数据结构。珂朵莉树是一场 CF 比赛中提出的数据结构,因那道题题面(CF896C)关于珂朵莉而得名。

珂朵莉树适用于以下的情况:维护一个序列,有区间赋值操作,数据随机。下面是珂朵莉树板子题:

维护一个序列,需要支持以下操作

1. 将 $[l,r]$ 区间所有数加上 $x$

2. 将 $[l,r]$ 区间所有数改成 $x$

3. 求 $[l,r]$ 区间第 $k$ 小

4. 求 $[l,r]$ 区间每个数字的 $x$ 次方的和模 $y$ 的值 (即 $\left(\sum_{i=l}^{r} a_{i}^{x}\right) \bmod y$)

– CF896C Willem, Chtholly and Seniorious

支持的操作还可以有很多,只要暴力能做珂朵莉树一般都可以做。

珂朵莉树的思想是维护一堆区间,合并相同值的区间,这样区间总数就可以减少。

珂朵莉树非常依赖区间赋值操作,如果区间赋值操作很少或者区间赋值的区间都较短,那么珂朵莉树和暴力就没什么区别了。

显然,要卡珂朵莉树非常容易。但对于数据完全随机的情况,珂朵莉树就可以跑得飞快。有很多题可以用珂朵莉树水过,甚至比正解还快。

思路

珂朵莉树维护了很多区间。

一个区间表示一段相同的数。一个区间 $(l,r,num)$ 表示从左端点 $l$ 到右端点 $r$,中间的数字全部为 $num$。

例如 $1,2,3,3,3,4,4,5$ 可以用 $5$ 个区间来表示:$(1,1,1)(2,2,2)(3,5,3)(6,7,4)(8,8,5)$。

区间赋值的时候,我们可以删去一些区间并用一个大区间代替它们,区间数量就少了很多。

而查询只需要找出相应的区间,然后暴力统计即可。

如果某次操作的边界在某个区间的中心,那么将这个区间断开即可。

我们用 set 维护区间左端点位置的值,使区间始终保持有序。

区间结构体定义

struct node{
	long long l,r; //左端点,右端点
	mutable long long num; //区间值
	bool operator<(const node y) const{
		return l<y.l;
	}
};

Split

Split 操作用来将一个区间断开。

set<node>::iterator split(long long x){ //返回位置为 x 的区间迭代器,如果不存在该区间则 split 该位置所在的区间成两份
	node tmp={x};
	set<node>::iterator it=s.lower_bound(tmp); //查找所在的位置
	if (it!=s.end()&&it->l==x){ //如果区间边界就是 x
		return it; //那么直接返回该区间
	}
	it--; //否则退回前一个区间
	long long l=it->l,r=it->r,num=it->num;
	s.erase(it); //移除这个区间
	tmp={l,x-1,num};
	s.insert(tmp); //插入 split 后的左半区间
	tmp={x,r,num};
	return s.insert(tmp).first; //插入 split 后的右半区间并返回该区间的迭代器
	//insert 方法返回的是一个 pair,pair 的第一个元素即为插入后元素的迭代器
}

区间赋值操作 (Assign)

删除该区间所覆盖的所有小区间,并插入一个大区间来代替它们。

void assign(long long l,long long r,long long x){ //将 l 到 r 的数赋值为 x
	set<node>::iterator R=split(r+1); //找右边端点区间 (注意这里要先找 R,否则如果为边界情况区间会被 erase 一次,接下来的 erase 操作就会错误)
	set<node>::iterator L=split(l); //找左边端点区间
	s.erase(L,R); //移除左右端点区间之间的这些区间
	node tmp={l,r,x};
	s.insert(tmp); //插入新的大区间
}

查询操作

就是暴力,找出相应区间并暴力统计

区间和

long long query_sum(long long l,long long r){ //l 到 r 的区间和
	set<node>::iterator R=split(r+1),L=split(l); //找左右端点区间
	long long ans=0;
	while (L!=R){
		ans+=L->num*(L->r-L->l+1); //遍历求和
		ans%=y; 
		L++;
	}
	return ans;
}

区间 x 次方和

和求和一样,只是改成快速幂

long long query_pow_sum(long long l,long long r,long long x,long long y){ //l 到 r 的 x 次方和模 y
	set<node>::iterator R=split(r+1),L=split(l);
	long long ans=0;
	while (L!=R){
		ans+=qpow(L->num,x,y)*(L->r-L->l+1); //快速幂并累计
		ans%=y; 
		L++;
	}
	return ans;
}

区间第 k 小

取出相应区间内的所有区间排序,从前到后找第 k 小

long long query_kth(long long l,long long r,long long k){ //l 到 r 区间内第 k 小的数
	set<node>::iterator R=split(r+1),L=split(l);
	vector<pair<long long,long long> > t;
	while (L!=R){
		t.push_back(make_pair(L->num,L->r-L->l+1)); //插入 vector
		L++;
	}
	sort(t.begin(),t.end()); //排序
	for (long long i=0;i<t.size();i++){
		k-=t[i].second;
		if (k<=0){
			return t[i].first; //达到前 k 个就返回
		}
	}
	return -2147483647;
}

其他操作

你应该已经发现了,珂朵莉树其实就是暴力,暴力怎么写珂朵莉树就怎么写,真·暴力数据结构

例题代码

CF896C Willem, Chtholly and Seniorious

#include<bits/stdc++.h>
using namespace std;
long long n,m,seed,vmax;
long long rnd(){
	long long ret=seed;
	seed=(seed*7+13)%1000000007;
	return ret;
}
inline long long qpow(long long a,long long b,long long p){
    long long ans=1;
    a%=p;
    while(b){
        if(b&1){
        	ans=ans*a%p;
		}
        a=a*a%p;
    	b>>=1;
    }
    return ans;
}
struct node{
	long long l,r;
	mutable long long num;
	bool operator<(const node y) const{
		return l<y.l;
	}
};
set<node> s;
set<node>::iterator split(long long x){
	node tmp={x};
	set<node>::iterator it=s.lower_bound(tmp);
	if (it!=s.end()&&it->l==x){
		return it;
	}
	it--;
	long long l=it->l,r=it->r,num=it->num;
	s.erase(it);
	tmp={l,x-1,num};
	s.insert(tmp);
	tmp={x,r,num};
	return s.insert(tmp).first;
}
void assign(long long l,long long r,long long x){
	set<node>::iterator R=split(r+1);
	set<node>::iterator L=split(l);
	s.erase(L,R);
	node tmp={l,r,x};
	s.insert(tmp);
}
long long query_kth(long long l,long long r,long long k){
	set<node>::iterator R=split(r+1),L=split(l);
	vector<pair<long long,long long> > t;
	while (L!=R){
		t.push_back(make_pair(L->num,L->r-L->l+1));
		L++;
	}
	sort(t.begin(),t.end());
	for (long long i=0;i<t.size();i++){
		k-=t[i].second;
		if (k<=0){
			return t[i].first;
		}
	}
	return -2147483647;
}
long long query_pow_sum(long long l,long long r,long long x,long long y){
	set<node>::iterator R=split(r+1),L=split(l);
	long long ans=0;
	while (L!=R){
		ans+=qpow(L->num,x,y)*(L->r-L->l+1);
		ans%=y; 
		L++;
	}
	return ans;
}
void add(long long l,long long r,long long x){
	set<node>::iterator R=split(r+1),L=split(l);
	while (L!=R){
		L->num+=x;
		L++;
	}
}
int main(){
	cin>>n>>m>>seed>>vmax;
	for (long long i=1;i<=n;i++){
		node tmp={i,i,rnd()%vmax+1};
		s.insert(tmp);
	}
	for (long long i=1;i<=m;i++){
		long long op=(rnd()%4)+1,l=(rnd()%n)+1,r=(rnd()%n)+1,x,y;
		if (l>r){
			swap(l,r);
		}
		if (op==3){
			x=(rnd()%(r-l+1))+1;
		}else{
			x=(rnd()%vmax)+1;
		}
		if (op==4){
			y=(rnd()%vmax)+1;
		}
		if (op==1){
			add(l,r,x);
		}
		if (op==2){
			assign(l,r,x);
		}
		if (op==3){
			cout<<query_kth(l,r,x)<<endl;
		}
		if (op==4){
			cout<<query_pow_sum(l,r,x,y)<<endl;
		}
	}
}

评论

  1. 匿名
    Macintosh Chrome
    3周前
    2020-10-11 11:02:02

    hi guys

  2. code
    Windows Edge
    3月前
    2020-8-11 8:55:20

    您好 请问您这个代码块是怎么调出来的 ?

  3. shiro
    Android Chrome
    3月前
    2020-8-02 9:41:27

    珂朵莉树,又称Old Driver Tree(ODT)(老司机树),是一种基于std::set的暴力数据结构(滑稽

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: Telegram @AmashiroNatsukiEars_NoWord Sticker
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
AmashiroNatsukiEars
小恐龙
花!
上一篇