A. Reverse

给一个

[

1..

n

]

[1..n]

[1..n]的序列，可以翻转一次，求字典序最小

只需要找到第一个与下标不同的数字，然后把这个数翻转到这个位置即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 4e5 + 10;
const int mod = 998244353;

#define fi first
#define se second
#define lowbit(x) x & (-x)

int a[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int _; cin >> _; while (_--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		int flag = 0;
		int c = 0;
		for (int i = 1; i <= n; i++) {
			if (i != a[i]) {
				c = i;
				flag = 1;
				break;
			}
		}
		if (!flag) {
			for (int i = 1; i <= n; i++) cout << a[i] << ' ';
			cout << endl;
			continue;
		}
		int d = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i] == c) {
				d = i;
				break;
			}
		}
		reverse(a+c, a+d+1);
		for (int i = 1; i <= n; i++) cout << a[i] << ' ';
		cout << endl;
	}
	return 0;
}
 

B. Odd Swap Sort

因为只能交换相邻数组，因此需要保证偶数和奇数分别有序

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 4e5 + 10;
const int mod = 998244353;

#define fi first
#define se second
#define lowbit(x) x & (-x)

int a[N], fa[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int _; cin >> _; while (_--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		int flag = 0;
		vector<int> c, b;
		for (int i = 1; i <= n; i++) {
			if (a[i] % 2 == 1) c.push_back(a[i]);
		}
		for (int i = 1; i <= n; i++) {
			if (a[i] % 2 == 0) b.push_back(a[i]);
		}
		flag = 0;
		for (int i = 1; i < b.size(); i++) {
			if (b[i] < b[i-1]) flag = 1;
		}
		for (int i = 1; i < c.size(); i++) {
			if (c[i] < c[i-1]) flag = 1;
		}
		if (flag) cout << "No" << endl;
		else cout << "Yes" << endl;
	}
	
	return 0;
}

C. Inversion Graph

题意中比较重要的信息，一个是[1…n]的序列，还有一个是逆序对建边

举个例子，3 1 5 2 4
第一个数是3，因此前3个数肯定可以组成一个连通块，到第三个数被更新成5，因此前5个数肯定是一个连通块。。。
还是比较好理解的

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 4e5 + 10;
const int mod = 998244353;

#define fi first
#define se second
#define lowbit(x) x & (-x)

int a[N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int _; cin >> _; while (_--) {
		int n; cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		int mx = a[1], ans = 1;
		for (int i = 2; i <= n; i++) {
			if (i > mx) {
				ans++;
			} 
			mx = max(mx, a[i]);
		}
		cout << ans << endl;
	}
	 
	return 0;
}

D. Big Brush

比较暴力的一题，考虑bfs，倒着考虑，把可以涂色的都入队，入队后将当前颜色置位0，为万能色，然后一直暴力找周围的8个点

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 4e5 + 10;
const int mod = 998244353;

#define fi first
#define se second
#define lowbit(x) x & (-x)
#define endl '\n'

int a[1005][1005], vis[1005][1005];
struct node {
	int x, y, k;
};
int n, m; 
int check(int x, int y) {
	int col = 0;
	int flag = 0;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			int dx = x+i;
			int dy = y+j;
			if (dx > n || dy > m) return 0;
			if (a[dx][dy] != col && a[dx][dy] && col) flag = 1;
			if (a[dx][dy]) col = a[dx][dy];  
		}
	}
	if (flag) return 0;
	else {
		for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) a[x+i][y+j]=0;
		return col;
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	cin >> n >> m;
	queue<node> q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int cur = check(i, j);
			if (cur) q.push({i,j,cur});
		}
	}
	vector<node> ans;
	while (q.size()) {
		node now = q.front();
		q.pop();
		if (vis[now.x][now.y]) continue;
		vis[now.x][now.y] = 1;
		// cout << now.x << ' ' << now.y << endl;
		ans.push_back(now);
		for (int l = -1; l <= 1; l++) {
			for (int r = -1; r <= 1; r++) {
				int dx = now.x + l;
				int dy = now.y + r;
				if (dx + 1 <= n && dx >= 1 && dy + 1 <= m && dy >= 1 && !vis[dx][dy]) {
					int cur = check(dx, dy);
					if (cur) q.push({dx,dy,cur});
				}
			}
		}
	}
	int flag = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j]) flag = 1;
		}
	}
	if (flag) {
		cout << "-1" << endl;
		return 0;
	}
	cout << ans.size() << endl;
	reverse(ans.begin(), ans.end());
	for (auto it : ans) {
		cout << it.x << ' ' << it.y << ' ' << it.k << endl;
	}
	return 0;
}

E. Colorful Operations

三个操作：1.区间覆盖颜色 2.对某种颜色加权值 3.输出单点权值

对于某种颜色的权值累加和可以开个数组单独处理，然后再修改颜色的时候对权值进行结算，先加上原先颜色的权值，再减去当前颜色的权值

至于怎么处理区间内的颜色，可以用珂朵莉树（其实就是用set模拟暴力）

珂朵莉树详解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N = 1e6 + 10;
const int mod = 1e9+7;

#define fi first
#define se second
#define lowbit(x) x & (-x)
#define endl '\n'
#define auto set<node> ::iterator

template <typename T>
struct BIT {
	const int n;
	vector<T> a;
	BIT(int n) :n(n), a(n){}
	void add(int x, T v) {
		for (int i = x; i <= n; i += i&-i) {
			a[i] += v;
		}
	}
	void rangeAdd(int x, int y, T v) {
		add(x, v);
		add(y+1, -v);
	}
	T sum(int x) {
		T ans = 0;
		for (int i = x; i > 0; i -= i & -i) {
			ans += a[i];
		}
		return ans;
	}
	T rangeSum(int l, int r) {
		return sum(r) - sum(l-1);
	}
};
struct node {
    int l, r;
    mutable ll val;
    node(int L, int R = -1, ll V = 0):l(L), r(R), val(V) {}
    bool operator < (const node &rhs) const {
        return l < rhs.l;
    }
};

set<node> odt;
auto split(int pos) {
    auto it = odt.lower_bound(node(pos));
    if (it != odt.end() && it->l == pos) return it;
    it--;
    int L = it->l, R = it->r;
    ll val = it->val;
    odt.erase(it);
    odt.insert(node(L, pos-1, val));
    return odt.insert(node(pos, R, val)).first;
}

vector<ll> add(N);
BIT<ll> bit(N);

void assign(int l, int r, int v) {
	auto itr = split(r + 1), itl = split(l);
	odt.erase(itl, itr);
	odt.insert(node(l, r, v));
	bit.rangeAdd(l, r, -add[v]);
}
void work(int l, int r) {
	// cout << l << ' ' << r << endl;
	auto itr = split(r + 1), itl = split(l);
	for (; itl != itr; ++itl) {
		// Perform Operations here 
		bit.rangeAdd(itl->l, itl->r, add[itl->val]);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m; cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		odt.insert(node(i,i,1));
	}

	while (m--) {
		string op; cin >> op;
		if (op == "Color") {
			int l, r, c; cin >> l >> r >> c;
			work(l, r);
			assign(l, r, c);
		} else if (op == "Add") {
			int c, x; cin >> c >> x;
			add[c] += x;
		} else {
			int x; cin >> x;
			auto itr = split(x + 1), itl = split(x);
			cout << bit.sum(x) + add[itl->val] << endl;
		}
	}

	return 0;
}