暴力打满直接rk3？
T1 Game
想了一万种贪心和两万种$hack$。
可以先用最显然的贪心求出最高得分是多少。（从小到大用最小的大于$b_i$的$a$得分）
然后用一棵权值线段树维护值域内$a$和$b$的个数，发现两个儿子合并对答案的贡献就是$min(a_r,b_l)$。（要用大的$a$对小的$b$）于是最优分数可以直接在建树时算出。
对每个位置考虑放什么数可以令最优分数不下降，发现它是单调的。于是可以二分。具体是把$mid$值删去后检查一遍最优分数有无下降。
对$a_mid$是否大于$b_i$要分类讨论，如果$a_mid$大于$b_i$，检查时要将最终答案$+1$，因为当前位置会贡献$1$。
找到该位答案后把$a_mid$和$b_i$删掉，对最优答案$-1$，使它不会对之后的答案产生影响。
挺妙的，在线段树操作中自动修改最优分数。
$code:$
1 #include<bits/stdc++.h>
2 #define ld rt<<1
3 #define rd (rt<<1)|1
4 #define rin register signed
5 using namespace std;
6 const int NN=1e5+5;
7 int n,a[NN],pre[NN],b[NN],ans[NN],an[NN],bota[NN],k,it,botb[NN],tk;
8 inline int read(){
9 int x=0,f=1; char ch=getchar();
10 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
11 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
12 return x*f;
13 }
14 inline void write(int x){
15 char ch[20]; int len=0;
16 if(x<0) putchar('-'), x=~x+1;
17 do{
18 ch[len++]=x%10+(1<<5)+(1<<4);
19 x/=10;
20 }while(x);
21 for(rin i=len-1;i>=0;--i) putchar(ch[i]);
22 return;
23 }
24 struct segment_tree{
25 int suma[NN<<2],sumb[NN<<2],l[NN<<2],r[NN<<2];
26 void pushup(int rt){
27 int tmp=min(suma[rd],sumb[ld]); tk+=tmp;
28 suma[rt]=suma[ld]+suma[rd]-tmp;
29 sumb[rt]=sumb[ld]+sumb[rd]-tmp;
30 }
31 void build(int rt,int opl,int opr){
32 l[rt]=opl; r[rt]=opr;
33 if(opl==opr){
34 suma[rt]=bota[opl];
35 sumb[rt]=botb[opl];
36 return;
37 }
38 int mid=opl+opr>>1;
39 build(ld,opl,mid);
40 build(rd,mid+1,opr);
41 pushup(rt);
42 }
43 void update(int rt,int pos){
44 if(l[rt]==r[rt]){
45 suma[rt]=bota[pos];
46 sumb[rt]=botb[pos];
47 return;
48 }
49 int mid=l[rt]+r[rt]>>1;
50 tk-=min(sumb[ld],suma[rd]);
51 if(pos<=mid) update(ld,pos);
52 else update(rd,pos);
53 pushup(rt);
54 }
55 }s;
56 bool check(int mid,int op){
57 bota[mid]--; s.update(1,mid);
58 int res=tk+op;
59 bota[mid]++; s.update(1,mid);
60 return res==k;
61 }
62 signed main(){
63 n=read(); rin atmp=0;
64 for(rin i=1;i<=n;++i){ b[i]=read(); botb[b[i]]++; }
65 for(rin i=1;i<=n;++i){ int t=read(); bota[t]++; it=max(it,t); }
66 s.build(1,1,it); k=tk;
67 for(rin i=1;i<=n;i++){
68 botb[b[i]]--; s.update(1,b[i]);
69 while(!bota[it]&&it) it--;
70 int l=b[i]+1,r=it,pos=0;
71 while(l<=r){
72 int mid=l+r>>1;
73 if(check(mid,1)) l=mid+1, pos=mid;
74 else r=mid-1;
75 }
76 if(!pos){
77 l=0; r=b[i];
78 while(l<=r){
79 int mid=l+r>>1;
80 if(check(mid,0)) l=mid+1, pos=mid;
81 else r=mid-1;
82 }
83 }
84 else k--;
85 bota[pos]--; s.update(1,pos); ans[i]=pos;
86 }
87 for(int i=1;i<=n;i++) write(ans[i]), putchar(' ');
88 putchar('\n');
89 return 0;
90 }
T1
T2 Time
是个贪心。每次找到序列中的最小值，把它移到左或右端点，哪近移哪。貌似可以分治。
事实上每个点移到它成为最小值时端点对答案的贡献就是它左/有大于它数的个数。树状数组即可。
（到现在我也不知道求逆序对为什么假了
$code:$
1 #include<bits/stdc++.h>
2 #define ld rt<<1
3 #define rd (rt<<1)|1
4 using namespace std;
5 const int NN=1e5+5;
6 int n,p[NN],ans,c[NN],pre[NN],suf[NN];
7 inline int read(){
8 int x=0,f=1; char ch=getchar();
9 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
10 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
11 return x*f;
12 }
13 inline void write(int x){
14 char ch[20]; int len=0;
15 if(x<0) putchar('-'), x=~x+1;
16 do{
17 ch[len++]=x%10+(1<<5)+(1<<4);
18 x/=10;
19 }while(x);
20 for(int i=len-1;i>=0;i--) putchar(ch[i]);
21 return;
22 }
23 inline int lowbit(int x){ return x&(-x); }
24 inline void insert(int pos){
25 while(pos<100000){
26 c[pos]++;
27 pos+=lowbit(pos);
28 }
29 }
30 inline int query(int pos){
31 int res=0;
32 while(pos){
33 res+=c[pos];
34 pos-=lowbit(pos);
35 }
36 return res;
37 }
38 signed main(){
39 n=read();
40 for(int i=1;i<=n;i++)
41 p[i]=read();
42 for(int i=1;i<=n;i++){
43 pre[i]=query(100000)-query(p[i]);
44 insert(p[i]);
45 }
46 memset(c,0,sizeof(c));
47 for(int i=n;i;i--){
48 suf[i]=query(100000)-query(p[i]);
49 insert(p[i]);
50 }
51 for(int i=1;i<=n;i++)
52 ans+=min(pre[i],suf[i]);
53 write(ans); putchar('\n');
54 return 0;
55 }
T2
T3 Cover
是道神题。
暴力$DP$挺简单的，定义$f_{i,j}$为$i$子树中最多覆盖$j$层，有：
$f_{i,j}=max(max(\sum f_{son,j-1}+w_i,\sum f_{son,j}),f_{i,j-1}))$