<span>模拟106 题解</span>

显然的区间dp。

断环成链，预处理出每个连续区间集合的元素个数。

然后直接dp就完了。

想了一些简单的贪心，然后都伪了。

所以考虑如何暴力$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 }