题解：P7134 小 H 的序列

solution

这个查询操作看起来十分像珂朵莉树的起源题对吧，所以自然想到珂朵莉树解决。

操作一似乎不能直接推平，考虑把每个区间转存到数组里面，再把操作区间删掉，然后把相邻且值相同的区间合并之后再加到珂朵莉树中。

询问操作就是很典的珂树了，把每个树里的的区间一起计算

v ^ {p}

，再乘上区间长度，累加到答案。

~~（怎么感觉能珂树的题都比较容易实现）~~

一些小细节

1.查询操作的累加应该写作 cnt = (cnt + (qpow(itl -> v, p, mod) % mod) * len(itl)) % mod;，不要模错地方，不要把

cnt

放到乘长度的括号里（因为这句盯了好久）。

2.正如大佬所说，就这样子写的话会因为每个查询里面有很多一样的数被重复计算而 T 一个点，所以要给快速幂加上记忆化。

code

CPP

#include<bits/stdc++.h>

#define int unsigned long long

namespace IO {
	inline int read() {
		int ret = 0, f = 1;char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -f;
			ch = getchar();
		}
		while (ch >= '0' && ch <= '9') {
			ret = (ret << 1) + (ret << 3) + (ch ^ 48);
			ch = getchar();
		}
		return ret * f;
	}
	void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}

using namespace IO;
using namespace std;

constexpr int maxn = 1e5 + 5;

int n, m;

struct Node {
	int l, r;
	mutable int v;
	
//	Node(int x, int y, int z) {
//		l = x, r = y, v = z;
//	}
	
	bool operator < (const Node & x) const {
		return l < x.l;
	} 
};

set<Node> odt;

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

void assign(int l, int r, int v) {
	auto itr = split(r + 1), itl = split(l);
	odt.erase(itl, itr);
	odt.insert({l, r, v});
}


int MOD[maxn], Val[maxn];
int qpow(int a, int p, int mod) {
	int ans = 1LL, A = a;
	
	if (MOD[A] == mod) return Val[A];

	while (p) {
		if (p & 1) ans *= a, ans %= mod;
		a *= a, a %= mod;
		p >>= 1;
	}
	
	Val[A] = ans, MOD[A] = mod;
	
//	cout << ans << '\n'; 
	return ans % mod;
}

void update(int l, int r, int x, int y, int d) {
//	cout << l << ' ' << r << ' ' << x << ' ' << y << ' ' << d << '\n';
	auto itr = split(r + 1), itl = split(l);Node its[maxn];
	int tot = 1, nowx = 0;
	for (auto i = itl;i != itr;i++) {
		int v = i -> v;
		its[++tot] = *i;
		if (v <= y && v >= x) its[tot].v = d;
	}
	
	odt.erase(itl, itr);
	
	for (int i = 1;i <= tot;i++) {
		if (i == 1 || its[i].v != its[i - 1].v) {
			if (nowx) odt.insert({nowx, its[i - 1].r, its[i - 1].v});
			nowx = its[i].l;
		}
	}
	odt.insert({nowx, r, its[tot].v});
}

int len(auto it) {
	return it -> r - it -> l + 1;
}

int query(int l, int r, int p, int mod) {
//	cout << l << ' ' << r << ' ' << p << ' ' << mod << '\n';
	auto itr = split(r + 1), itl = split(l);
//	cout << itl -> l << ' ' << itr -> r;
	int cnt = 0;
	for (;itl != itr;itl++) {
//		cout << itl -> l << ' ' << itl -> r << ' ' << itl -> v << ' ' << len(itl) << '\n';
//		(((cnt += qpow(itl -> v, p, mod)) %= mod) *= len(itl)) %= mod;
		cnt = (cnt + (qpow(itl -> v, p, mod) % mod) * len(itl)) % mod;
//		cout << qpow(itl -> v, p, mod) << "nailong " << cnt << '\n';
	}
//	cout << cnt << '\n';
	return cnt;
}

signed main() {
	n = read(), m = read();
	
	for (int i = 1;i <= n;i++) odt.insert({i, i, read()});
	
	int Ans = 0;
	
	while (m--) {
		int op = read(), l = read(), r = read(), u = read(), v = read(), t;
		if (op == 0) t = read(), update(l, r, u, v, t);
		else Ans ^= query(l, r, u, v);
		
//		for (auto i : odt) cout << i.l << ' ' << i.r << ' ' << i.v << '\n';
	}
	
	write(Ans), putchar(10);
	
	return 0;
}

题解：P7134 小 H 的序列

文章操作

solution

一些小细节

code

相关推荐

评论

题解：P7134 小 H 的序列