求调 CF2030D,悬两到三关
  • 板块学术版
  • 楼主EricWan
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/20 00:43
  • 上次更新2024/10/20 10:46:12
查看原帖
求调 CF2030D,悬两到三关
377873
EricWan楼主2024/10/20 00:43
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
int T, n, q, a[MAXN], b[MAXN][16], c[MAXN][16];
set<int> ending;
set<pair<int, int> > block;
char op[MAXN];
int querymin(int l, int r)
{
	int k = log2(r - l);
	return min(c[l][k], c[r - (1 << k) + 1][k]);
}
int querymax(int l, int r)
{
	int k = log2(r - l);
	return max(b[l][k], b[r - (1 << k) + 1][k]);
}
int querymin(pair<int, int> a)
{
	return querymin(a.first, a.second);
}
int querymax(pair<int, int> a)
{
	return querymax(a.first, a.second);
}
void printblock()
{
	cout << "printblock:" << endl;
	for (pair<int, int> i : block)
	{
		cout << i.first << " " << i.second << endl;
	}
	cout << endl;
}
int main()
{
	memset(c, 0x3f, sizeof(c));
	cin >> T;
	while (T--)
	{
		// cout << "T = " << T << endl;
		block.clear();
		cin >> n >> q;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			b[i][0] = a[i];
			c[i][0] = a[i];
		}
		for (int i = 1; i <= n; i++)
		{
			cin >> op[i];
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= 15; j++)
			{
				b[i][j] = max(b[i][j - 1], b[i + (1 << (j - 1))][j - 1]);
				c[i][j] = min(c[i][j - 1], c[i + (1 << (j - 1))][j - 1]);
			}
		}
		ending.clear();
		for (int i = 1; i <= n; i++)
		{
			if (op[i] == 'R' && op[i - 1] == 'L')
			{
				ending.insert(i - 1);
				// cout << "ending : " << i - 1 << endl;
			}
		}
		ending.insert(n);
		int lst = 0, badend = 0;
		for (int i : ending)
		{
			block.insert({lst + 1, i});
			lst = i;
		}
		pair<int, int> lstblock = {0, 0}, emptyblock = {0, 0};
		for (pair<int, int> i : block)
		{
			if (lstblock != emptyblock)
			{
				badend += ((querymin(i) > querymax(lstblock)) ? 0 : 1);
			}
			lstblock = i;
		}
		// for (pair<int, int> i : block)
		// {
		// 	cout << i.first << " " << i.second << endl;
		// }
		while (q--)
		{
			int OP;
			cin >> OP;
			auto i = block.upper_bound({OP, OP});
			i--;
			pair<int, int> nowblock = *i;
			auto nowit = i;
			int Cnt = 0;
			while (i != block.begin() && Cnt <= 2)
			{
				i--;
				Cnt++;
			}
			int bgn = (*i).first;
			Cnt = 0;
			while ((*i).second < n && Cnt <= 5)
			{
				i++;
				Cnt++;
			}
			int ed = (*i).second;
			for (auto j = block.lower_bound({bgn, bgn}); j != block.end() && (*j).second < ed; j++)
			{
				auto k = j;
				k++;
				badend -= ((querymin(*k) > querymax(*j)) ? 0 : 1);
			}
			pair<int, int> pre = emptyblock, nxt = emptyblock;
			if (nowit != block.begin())
			{
				nowit--;
				pre = *nowit;
				nowit++;
			}
			if ((*nowit).second < n)
			{
				nowit++;
				nxt = *nowit;
				nowit--;
			}
			// cout << pre.first << "," << pre.second << "  " << nxt.first << "," << nxt.second << "  " << OP << " " << op[OP - 1] << op[OP] << op[OP + 1] << endl;
			if (op[OP - 1] == 'L' && op[OP] == 'L' && op[OP + 1] == 'L') block.erase(nowblock), block.insert({nowblock.first, OP - 1}), block.insert({OP, nowblock.second});
			if (op[OP - 1] == 'L' && op[OP] == 'R' && op[OP + 1] == 'L') block.erase(nowblock), block.erase(pre), block.insert({pre.first, nowblock.second});
			if (op[OP - 1] == 'R' && op[OP] == 'R' && op[OP + 1] == 'R') block.erase(nowblock), block.insert({nowblock.first, OP}), block.insert({OP + 1, nowblock.second});
			if (op[OP - 1] == 'R' && op[OP] == 'L' && op[OP + 1] == 'R') block.erase(nowblock), block.erase(nxt), block.insert({nowblock.first, nxt.second});
			if (op[OP - 1] == 'L' && op[OP] == 'L' && op[OP + 1] == 'R') block.erase(nowblock), block.erase(nxt), block.insert({nowblock.first, OP - 1}), block.insert({OP, nxt.second});
			if (op[OP - 1] == 'L' && op[OP] == 'R' && op[OP + 1] == 'R') block.erase(nowblock), block.erase(pre), block.insert({pre.first, OP}), block.insert({OP + 1, nowblock.second});
			// if (op[OP - 1] == 'L' && op[OP] == 'R' && op[OP + 1] == 'R') ;
			// if (op[OP - 1] == 'R' && op[OP] == 'L' && op[OP + 1] == 'L') ;
			for (auto j = block.lower_bound({bgn, bgn}); j != block.end() && (*j).second < ed; j++)
			{
				auto k = j;
				k++;
				badend += ((querymin(*k) > querymax(*j)) ? 0 : 1);
			}
			cout << ((badend == 0) ? "YES\n" : "NO\n");
			// cout << OP << " ";
			// for (int i = 1; i <= n; i++)
			// {
				// cout << op[i];
			// }
			// cout << " -> ";
			if (op[OP] == 'L')
			{
				op[OP] = 'R';
			}
			else if (op[OP] == 'R')
			{
				op[OP] = 'L';
			}
			// for (int i = 1; i <= n; i++)
			// {
				// cout << op[i];
			// }
			// cout << "    " << badend << endl;
		}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j <= 15; j++)
			{
				b[i][j] = 0;
				c[i][j] = 1e9;
			}
		}
	}
	return 0;
}
2024/10/20 00:43
加载中...