杂题

uoj46

看到这个操作是线性操作，我们想到可以把两个操作直接合并。那么就可以使用二进制分组。但是这道题有几个问题。

1. 修改是某一个区间，那么我们把一个修改 \((l,r,a,b)\) 改成三个 \((1,l-1,1,0),(l,r,a,b),(r+1,n,a,b)\)，就是对一整个序列操作。

2. 如何合并。直接归并排序，此时新的分割点数量是合并两者的和，所以总大小是 \(O(n)\) 的。

3. 查询是某一区间的修改，那么我们用一个支持合并又支持区间查询的的数据结构维护即可。那么使用线段树即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 600005;
template <typename T>
void read(T &x) {
	T sgn = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
	for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	x *= sgn;
}
ll mod;
int cnt;
ll add(ll a, ll b) { return a + b >= mod ? a + b - mod : a + b; }
ll dec(ll a, ll b) { return a - b < 0 ? a - b + mod : a - b; }
ll mul(ll a, ll b) { return (__int128)a * b % mod; }
struct opt{
	ll a, b;
	int r;
};
opt operator + (opt x, opt y) { // 先作用 x 再作用 y 
	return opt{mul(x.a, y.a), add(mul(y.a, x.b), y.b), min(x.r, y.r)};
}
bool operator < (opt x, opt y) {
	if (x.r != y.r) return x.r < y.r;
	return x.a < y.a;
}
int type;
int n, Q;
ll w[maxn];
ll lastans;
vector<opt> tr[maxn << 2];
int sum[maxn << 2];
vector<opt> Merge(vector<opt> &A, vector<opt> &B){
	vector<opt> ret;
	ret.clear();
	int p = 0, q = 0;
	while (p < (int)A.size() && q < (int)B.size()) {
		ret.push_back(A[p] + B[q]);
		if (A[p].r == B[q].r) p++, q++;
		else if (A[p].r < B[q].r) p++;
		else q++;
	}
	return ret;
}
void modify(int p, int l, int r, int pos, int x, int y, int a, int b) {
	if (l == r) {
		sum[p] = 1;
		tr[p].clear();
		if (x > 1) tr[p].push_back(opt{1, 0, x - 1});
		tr[p].push_back(opt{a, b, y});
		if (y < n) tr[p].push_back(opt{1, 0, n});
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) modify(p << 1, l, mid, pos, x, y, a, b);
	else modify(p << 1 | 1, mid + 1, r, pos, x, y, a, b);
	sum[p] = sum[p << 1] + sum[p << 1 | 1];
	if (sum[p] == r - l + 1) tr[p] = Merge(tr[p << 1], tr[p << 1 | 1]);
}
void query(int p, int l, int r, int x, int y, int pos) {
	if (l > y || r < x) return;
	if (x <= l && r <= y) {
		int q = lower_bound(tr[p].begin(), tr[p].end(), opt{0, 0, pos}) - tr[p].begin();
		lastans = add(mul(lastans, tr[p][q].a), tr[p][q].b);
		return;
	}
	int mid = (l + r) >> 1;
	query(p << 1, l, mid, x, y, pos);
	query(p << 1 | 1, mid + 1, r, x, y, pos);
} 
int main() {
	read(type);
	read(n); read(mod);
	for (int i = 1; i <= n; i++) read(w[i]);
	read(Q); int tmp = Q;
	while (Q--) {
		int cmd;
		int l, r, a, b;
		read(cmd);
		if (cmd == 1) {
			cnt++;
			read(l); read(r); read(a); read(b);
			if (type & 1) l = l ^ lastans, r = r ^ lastans;
			modify(1, 1, tmp, cnt, l, r, a, b);
		} else {
			read(l); read(r); read(a);
			if (type & 1) l = l ^ lastans, r = r ^ lastans, a = a ^ lastans;
			lastans = w[a];
			query(1, 1, tmp, l, r, a);
			printf("%lld\n", lastans);
		}
	}
	return 0;
}