A. 合并集合
显然的区间dp。
断环成链，预处理出每个连续区间集合的元素个数。
然后直接dp就完了。
B. climb
想了一些简单的贪心，然后都伪了。
所以考虑如何暴力$O(n^2)$来做这个题。
枚举最终用来跳最后一步的药丸，显然前面的药丸可以按$a_i-b_i$排序。
然后考虑如何优化这个过程，问题在于如何判断溺水的情况。
溺水的情况只出现在$a_i-b_i$的前缀和小于等于$c_i$的前缀和。
然而对于单个元素的删除添加，很多元素的下标会出现移位，然后就很难搞。实际上并没有很多，是我弱智了
一个方法是线段树分治，首先对所有的药丸按$a_i-b_i$从大到小排序。
$solve(l,r)$表示用来跳最后一步的药丸在$(l,r)$范围内，已经考虑其它状态。
这个做法的好处在于，当$(l,r)$确定，除掉这个区间内每个药丸的排名也是确定的。
维护两棵线段树，下标为排名，
其中第一棵维护$a_i-b_i-c_i$前缀和的最小值，第二棵维护$a_i-b_i$前缀和的最大值。
递归$solve(mid+1,r)$之前，将$[l,mid]$之间的贡献统计，暴力求出范围内的前缀和，之后区间加$l-1$前缀和的值。
同理递归$solve(l,mid)$之前，将$[mid+1,r]$之间的贡献统计，暴力求出范围内的前缀和，更新$[r+1,n]$之间元素的值。
当递归到$l=r$，可以现在第一棵线段树上二分确定不会溺水的边界，再在第二棵线段树上二分确定最早可以跳出的时间，更新最终答案就好了。
虽然分治套线段树，但是这个做法的复杂度是$O(nlogn)$的。
因为$solve$函数显然只会调用$n$次，对于每次调用：
在线段树上确定区间是$log$复杂度的，因为线段树集合划分的性质，之后暴力递归到叶子节点是与长度线性相关的。
对于最终$l=r$，两次二分都在线段树上实现，所以复杂度也是正确的。
考场上打了$4K$代码，一遍过对拍。
起初有两处导致复杂度$O(nlog^2)$的地方，最终一步步改到了$O(nlogn)$，打起来确实很爽。
然而实际上我的做法并没有什么必要，因为邻项的修改只会更改一位上的值，普通线段树也可以实现。
1 #include<algorithm>
2 #include<iostream>
3 #include<cstdio>
4 #define ll long long
5 #define cri const register
6 #define lch p<<1
7 #define rch p<<1|1
8 using namespace std;
9 const int N=1e5+7;
10 const int inf=0x3f3f3f3f;
11 struct YaoWan{
12 int a,b;
13 }med[N];
14 int n,ans=inf;
15 long long lim,pre[N],w[N];
16 struct node{
17 ll val[2],lzy[2];//0表示最小值 减pre之后的
18 }s[N<<2];//1表示最大值 不减pre的
19 inline void down(cri int p){
20 if(s[p].lzy[0]){
21 s[lch].val[0]+=s[p].lzy[0];
22 s[rch].val[0]+=s[p].lzy[0];
23 s[lch].lzy[0]+=s[p].lzy[0];
24 s[rch].lzy[0]+=s[p].lzy[0];
25 s[p].lzy[0]=0;
26 }
27 if(s[p].lzy[1]){
28 s[lch].val[1]+=s[p].lzy[1];
29 s[rch].val[1]+=s[p].lzy[1];
30 s[lch].lzy[1]+=s[p].lzy[1];
31 s[rch].lzy[1]+=s[p].lzy[1];
32 s[p].lzy[1]=0;
33 }
34 }
35 inline void up(cri int p){
36 s[p].val[0]=min(s[lch].val[0],s[rch].val[0]);
37 s[p].val[1]=max(s[lch].val[1],s[rch].val[1]);
38 }
39 void build(cri int p,cri int l,cri int r){
40 if(l==r) return s[p].val[0]=-pre[l],void();
41 int mid=l+r>>1;
42 build(lch,l,mid);
43 build(rch,mid+1,r);
44 up(p);
45 }
46 void toadd(cri int p,cri int fl,cri int l,cri int r,cri int L,cri int R,cri int f){
47 if(L==R) return s[p].val[0]+=w[L-l+fl]*f,s[p].val[1]+=w[L-l+fl]*f,void();
48 down(p);
49 int mid=L+R>>1;
50 if(l<=mid) toadd(lch,fl,l,r,L,mid,f);
51 if(r>mid) toadd(rch,fl,l,r,mid+1,R,f);
52 up(p);
53 }
54 void modify(cri int p,cri int l,cri int r,cri ll val,cri int L,cri int R){
55 if(L>=l&&R<=r) return s[p].lzy[0]+=val,s[p].lzy[1]+=val,s[p].val[0]+=val,s[p].val[1]+=val,void();
56 down(p);
57 int mid=L+R>>1;
58 if(l<=mid) modify(lch,l,r,val,L,mid);
59 if(r>mid) modify(rch,l,r,val,mid+1,R);
60 up(p);
61 }
62 ll query(cri int p,cri int l,cri int r,cri int L,cri int R){
63 if(L>=l&&R<=r) return s[p].val[1];
64 down(p);
65 int mid=L+R>>1;
66 if(r<=mid) return query(lch,l,r,L,mid);
67 if(l>mid) return query(rch,l,r,mid+1,R);
68 return max(query(lch,l,r,L,mid),query(rch,l,r,mid+1,R));
69 }
70 int ask(cri int p,cri ll add,cri int L,cri int R){
71 if(L==R) return L;
72 down(p);
73 int mid=L+R>>1;
74 if(s[lch].val[1]+add>=lim) return ask(lch,add,L,mid);
75 else return ask(rch,add,mid+1,R);
76 }
77 int find(cri int p,cri int L,cri int R){
78 if(L==R) return L;
79 down(p);
80 int mid=L+R>>1;
81 if(s[lch].val[0]<=0) return find(lch,L,mid);
82 else return find(rch,mid+1,R);
83 }
84 void solve(cri int l,cri int r){
85 ll val;
86 if(l==r){
87 if(l!=1&&l!=n){
88 val=query(1,l-1,l-1,1,n-1);
89 modify(1,l,n-1,val,1,n-1);
90 }
91 register int fr=n-1;
92 if(s[1].val[0]<=0) fr=find(1,1,n-1)-1;
93 if(fr&&query(1,1,fr,1,n-1)+med[l].a>=lim) ans=min(ans,ask(1,med[l].a,1,n-1)+1);
94 if(l!=1&&l!=n) modify(1,l,n-1,-val,1,n-1);
95 return ;
96 }
97 cri int mid=l+r>>1;
98 w[mid]=0;
99 for(register int i=mid+1;i<=r;++i) w[i]=w[i-1]+med[i].a-med[i].b;
100 toadd(1,mid+1,mid,r-1,1,n-1,1);
101 if(r!=n) modify(1,r,n-1,w[r],1,n-1);
102 solve(l,mid);
103 w[mid]=0;
104 for(register int i=mid+1;i<=r;++i) w[i]=w[i-1]+med[i].a-med[i].b;
105 toadd(1,mid+1,mid,r-1,1,n-1,-1);
106 if(r!=n) modify(1,r,n-1,-w[r],1,n-1);
107
108 w[l-1]=0;
109 for(register int i=l;i<=mid;++i) w[i]=w[i-1]+med[i].a-med[i].b;
110 toadd(1,l,l,mid,1,n-1,1);
111 if(l!=1){
112 val=query(1,l-1,l-1,1,n-1);
113 modify(1,l,mid,val,1,n-1);
114 }
115 solve(mid+1,r);
116 w[l-1]=0;
117 for(register int i=l;i<=mid;++i) w[i]=w[i-1]+med[i].a-med[i].b;
118 toadd(1,l,l,mid,1,n-1,-1);
119 if(l!=1) modify(1,l,mid,-val,1,n-1);
120 }
121 inline bool cmp(const YaoWan &x,const YaoWan &y){
122 return x.a-x.b>y.a-y.b;
123 }
124 inline int read(register int x=0,register char ch=getchar()){
125 for(;!isdigit(ch);ch=getchar()) ;
126 for(; isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
127 return x;
128 }
129 int main(){
130 freopen("climb.in","r",stdin);
131 freopen("climb.out","w",stdout);
132 n=read(); scanf("%lld",&lim);
133 for(int i=1;i<=n;++i){
134 med[i].a=read(); med[i].b=read();
135 if(med[i].a>=lim) return printf("%d\n",1),0;
136 }
137 for(int i=1;i<=n;++i) pre[i]=pre[i-1]+read();
138 if(n==1) return puts("-1"),0;
139 sort(med+1,med+n+1,cmp);
140 build(1,1,n-1);
141 solve(1,n);
142 printf("%d\n",ans==inf?-1:ans);
143 return 0;
144 }
T2
C. coin
当存在一种方案，使得二者共同努力可以达到全部硬币正面朝上，答案显然不会低于2。
否则答案只与行数+列数的奇偶性有关。
所以首先判局面是否可以转化到全部硬币正面朝上：
对于每一个硬币，
如果它是正面，那么行翻转对应列翻转，行不翻转对应列不翻转。
如果它是反面，那么行翻转对应列不翻转，行不翻转对应列翻转。
发现这个东西可以用拓展域并查集简单维护，
如果最终态存在矛盾，那么无解，否则存在至少一组解。
之后考虑先手是否必胜。
对于每一个集合，如果该集合对应着偶数个翻转，其对立集合对应着偶数个翻转，那么显然可以忽略这个集合。
其余的两个情况是：
该集合对应着奇数个翻转，其对立集合对应着偶数个翻转。
该集合对应着奇数个翻转，其对立集合对应着奇数个翻转。
所以只要考虑后两种情况，设$dp(i,j)$表示前一种状态有$i$个，后一种状态有$j$个。
显然$dp(0,0)=0$,对应先手必败。
有转移
$dp(i,j)|=!dp(i,j-1)$，表示简单选择一个两面都是奇数的集合，将其转化为没用的偶数集合。
$dp(i,j)|=!dp(i-1,j)$，表示选择一个奇偶面集合的奇面，将其转化为没用的偶数集合。
$dp(i,j)|=!dp(i-1,j+1)$，表示选择一个奇偶面集合的偶面，那么多一个奇数集合。