感觉这天一整天有点头昏脑涨，晚上吃完饭就睡过去了连博客也没写
T1大判断，T3看上去比较裸的二分完线段树优化DP，就T2看上去比较有意思，没想到最后正解还要用什么积分orz。最后没交，补一道T3，其他没什么打的欲望。
T3.序列
题目大意：给定正整数m和两个长度为n的序列对(ai,bi)，要求把序列分成若干段，满足：1.若i<j且i与j不在同一段，则bi>aj；2.每一段a的最大值之和不超过m。要求划分方案满足条件的同时每一段b的和的最大值最小。（n<=100000）
思路：条件1说明只有前i个b的最小值大于后n-i个a的最大值，i才能作为段的末尾，预处理一下可以把不能分段的缩成一个点（新的a取段中a最大值，b取段中b的和），这样我们之后就不用考虑条件1了。我们二分答案，DP求出每一段b之和都不超过当前二分出的答案时最小的各段a最大值之和。f[i]表示序列前i个分成若干段最小的a最大值之和，则f[i]=min(f[j]+max(a[i+1]~a[j]))（sum(b[i+1]~b[j])<=当前二分的答案），可以用线段树大力维护，总复杂度O(nlogn^2)。
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define ll long long inline ll read() { ll x;char c; while((c=getchar())<'0'||c>'9'); for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return x; } #define MN 100000 #define INF (1LL<<60) #define L (x<<1) #define R (x<<1^1) int n,a[MN+5],ma[MN+5]; ll b[MN+5],sb[MN+5],mb[MN+5],f[MN+5]; struct node{int l,r,mx,mk;ll mf,ms;}t[MN*4+5]; inline void up(int x) { t[x].mx=max(t[L].mx,t[R].mx); t[x].mf=min(t[L].mf,t[R].mf); t[x].ms=min(t[L].ms,t[R].ms); } inline void mark(int x,int z) { t[x].mx=t[x].mk=z; t[x].ms=t[x].mf+z; } #define down(x) if(t[x].mk)mark(L,t[x].mk),mark(R,t[x].mk),t[x].mk=0 void build(int x,int l,int r) { t[x].l=l;t[x].r=r;t[x].mk=0; if(l==r){t[x].mx=0;t[x].mf=t[x].ms=INF;return;} build(L,l,l+r>>1);build(R,(l+r>>1)+1,r);up(x); } void renew1(int x,int k,ll f) { if(t[x].l==t[x].r){t[x].mf=t[x].ms=f;return;} down(x);renew1(k>t[x].l+t[x].r>>1?R:L,k,f);up(x); } void renew2(int x,int r,int a) { if(t[x].mx<a&&t[x].r==r){mark(x,a);return;} if(t[x].l==t[x].r)return;down(x); int mid=t[x].l+t[x].r>>1; if(r<=mid)renew2(L,r,a); else if(t[R].mx>=a)renew2(R,r,a); else renew2(L,mid,a),renew2(R,r,a); up(x); } ll query(int x,int l,int r) { if(t[x].l==l&&t[x].r==r)return t[x].ms; down(x); int mid=t[x].l+t[x].r>>1; if(r<=mid)return query(L,l,r); if(l>mid)return query(R,l,r); return min(query(L,l,mid),query(R,mid+1,r)); } ll check(ll x) { int i; build(1,1,n);renew1(1,1,0); for(i=1;i<=n;++i) { renew1(1,i,f[i-1]); renew2(1,i,a[i]); f[i]=query(1,lower_bound(sb,sb+n+1,sb[i]-x)-sb+1,i); } return f[n]; } int main() { freopen("sequence.in","r",stdin); freopen("sequence.out","w",stdout);int i,j,k,x;ll m,l=0,r,mid,ans; n=read();m=read(); for(mb[0]=INF,i=1;i<=n;++i)a[i]=read(),mb[i]=min(mb[i-1],b[i]=read()); for(i=n;i;--i)ma[i]=max(ma[i+1],a[i]); for(i=1,k=0;i<=n;i=j) { for(j=i,x=r=0;j==i||mb[j-1]<=ma[j];++j)x=max(x,a[j]),r+=b[j]; a[++k]=x;b[k]=r; } for(n=k,i=1;i<=n;++i)sb[i]=sb[i-1]+b[i],l=max(l,b[i]); for(r=INF;l<=r;)if(check(mid=l+r>>1)<=m)ans=mid,r=mid-1;else l=mid+1; cout<<ans; fclose(stdin);fclose(stdout);return 0; }