K题简单题解_牛客博客

K题简单题解：

用 $ls$ 与 $rs$ 维护一段区域中, 最左端区间与最右端区间的方块高度。由于题目是单点修改, 所以可以去掉 $pushdown$ 操作, 仅保留最关键的 $pushup$ , 用 $lz$ 记录最左与最右端的红色方块数。

在 $pushup$ 中, 由于蓝色方块会出现在上一排的右边, 所以我们设蓝色方块区间的最左端方块高度为 $0$ 而最右端高度为 $1$ (这时我们假设一个蓝色方块要占两排, 左边那一排没有任何方块, 等与左边区间合并时再填入这个空格排) , 最后与蓝色方块合并的时候要注意 $y.ls$ 是否是 $0$ , 若 $y.ls$ 为零, 那么合并后的区间 $u$ 的 $u.rs=y.rs$ 。注意当 $x$ 区间与 $y$ 区间合并的时候, 若 $y$ 区间的最左端方块堆内有红色方块, 那么 $x$ 区间最右端的所有方块都要翻 $y.lz$ 倍且 $x$ 区间内没有蓝色方块时, 我们可以发现 $y$ 区间内的红色方块还可以在下一次区间合并时, 继续使 $x'$ 区间最右端的方块数翻 $y.lz$ 倍, 当然, 若 $x$ 区间内没有蓝色方块且有红色方块那么合并区间 $u$ 区间的红色方块数为 $y.lz y.lz \times x.lz x.lz$ , 若 $x$ 区间内有蓝色方块, 那么合并区间 $u$ 区间的 $lz$ 为 $0$ 。

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define int long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define all(x) (x).begin(), (x).end()
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;

const int R = 'R';
const int B = 'B';
const int Y = 'Y';

const int mod = 1e9 + 7;


struct Node
{
	ll l, r;
	ll lz;
	ll ls, rs;
	ll res;
	ll ok; // 访问该点是否合法

	Node()
	{
		ls = rs = 0;
		l = r = 0;
		lz = 0;
		res = 0;
		ok = 0;
	}
};

vector<ll> arr;
vector<Node> tree;

void pushup(Node& u, Node& x, Node& y)
{
	u.ok = 1;
	u.lz = 0;
	if (!x.ok)
	{
		u.res = y.res;
		u.rs = y.rs;
		u.ls = y.ls;
		u.lz = y.lz;
	}
	else if (!y.ok)
	{
		u.res = x.res;
		u.rs = x.rs;
		u.ls = x.ls;
		u.lz = x.lz;
	}
	else
	{
		u.res = (x.res + y.res) % mod;
		u.ls = x.ls;
		u.rs = y.rs;
		if (x.ls == x.res) u.ls += y.ls, u.ls % mod;
		if (y.rs == y.res and y.ls) u.rs += x.rs, u.rs %= mod;
		if (x.lz) u.lz += x.lz;
		if (y.lz)
		{
			u.res = (y.res + x.res + x.rs * y.lz) % mod;
			if (x.ls == x.res) u.lz += y.lz + (y.lz) * x.lz, u.lz %= mod, u.ls += x.res * y.lz, u.ls %= mod;
			if (y.rs == y.res) u.rs += x.rs * y.lz, u.rs %= mod;
		}
	}
}

void build(ll i, ll l, ll r)
{
	tree[i].l = l;
	tree[i].r = r;
	if (l == r)
	{
		tree[i].ok = 1;
		tree[i].res = 1;
		if (arr[l] == Y)
		{
			tree[i].ls = 1;
			tree[i].rs = 1;
		}
		if (arr[l] == B)
		{
			tree[i].ls = 0;
			tree[i].rs = 1;
		}
		if (arr[l] == R)
		{
			tree[i].lz = 1;
			tree[i].ls = 1;
			tree[i].rs = 1;
		}
		return;
	}
	ll mid = (l + r) / 2;
	build(i << 1, l, mid);
	build(i << 1 | 1, mid + 1, r);
	pushup(tree[i], tree[i << 1], tree[i << 1 | 1]);
}


void modify(ll i, ll l, ll r, ll k)
{
	if (tree[i].l >= l && tree[i].r <= r)
	{
		if (k == Y)
		{
			tree[i].lz = 0;
			tree[i].ls = 1;
			tree[i].rs = 1;
		}
		if (k == B)
		{
			tree[i].lz = 0;
			tree[i].ls = 0;
			tree[i].rs = 1;
		}
		if (k == R)
		{
			tree[i].lz = 1;
			tree[i].ls = 1;
			tree[i].rs = 1;
		}
		return;
	}
	if (tree[i << 1].r >= l)
		modify(i << 1, l, r, k);
	if (tree[i << 1 | 1].l <= r)
		modify(i << 1 | 1, l, r, k);
	pushup(tree[i], tree[i << 1], tree[i << 1 | 1]);
}

Node query(ll i, ll l, ll r)
{
	if (tree[i].l >= l && tree[i].r <= r) return tree[i];
	Node ans, tmp1, tmp2;
	if (tree[i << 1].r >= l) tmp1 = query(i << 1, l, r);
	if (tree[i << 1 | 1].l <= r) tmp2 = query(i << 1 | 1, l, r);
	pushup(ans, tmp1, tmp2);
	return ans;
}

void solve()
{
	int n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	arr.resize(n + 1, 0);
	tree.resize(n << 2);
	for (int i = 1; i <= n; ++i) arr[i] = s[i - 1];
	build(1, 1, n);
	for (int i = 1; i <= m; ++i)
	{
		ll op;
		cin >> op;
		if (op == 1)
		{
			ll a; char b;
			cin >> a >> b;
			int k = b;
			modify(1, a, a, k);
		}
		if (op == 2)
		{
			ll a, b;
			cin >> a >> b;
			Node ans = query(1, a, b);
			cout << ans.res << endl;
		}
	}
}

signed main()
{
	IOS;
	int t = 1;
//	cin >> t;
	while (t--) solve();
	return 0;
}