## 正负 1
#线段树 #排序 #贪心 #优先队列
首先，把所有空白的格子都涂成 $1$ 肯定是最可能满足条件的，如果这都不行肯定是无解的。但是题目要求的是字典序最小的解，然后看样例很显然是 $-1$ 排在 $1$ 前面的，并且对于越前面的一个数，可以填 $-1$ 一定会填上 $-1$，不行才会填 $1$。
所以我们可以对每一个空着的数首先均填上 $1$，然后从前往后依次枚举，看一看每一个数能否改成 $-1$，从前往后保证字典序最小。判断能否改成 $-1$ 就是 $\mathcal O(m)$ 枚举一下限制，如果每个包含了当前枚举的数的限制都比实际要求的 $k_i$ 大至少 $2$ 时，就可以把这个数改成 $-1$ 了。区间查询和、单点修改采用树状数组实现，时间复杂度 $\mathcal O(nm\log_2 n)$。
但是这样子会超时，所以我们需要转变思路。一个数想要变成 $-1$，需要满足 $m$ 个限制才可以，判断限制的过程很慢，因此我们反过来，每个数先暂时填上 $-1$，然后对于每个限制再将限制区域内的一些 $-1$ 改成 $1$ 即可。
修改成 $1$ 的 $-1$ 肯定是越往后越好，这样子才可以保证字典序最小。但是这样子就会引起一个问题，如果当前限制的区间不满足条件，我把它后端的若干个 $-1$ 改成 $1$ 了，但是下面又来了一个新的区间，在上个区间前面但有交汇，把交汇处的若干个 $-1$ 变成了 $1$，导致后面的区间实际的值比要求的 $k_i$ 要大，那么原来我们在区间后端改成的 $1$ 就没用了，反而使答案字典序不是最小，导致 WA。
所以我就想出了一个绝佳的策略，便是把所有限制离线下来然后按照 $r_i$ 从小到大的顺序处理，这样子先处理的区间就会影响后面的区间，使得不会修改多余的 $1$。
至于如何把区间尾端的若干个 $-1$ 改成 $1$，我使用一个线段树维护段内最大 $-1$ 下标，同时维护段内和和可以改成 $1$ 的 $-1$ 的数量。每次先判断能否满足条件，如果可以就循环找区间内最后一个 $-1$ 并修改。由于最多一共就 $n$ 的 $-1$ 给你修改，因此时间复杂度 $\mathcal O((\log_2 m+\log_2 n)m+n\log_2 n)$。
此外，这道题目使用优先队列贪心也是另外一种解法，但是我觉得我的解法更简单自然。
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int kMaxN = 1e5 + 5;
struct Node {
int id, sum, cnt; // 最大可改 -1 编号，目前实际的和，目前 -1 的数量
} tr[4 * kMaxN];
struct Limit {
int l, r, k;
} q[kMaxN];
int a[kMaxN], n, m;
void pushUp(int p) {
tr[p].id = max(tr[2 * p].id, tr[2 * p + 1].id);
tr[p].sum = tr[2 * p].sum + tr[2 * p + 1].sum;
tr[p].cnt = tr[2 * p].cnt + tr[2 * p + 1].cnt;
}
void modify(int p, int l, int r, int x, int val) {
if (l == r) {
if (!val) { // 暂时填 -1
tr[p] = Node {l, -1, 1};
} else {
tr[p] = Node {-1, val, 0};
}
return;
}
int m = (l + r) / 2;
if (x <= m) {
modify(2 * p, l, m, x, val);
} else {
modify(2 * p + 1, m + 1, r, x, val);
}
pushUp(p);
}
int querySum(int p, int l, int r, int s, int t) {
if (s <= l && r <= t) {
return tr[p].sum;
}
int m = (l + r) / 2, res = 0;
if (s <= m) {
res += querySum(2 * p, l, m, s, t);
}
if (m < t) {
res += querySum(2 * p + 1, m + 1, r, s, t);
}
return res;
}
int queryCnt(int p, int l, int r, int s, int t) {
if (s <= l && r <= t) {
return tr[p].cnt;
}
int m = (l + r) / 2, res = 0;
if (s <= m) {
res += queryCnt(2 * p, l, m, s, t);
}
if (m < t) {
res += queryCnt(2 * p + 1, m + 1, r, s, t);
}
return res;
}
int queryId(int p, int l, int r, int s, int t) {
if (s <= l && r <= t) {
return tr[p].id;
}
int m = (l + r) / 2, res = -1;
if (s <= m) {
res = max(res, queryId(2 * p, l, m, s, t));
}
if (m < t) {
res = max(res, queryId(2 * p + 1, m + 1, r, s, t));
}
return res;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
modify(1, 1, n, i, a[i]);
if (!a[i]) {
a[i] = -1;
}
}
for (int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r >> q[i].k;
}
sort(q + 1, q + m + 1, [](const Limit &a, const Limit &b) {
return a.r < b.r;
});
bool ans = 1;
for (int i = 1; i <= m; i++) {
int sum = querySum(1, 1, n, q[i].l, q[i].r);
int cnt = queryCnt(1, 1, n, q[i].l, q[i].r);
if (sum + 2 * cnt < q[i].k) {
ans = 0;
break;
}
while (sum < q[i].k) {
int p = queryId(1, 1, n, q[i].l, q[i].r);
modify(1, 1, n, p, a[p] = 1);
sum += 2;
}
}
if (!ans) {
cout << "Impossible\n";
return 0;
}
for (int i = 1; i <= n; i++) {
cout << a[i] << ' ';
}
return 0;
}
```
## 随机左移
#状压dp #组合数学
最开始我想到的是反过来操作，把 $p$ 进行 $m$ 次前缀循环右移操作，最后变成 $1\sim n$ 的排列，但是后来我去写第三题了，这题也没有继续想，代码都没有写。
其实对于 $n\le 5,m\le 5000$ 的 $10$ 分数据，由于排列只有 $n!=120$ 种，实际上可以直接做一个 $\mathcal O(n!\times m)$ 的 dp 模拟操作的，但是我没有写。。。
## 序列变换
#线段树
按照正常人的操作来说，终止状态应该是只有一个的。所以我在这个基础之上搞了非常多的暴力、式子但是最后都壮烈牺牲了。
首先这道题目有单点修改和区间查询，区间查询虽然需要进行一连串的操作，但是应该是有规律可以找的。于是我就最开始瞎写了一个式子，然后样例都过不了……后面我又改进了式子。令 $k$ 为 $[l,r)$ 中最后一个偶数下标，如果没有答案为 $0$，有的话答案为 $k-l+1$。我想的是先把 $k$ 通过操作一改成 $0$ 了之后用二号操作把前面的也搞成 $0$ 抛到后面，前面一个是 $0$ 了又能继续二操作，一直这么搞最后 $[l,k]$ 都是 $0$。但是对于 `1 1 2 2` 的数据，当进行一、二操作之后变为 `1 0 0 5` 后，此时把 $1$ 抛到后面仍然只有 $2$ 个 $0$，所以我又进行了优化，如果 $[l,k]$ 中有 $d$ 个奇数的话，答案就是 $k-l+1-d$，但是因为不太清楚的原因 WA 了。
然后我就没有渴望 AC 了，转去写暴力。最开始我写的是线性往后枚举每一个元素，依次对该元素进行两种操作，但是会比标准答案小。XBC 的方法是不停地循环，直到无法进行任何操作，但是我没写这一步，遗憾炸裂，进行多次小修改了之后仍然是 WA。不停循环的时间复杂度是 $\mathcal O(n^2q)$ 的，因为最多只会进行 $n$ 次循环，可以通过 $15$ 分。
## 删除线段
#状压dp #线段树
首先我想到了状压，把当前还剩下哪些线段状压起来，时间复杂度 $\mathcal O(n^2n)$，可以通过 $5$ 分，然后我就不会了。主要是不知道如何让状态脱离对剩下线段的依赖，贪心我也想不到一个好的策略，于是就挂分了。
## 总结
总分：$100+0+0+5=105$。
首先我太菜了，后三题都不会。但是我暴力打的也不行，具体来说是第二题应该打的 $10$ 分没有写，然后第三题暴力循环 $15$ 分没有注意到，最后最后一题没有过多的思考只有 $5$ 分，下次应该注意暴力奇技淫巧的使用，正确获得更多暴力分。