写在前面：
废话
坏坏坏坏坏坏坏，假假假假假假假，唐唐唐唐唐唐唐，爆爆爆爆爆爆爆，蒻蒻蒻蒻蒻蒻蒻！！！！111
P
推歌
《幸福安心委员会》
どうして みんなが幸せなの？
为什么 大家都这么幸福呢?
この世界のこと 闻きたいって、知りたいって
关于这个世界的事 想要明白更多 知道更多
水辺の公园で みんなが耳を済ませて
在水边的公园 请各位侧耳倾听
わくわくするね ねぇ、オンディーヌ？
内心雀跃不已 呐 Ondine?()
ハイハーイ！
来唷来-唷!
さあさあ、みなさん 教えてあげまーす！
看这里 各位 我来告诉你们!
みんなが気になっていること 疑问に思ってること
大家在意的事情 抱持疑惑的事情
ぜーんぶ 教えてあげまーす！
全—部 都会帮你们解答!
えー、みなさんが 幸福なのは义务なんです。
没错喔各位 所谓的幸福就是义务
幸せですか？ 义务ですよ？果たしてますか?
觉得幸福吗? 这是义务唷? 你有好好履行吗?
我々、幸福安心委员会は みなさまの幸せを愿い そして、支えまーす！
我们 幸福安心委员会 为各位祈求幸福 然後一直 支—持各位！
幸福なのは义务なんです
所谓的幸福就是义务
幸福なのは义务なんです
所谓的幸福就是义务
幸福なのは义务なんです
所谓的幸福就是义务
幸せですか？义务ですよ
觉得幸福吗? 这是义务唷
幸福なのは义务なんです
所谓的幸福就是义务
幸福なのは义务なんです
所谓的幸福就是义务
幸福なのは义务なんです
所谓的幸福就是义务
幸せですか？义务ですよ
觉得幸福吗? 这是义务唷
ですから、安心して义务を果たすように！
因此 务必安心完成你们的义务！
みなさまの幸せが 我々の幸せ
因为各位的幸福 就是我们的幸福
幸せですか？义务ですよ？果たしてますか？
觉得幸福吗? 这是义务唷 你有好好履行吗?
幸せじゃないなら…
如果不幸福的话 那就...
绞首 斩首 铳杀 釜ゆで 溺死 电気
绞刑 斩首 枪毙下油锅 溺死 电刑
火炙り 生き埋め 薬杀 石打ち 锯 磔
火烤 活埋 毒杀 石刑 锯子 凌迟
好きなのを选んでね♪
选一个喜欢的吧♪
ハイハーイ！
来唷来-唷!
さあさあ、みなさん幸せだけが満ちてまーす！
看这里 各位 只感到满满的幸福唷!
不安とか不満、なにひとつないでしょー？
不安和不满什么的 完全没有对吧?
コワーイ、恐いわー
好—可怕 好可怕唷—
幸せすぎて、恐いわー。
因为太过幸福 而感到害怕
—间奏—
ホントに みんなが 幸せなの？
各位真的 感到幸福吗?
この世界の外 行きたいって、逃げたいって
这个世界之外 好想前往 好想逃离
水辺の公园で みんなが耳を塞いで
在水边的公园 大家塞住耳朵
ビクビクしてた ねぇ、ウンディーネ？
感到害怕发抖 呐 Undine?()
ハイハーイ！
来唷来-唷!
さあさあ、みなさん 死にましたー！
看这里 各位 已经死掉了—!
オンディーヌをふった骑士は 死にましたー！
抛弃了Ondine的骑士 已经死掉了—！
葬仪に出るなら、向こうに并べ！
要出席葬礼的 都给我去那边排队!
それ以外は 幸せに暮らせ！以上
其他的 给我幸福活下去! 就这些
幸福なのは义务なんです
所谓的幸福就是义务
幸福なのは义务なんです
所谓的幸福就是义务
幸福なのは义务なんです
所谓的幸福就是义务
幸せですか？义务ですよ
觉得幸福吗? 这是义务唷
幸福なのは义务なんです
所谓的幸福就是义务
幸福なのは义务なんです
所谓的幸福就是义务
幸福なのは义务なんです
所谓的幸福就是义务
幸せですか？义务ですよ
觉得幸福吗? 这是义务唷
义务なんです 义务ですよ？
是义务 是义务唷?
义务なんです 幸福なのは义务なんです
是义务 所谓的幸福就是义务
义务なんです 义务ですよ？
是义务 是义务唷?
义务なんです
是义务
幸せじゃないなら 死ね
如果不幸福的话 那就去死吧
T1 最⻓不下降⼦序列
Bonus：挑战不使用数组完成本题。（好像串台了）
题目描述：
小 W 有一个长度为 \(n\) 的序列 \(a_1,a_2,\cdots,a_n\) ，且 \(a_i\) 的取值只可能为 \(1\) 或 \(2\) 。
现在，你可以任意选择该序列的一个区间进行翻转操作，但你只能翻转一次。
小 \(W\) 希望执行操作之后，整个序列的最长不下降子序列长度最大。请你求出这个最大值。
样例 #1
样例输入 #1
4
1 2 1 2样例输出 #1
4
样例解释 #1
翻转区间 \([2, 3]\) ，整个序列变为 \(1, 1, 2, 2\) ，自然答案是 \(4\) 。
样例 #2
样例输入 #2
10
1 1 2 2 2 1 1 2 2 1样例输出 #2
9
样例解释 #2
翻转区间 \([3, 7]\) 。
数据规模与约定
对于前 \(10%\) 的数据，保证 \(a_i=1\) 。
对于前 \(30%\) 的数据，保证 \(n ≤50\) 。
对于前 \(70%\) 的数据，保证 \(n ≤2000\) 。
对于所有数据，保证 \(1 ≤n ≤10^6\) ，\(a_i \in \{1,2\}\)。
Solve：
首先看到“最长不下降子序列”的字样，于是花费 \(1ms\) 就能想到是 \(DP\) ，但是要翻转区间，我不会。于是可以打出 \(n^2\) 的 \(DP\) ，但是泰镗辣，于是写一个聪明一点的 \(DP\) ：设 \(f_{i,0/1}\) 表示到第 \(i\) 位，末位是 \(1\) 与末位是 \(0\) 的最长不下降子序列长度，于是再用 \(1ms\) 就可以写完，但是我还是不会（唐坏了！！！）。
于是我们使用注意力（赛时没有注意力怎么办？赛后什么都有了，什么都有了！！！【确信】），发现，当你试图翻转一次区间，使得选出的子序列变成不下降子序列时，可以成功的子序列一定是形如 \(1,\dots1,2,2,\dots2,1,1,\dots1,2,2,\dots2\) 的。 \(eg\) ：
于是设 \(f_{i, j}\) 表示前 \(i\) 个数选出的子序列到了第 \(j\) 段（显然 \(j≤4\) 才合法）的最长长度，然后 \(O(n)\) 递推，但是 \(f\) 的第一位太唐了于是砍掉，然后就只剩下小于等于 \(4\) 的 \(j\) ，于是 Bonus：挑战不使用数组完成本题。 （你谷昨天入门赛乱入），就没了。
Code：
#include <bits/stdc++.h>
using namespace std;
int a, b, c, d, n, x;
int main(){freopen("sequence.in", "r", stdin);freopen("sequence.out", "w", stdout);scanf("%d", & n);for(int i = 1; i <= n; i ++){scanf("%d", & x);if(x & 1)a ++, c ++;elseb ++, d ++;b = max(b, a);c = max(c, b);d = max(d, c);}printf("%d", d);return 0;
}
T2 美⻝节（[KOI 2022 Round 2] 食事计划）
怕变成肝硬化の逝世计划，鳝凉的出题人更改了题目名称
Solve：
· 判无解：如果序列中出现次数最多的数 \(>\lceil\frac{n}{2}\rceil\) 那么无解，反之一定有解；
· 如果序列中的众数 \(=\lceil\frac{n}{2}\rceil\) ，那么接下来必须输出一个众数出来（不然就无解了）；
· 输出的序列要求字典序最小，于是每次输出都找合法的最小的位置即可；
· 别忘了输出之后将该数出现的次数减一；
·输出是空格不是换行（怎么会有人像肝硬化一样唐¿）；
·没了。然后就是肝硬化的线段树调了一辈子啊啊啊啊啊啊啊（再让我调一下午线段树就给我 \(RP++\) 好不好！！！）。
Code：
#include <bits/stdc++.h>
using namespace std;
#define lson (root << 1)
#define rson (root << 1 | 1)
const int _ = 300010, inf = 999999999;
int n, a[_], tot[_], p[_], cun, bfr, nxt[_], h, ans[_];
struct rain{struct hhh{int l, r, v, c, t;}tree[_ << 2];inline void pushup(int root){if(tree[lson]. c <= tree[rson]. c){tree[root]. c = tree[lson]. c;tree[root]. v = min(tree[rson]. c, tree[lson]. v);}else{tree[root]. c = tree[rson]. c;tree[root]. v = min(tree[lson]. c, tree[rson]. v);}if(tot[tree[lson]. t] == tot[tree[rson]. t]){if(p[tree[lson]. t] < p[tree[rson]. t]){tree[root]. t = tree[lson]. t;}else{tree[root]. t = tree[rson]. t;}}else if(tot[tree[lson]. t] > tot[tree[rson]. t]){tree[root]. t = tree[lson]. t;}else{tree[root]. t = tree[rson]. t;}return ;}inline void build(int root, int l, int r){tree[root]. l = l, tree[root]. r = r;if(l == r){tree[root]. c = p[l] ? p[l] : inf;tree[root]. v = inf;tree[root]. t = l;return ;}int mid = (l + r) >> 1;build(lson, l, mid);build(rson, mid + 1, r);pushup(root);return ;}inline void update(int root, int plc){if(tree[root]. l == tree[root]. r){tree[root]. c = p[tree[root]. l] ? p[tree[root]. l] : inf;return ;}int mid = (tree[root]. l + tree[root]. r) >> 1;if(plc <= mid){update(lson, plc);}else{update(rson, plc);}pushup(root);return ;}inline int query(int root){if(tot[tree[root]. t] > ((cun + 1) >> 1)){return - 1;}if(tot[tree[root]. t] == ((cun + 2) >> 1)){return tree[root]. t == bfr ? (a[tree[root]. c] == bfr ? tree[root]. v : tree[root]. c) : p[tree[root]. t];}return a[tree[root]. c] == bfr ? tree[root]. v : tree[root]. c;}
}H;
int main(){freopen("food.in","r",stdin);freopen("food.out","w",stdout);scanf("%d", & n);for(int i = 1; i <= n; i ++){scanf("%d", & a[i]);}for(int i = n; i; i --){nxt[i] = p[a[i]];p[a[i]] = i;tot[a[i]] ++;}H. build(1, 1, n);cun = n;for(int i = 1; i <= n; i ++){h = H. query(1);if(h == - 1){printf("-1");goto rain;}printf("%d ", h);p[a[h]] = nxt[h];tot[a[h]] --;cun --;H. update(1, a[h]);bfr = a[h];}rain :return 0;
}
T3 字符串
不知道不知道赛时打了个马拉车（\(horse \underline{}pull\underline{} car\)）就跑， \(TTTTTLE\) 得很彻底。
T4 概率
我不会我不会我不会推柿子推柿子推柿子啊啊啊啊啊啊啊啊啊！！！！！！111
--