MnZn求调,0pts全WA,线段树写的
查看原帖
MnZn求调,0pts全WA,线段树写的
661641
Cx114514楼主2023/10/25 07:34
#include <bits/stdc++.h>
using namespace std;

int read()
{
	int f = 1;
	char c = getchar();
	while (!isdigit(c))
	{
	    if (c == '-') f = -1;
	    c = getchar();
    }
	int x = 0;
	while (isdigit(c))
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}

int buf[15];

void write(int x)
{
	int p = 0;
	if (x < 0)
	{
	    putchar('-');
	    x = -x;
	}
	if (x == 0) putchar('0');
	else
	{
		while (x)
		{
			buf[++p] = x % 10;
			x /= 10;
		}
		for (int i = p; i >= 1; i--)
			putchar('0' + buf[i]);
	}
}

int n, q, tag[2000005];

char c[500005];

struct node
{
	int lc, rc, num;
};

node tree[2000005];

void build(int rt, int l, int r)
{
	if (l == r) tree[rt] = {(int)(c[l] - 'A' + 1), (int)(c[l] - 'A' + 1), 1};
	else
	{
		int mid = (l + r) / 2;
		build(rt * 2, l, mid);
		build(rt * 2 + 1, mid + 1, r);
		tree[rt].lc = tree[rt * 2].lc;
		tree[rt].rc = tree[rt * 2 + 1].rc;
		if (tree[rt * 2].rc == tree[rt * 2 + 1].lc) tree[rt].num = tree[rt * 2].num + tree[rt * 2 + 1].num - 1;
		else tree[rt].num = tree[rt * 2].num + tree[rt * 2 + 1].num;
	}
}

void update(int rt, int l, int r, int tl, int tr, int x)
{
    //cout << rt << " " << l << " " << r << " " << tl << " " << tr << " " << x << endl;
	if (tl <= l && r <= tr)
	{
		tag[rt] = x;
		tree[rt] = {x, x, 1};
	}
	else
	{
		if (tag[rt] != -1)
		{
			tag[rt * 2] = tag[rt];
			tree[rt * 2] = {tag[rt], tag[rt], 1};
			tag[rt * 2 + 1] = tag[rt];
			tree[rt * 2 + 1] = {tag[rt], tag[rt], 1};
			tag[rt] = -1;
		}
		int mid = (l + r) / 2;
		if (tl <= mid) update(rt * 2, l, mid, tl, tr, x);
		if (tr > mid) update(rt * 2 + 1, mid + 1, r, tl, tr, x);
		tree[rt].lc = tree[rt * 2].lc;
		tree[rt].rc = tree[rt * 2 + 1].rc;
		if (tree[rt * 2].rc == tree[rt * 2 + 1].lc) tree[rt].num = tree[rt * 2].num + tree[rt * 2 + 1].num - 1;
		else tree[rt].num = tree[rt * 2].num + tree[rt * 2 + 1].num;
	}
}

node query(int rt, int l, int r, int tl, int tr)
{
	if (tl <= l && r <= tr) return tree[rt];
	if (tag[rt] != -1)
	{
		tag[rt * 2] = tag[rt];
		tree[rt * 2] = {tag[rt], tag[rt], 1};
		tag[rt * 2 + 1] = tag[rt];
		tree[rt * 2 + 1] = {tag[rt], tag[rt], 1};
		tag[rt] = -1;
	}
	int mid = (l + r) / 2;
	if (tr <= mid) return query(rt * 2, l, mid, tl, tr);
	if (tl > mid) return query(rt * 2 + 1, mid + 1, r, tl, tr);
	node A = query(rt * 2, l, mid, tl, tr), B = query(rt * 2 + 1, mid + 1, r, tl, tr), C;
	C.lc = A.lc;
	C.rc = B.rc;
	if (A.rc == B.lc) C.num = A.num + B.num - 1;
	else C.num = A.num + B.num;
	return C;
}

int main()
{
	memset(tag, -1, sizeof(tag));
	n = read();
	for (int i = 1; i <= n; i++)
		scanf("%c", &c[i]);
	build(1, 1, n);
	q = read();
	while (q--)
	{
		char x;
		scanf("%c", &x);
		if (x == 'A')
		{
			int l, r;
			char op;
			l = read(), r = read();
			scanf("%c", &op);
			update(1, 1, n, l, r, (int)(op - 'A' + 1));
		}
		else
		{
			int l, r;
			l = read(), r = read();
			if (l == 1 || r == n)
			{
				node t = query(1, 1, n, l, r);
				if (t.num == 1) printf("Yes\n");
				else printf("No\n");
			}
			else
			{
				node t = query(1, 1, n, l, r), t1 = query(1, 1, n, l - 1, l - 1), t2 = query(1, 1, n, r + 1, r + 1);
				if (t.num == 1 && t1.lc != t2.rc) printf("Yes\n");
				else printf("No\n");
			}
		}
	}
    return 0;
}

2023/10/25 07:34
加载中...