Old Driver Tree

Posted by JHSN on January 17, 2018

Problem

[Codeforces 896C] Willem, Chtholly and Seniorious

一个随机序列,四种操作:区间加一个数,区间赋值,求区间第k小,求区间幂次和 $\sum_{i=l}^r{a_i}^x \mod y$。数据范围:$n,m\leq10^5$。保证操作随机。时限 2s。


ODT

这场 CF 的作者叫做 ODT。emmmmm … ODT 被称为 Old Driver Tree,亦称 Chtholly Tree。emmmmm … 其实 ODT 也不能算什么 Tree 一类的数据结构,不过是一种思想:将序列中连续的相同的元素整合,用一个三元组 $(L,R,val)$ 来表示。

怎么维护呢?std::set!用 set 以 $L$ 为关键字保存区间。先介绍一个 split 操作:从原有的区间中剥离出一个以 pos 开头的区间。所以对于每一个操作所涉及的 $[L,R]$,我们先将 $L$ 和 $R + 1$ 剥离出来,这样一来 $[L,R]$ 就由若干个区间组成了,处理起来很方便。接下来操作 ①②③④ 均可配合 set 的操作进行暴力维护,太简单了,set 一把梭就完了。

typedef long long LL;
struct ODT {
	struct node {
		int l, r;
		mutable LL v;
		node(int L, int R = -1, LL V=0) : l(L), r(R), v(V) {}
		bool operator < (const node& o) const {
			return l < o.l;
		}
	};

	set<node> s;
	vector< pair<LL, int> > vp;
	ODT(int n, LL x=0) {
		s.insert(node(1, n, x));
	}

	set<node>::iterator split(int pos) {
		auto it = s.lower_bound(node(pos));
		if (it != s.end() && it->l == pos) return it;
		--it;
		if (pos > it->r) return s.end();
		int L = it->l, R = it->r;
		LL V = it->v;
		s.erase(it);
		s.insert(node(L, pos - 1, V));
		return s.insert(node(pos, R, V)).first;
	}

	void add(int l, int r, LL val=1) {
		split(l);
		auto itr = split(r + 1), itl = split(l);
		for (; itl != itr; ++itl) itl->v += val;
	}

	void assign(int l, int r, LL val=0) {
		split(l);
		auto itr = split(r + 1), itl = split(l);
		s.erase(itl, itr);
		s.insert(node(l, r, val));
	}

	LL rank(int l, int r, int k, bool reversed=0) {
		if (reversed) k = r - l + 2 - k;
		split(l);
		auto itr = split(r + 1), itl = split(l);
		vp.clear();
		for (; itl != itr; ++itl)
			vp.push_back({itl->v, itl->r - itl->l + 1});
		sort(vp.begin(), vp.end());
		for (auto i : vp) {
			k -= i.second;
			if (k <= 0) return i.first;
		}
		return -1;
	}

	LL pow(LL x, int y, int mod) {
		x %= mod;
		LL res = 1;
		for (; y; y >>= 1, x = (x * x) % mod)
			if (y & 1) res = (res * x) % mod;
		return res;
	}

	LL sum(int l, int r, int ex, int mod) {
		split(l);
		auto itr = split(r + 1), itl = split(l);
		LL res = 0;
		for (; itl != itr; ++itl)
			res = (res + (LL)(itl->r - itl->l + 1) * pow(itl->v, ex, mod)) % mod;
		return res;
	}
};

因为有操作 ① 的存在,需要对 set 里的元素进行修改,所以使用了 mutable 关键字,用于完全解除 const 限制。


时间复杂度?

因为有 $\frac{1}{4}$ 的概率进行操作 ②,由于操作随机,所以会对其中一段(按概率统计,从一条线段中随机取出一条子线段的期望长度为原长度的 $\frac{1}{3}$)赋值,即将该段整合为一个元素。换一种不严谨但容易理解的说法:每 4 次操作,就有 1 次赋值操作,区间数就会变为原来的大约 $\frac{2}{3}$。

经测试发现,在理想的随机情况下,set 中的元素个数(下称 $\mid S\mid$)可以依靠操作 ② 来快速趋近一个相对稳定的状态,此稳态下 $\bar{\mid S\mid}$ 与 $\log_2n$ 有显著的线性关系(不会证)。所以时间复杂度可看作 $O((n+m) \log_2n)$,但常数很大,而且逼近稳态的过程也需要一些时间。


Another Problem

[Codeforces 915E] Physical Education Lessons

一个序列,起始全为黑色,进行区间黑白染色,每次操作结束后给出整个序列的黑色数量。数据范围:$n\leq10^9,m\leq3\cdot10^5$。时限 1s。

离散化+线段树打标记?太长了而且还容易写挫。ODT,请。而且不需要随机这个条件,因为每次操作最多增加 2 个区间,而每个区间只会被插入 1 次,删除 1 次或不删除,所以操作 set 的次数是极其有限的,而且整个序列的和可以随操作一起维护。总时间复杂度可近似看作 $O(m \log_2n)$。

struct ODT {
	struct node {
		int l, r;
		bool v;
		node(int L, int R = -1, bool V=0) : l(L), r(R), v(V) {}
		bool operator < (const node& o) const {
			return l < o.l;
		}
	};
	set<node> s;
	int sum=0; 
	ODT(int n, bool x=0) {
		push(node(1, n, x));
	}
	set<node>::iterator push(const node &x) {
		if (x.v) sum += x.r - x.l + 1;
		return s.insert(x).first;
	}
	void pop(set<node>::iterator x) {
		if (x->v) sum -= x->r - x->l + 1;
		s.erase(x);
	}
	set<node>::iterator split(int pos) {
		auto it = s.lower_bound(node(pos));
		if (it != s.end() && it->l == pos) return it;
		--it;
		if (pos > it->r) return s.end();
		int L = it->l, R = it->r;
		bool V = it->v;
		pop(it);
		push(node(L, pos - 1, V));
		return push(node(pos, R, V));
	}
	void assign(int l, int r, bool val=0) {
		split(l);
		auto itr = split(r + 1), itl = split(l);
		while (itl != itr) {
			auto tmp = itl;
			++itl;
			pop(tmp);
		}
		push(node(l, r, val));
	}
};

int main() {
	int n, Q, l, r, k;
	scanf("%d%d", &n, &Q);
	ODT odt(n, 1);
	while (Q--) {
		scanf("%d%d%d", &l, &r, &k);
		odt.assign(l, r, k - 1);
		printf("%d\n", odt.sum);
	}
	return 0;
}

比起离散化+线段树打标记,短爆好吧,短爆。




评论区加载中