题意

给你一个长为 \(n\) 的序列 \(a_i\) 需要支持四个操作。

\(1~l~r~x:\) 把 \(i \in [l, r]\) 的 \(a_i\) 加 \(x\) 。
\(2~l~r~x:\) 把 \(i \in [l, r]\) 的 \(a_i\) 赋值成 \(x\) 。
\(3~l~r~x:\) 求 \([l, r]\) 区间的第 \(x\) 小元素。
\(4~l~r~x~y:\) 求 \((\sum_{i = l}^{r} {a_i}^x) \mod y\) 。

一共会操作 \(m\) 次。

保证数据随机（给了你一个随机数据生成器）。

\(1 \le n, m \le 10^5, 1 \le a_i \le 10^9\)

题解

对于这种 数据随机 并且有 区间赋值 的题，常常有一个很牛逼的乱搞算法，叫做 \(\mathrm{ODT(Old~Driver~Tree)}\) ，也有叫 \(\mathrm{Chtholly Tree}\) 的。

至于这个怎么做的呢？其实核心就一条，优化暴力。

如何优化呢？因为有赋值操作，考虑把相邻的数值一样的点合并成一个整的区间就行了。

至于如何实现呢？我们用 std :: set<Node> 维护一段段区间就行了。

Node 内容如下 mutalbe 是为了支持指针修改：

struct Node {

	int l, r; mutable ll val;

}

inline bool operator < (const Node &lhs, const Node &rhs) {

	return lhs.l < rhs.l;

}

修改的时候，我们把 \([l, r]\) 这段区间 \(Split\) 出来，也就是我们把 \(l\) 与 \(l-1\) 分开，\(r\) 与 \(r + 1\) 分开就行了。

具体实现如下：

void Split(int pos) {

	auto it = S.lower_bound((Node){pos, 0, 0});

	if (it == S.end() || it -> l > pos) {

		-- it;

		S.emplace(it -> l, pos - 1, it -> val);

		S.emplace(pos, it -> r, it -> val);

		S.erase(it);

	}

} // 将 pos 与 pos - 1 分开。

然后对于操作 \([l, r]\) 区间，只需要暴力遍历指针就行了。（怎么暴力怎么来）

只有区间赋值那里需要搞搞操作，一次可以抹去一连续区间的迭代器。

也就是 S.erase(itl, itr) 会把 [itl, itr) 的所有元素全部删除，复杂度也挺优秀的。（比单个删除快）

然后这样操作后复杂度就变成 \(O(m \log n)\) 的，十分的优秀。

总结

乱搞大法好啊！！\(^o)/~

代码

好写好调，真是一个优秀的暴力做法。

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)

#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)

#define Set(a, v) memset(a, v, sizeof(a))

#define Cpy(a, b) memcpy(a, b, sizeof(a))

#define debug(x) cout << #x << ": " << (x) << endl

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

#define fir first

#define sec second

#define mp make_pair

#define pb push_back

using namespace std;

typedef long long ll;

typedef pair<ll, int> PII;

template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }

template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }

inline int read() {

	int x(0), sgn(1); char ch(getchar());

	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;

	for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);

	return x * sgn;

}

void File() {

#ifdef zjp_shadow

	freopen ("C.in", "r", stdin);

	freopen ("C.out", "w", stdout);

#endif

}

const int N = 1e5 + 1e3;

int n, m, seed, v, a[N];

inline int rnd() {

	int res = seed;

	seed = (seed * 7ll + 13) % 1000000007;

	return res;

}

inline int Get(int lim) {

	return rnd() % lim + 1;

}

struct Node {

	int l, r; mutable ll val;

	Node(int l_ = 0, int r_ = 0, ll val_ = 0): l(l_), r(r_), val(val_) {

	}

};

inline bool operator < (const Node &lhs, const Node &rhs) {

	return lhs.l < rhs.l;

}

multiset<Node> S;

vector<PII> V;

void Split(int pos) {

	auto it = S.lower_bound((Node){pos, 0, 0});

	if (it == S.end() || it -> l > pos) {

		-- it;

		S.emplace(it -> l, pos - 1, it -> val);

		S.emplace(pos, it -> r, it -> val);

		S.erase(it);

	}

}

int Mod;

inline int fpm(int x, int power) {

	int res = 1;

	for (; power; power >>= 1, x = 1ll * x * x % Mod)

		if (power & 1) res = 1ll * res * x % Mod;

	return res;

}

int main () {

	File();

	n = read(); m = read(); seed = read(); v = read();

	For (i, 1, n) a[i] = Get(v);

	for (int i = 1, j = 1; i <= n; i = j) {

		while (a[j] == a[i]) ++ j;

		S.emplace(i, j - 1, a[i]);

	}

	For (i, 1, m) {

		int opt = Get(4), l = Get(n), r = Get(n), x, y;

		if (l > r) swap(l, r);

		x = opt == 3 ? Get(r - l + 1) : Get(v);

		y = opt == 4 ? Get(v) : 0;

		Split(l); if (r < n) Split(r + 1);

		auto itl = S.lower_bound((Node) {l, 0, 0}),

			 itr = S.upper_bound((Node) {r, 0, 0});

		if (opt == 1) {

			for (auto it = itl; it != itr; ++ it)

				it -> val += x;

		}

		if (opt == 2) {

			S.erase(itl, itr);

			S.emplace(l, r, x);

		}

		if (opt == 3) {

			V.clear();

			for (auto it = itl; it != itr; ++ it)

				V.pb(mp(it -> val, it -> r - it -> l + 1));

			sort(V.begin(), V.end());

			for (auto it : V)

				if (x <= it.sec) {

					printf ("%lld\n", it.fir); break;

				} else x -= it.sec;

		}

		if (opt == 4) {

			int ans = 0; Mod = y;

			for (auto it = itl; it != itr; ++ it)

				ans = (ans + 1ll * fpm(it -> val % Mod, x) * (it -> r - it -> l + 1)) % Mod;

			printf ("%d\n", ans);

		}

	}

	return 0;

}

巴特西

Codeforces Round #449 (Div. 1) Willem, Chtholly and Seniorious (ODT维护)

题意

题解

总结

代码

最新文章

热门文章