Submission #38015595

---

Source Code Expand

#if IN_LOCAL
import local;
#endif // IN_LOCAL
#include<random>
#include<chrono>
#include<string>
#include<iostream>
using namespace std;
using namespace chrono;
mt19937 rng(static_cast<unsigned>(high_resolution_clock::now().time_since_epoch().count()));
struct Tree
{
	unsigned root, counter, init_weight[500005];
	struct Node
	{
		bool reversed;
		unsigned lc, rc, siz, weight, father;
	}node[500005];
	inline void Init(const unsigned n)
	{
		for (unsigned i = 1; i <= n; init_weight[i++] = rng());
		sort(init_weight + 1, init_weight + (n + 1));
		root = Build(1, n);
		return;
	}
	inline unsigned Build(const unsigned l, const unsigned r)
	{
		const unsigned mid = (l + r) / 2;
		node[mid].weight = init_weight[++counter];
		node[mid].siz = r - l + 1;
		if (l < mid)
		{
			node[node[mid].lc = Build(l, mid - 1)].father = mid;
		}
		if (mid < r)
		{
			node[node[mid].rc = Build(mid + 1, r)].father = mid;
		}
		return mid;
	}
	inline void AddTag(const unsigned pos)
	{
		node[pos].reversed = !node[pos].reversed;
		swap(node[pos].lc, node[pos].rc);
		return;
	}
	inline void DownTag(const unsigned pos)
	{
		if (node[pos].reversed)
		{
			if (node[pos].lc)
			{
				AddTag(node[pos].lc);
			}
			if (node[pos].rc)
			{
				AddTag(node[pos].rc);
			}
			node[pos].reversed = 0;
		}
		return;
	}
	inline void Maintain(const unsigned pos)
	{
		node[pos].siz = node[node[pos].lc].siz + node[node[pos].rc].siz + 1;
		return;
	}
	inline unsigned Split(unsigned& root, unsigned limit)
	{
		unsigned p = root;
		for (DownTag(p); limit != node[node[p].lc].siz; DownTag(p))
		{
			if (limit < node[node[p].lc].siz)
			{
				p = node[p].lc;
			}
			else
			{
				limit -= node[node[p].lc].siz + 1;
				p = node[p].rc;
			}
		}
		if (p)
		{
			unsigned a = node[p].lc;
			if (a)
			{
				node[a].father = node[p].lc = 0;
				node[p].siz -= node[a].siz;
			}
			for (unsigned i = node[p].father, t = p; i; t = i, i = node[i].father)
			{
				node[t].father = 0;
				if (t == node[i].lc)
				{
					node[node[i].lc = p].father = i;
					Maintain(p = i);
				}
				else
				{
					node[node[i].rc = a].father = i;
					Maintain(a = i);
				}
			}
			root = a;
		}
		return p;
	}
	inline unsigned Merge(const unsigned a, const unsigned b)
	{
		if (a && b)
		{
			DownTag(a);
			DownTag(b);
			if (node[a].weight < node[b].weight)
			{
				node[a].siz += node[b].siz;
				return node[node[a].rc = Merge(node[a].rc, b)].father = a;
			}
			node[b].siz += node[a].siz;
			return node[node[b].lc = Merge(a, node[b].lc)].father = b;
		}
		return a | b;
	}
	inline void Print(const unsigned pos)
	{
		DownTag(pos);
		if (node[pos].lc)
		{
			Print(node[pos].lc);
		}
		init_weight[++counter] = pos;
		if (node[pos].rc)
		{
			Print(node[pos].rc);
		}
		return;
	}
	inline void Reverse(const unsigned l, const unsigned r)
	{
		unsigned p = Split(root, l - 1), q = Split(p, r - l + 1);
		AddTag(p);
		root = Merge(Merge(root, p), q);
		return;
	}
}t1, t2;
string a[500005];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	unsigned h, w;
	cin >> h >> w;
	t1.counter = t2.counter = 0;
	t1.Init(h);
	t2.Init(w);
	for (unsigned i = 1; i <= h; cin >> a[i], a[i] = " " + a[i], ++i);
	unsigned q;
	cin >> q;
	for (unsigned i = 1; i <= q; ++i)
	{
		unsigned a, b;
		cin >> a >> b;
		t1.Reverse(1, a);
		t1.Reverse(a + 1, h);
		t2.Reverse(1, b);
		t2.Reverse(b + 1, w);
	}
	t1.counter = t2.counter = 0;
	t1.Print(t1.root);
	t2.Print(t2.root);
	const auto& x = t1.init_weight, & y = t2.init_weight;
	for (unsigned i = 1; i <= h; ++i)
	{
		for (unsigned j = 1; j <= w; cout.put(a[x[i]][y[j]]), ++j);
		cout.put('\n');
	}
	return 0;
}

Submission Info

Judge Result