明显求个l[i],r[i]，一开始想用二分，结果一直WA，以为自己二分打错了，想用lowerbound结果一看STL的解释必须是上升序列。。那就用单调站来维护咯。。
#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; int n,m; const int N=1e5+5; int a[N],b[N],c[N],stack[N],top,l[N],r[N]; typedef long long ll; int main() { scanf("%d",&n); fo(i,1,n)scanf("%d%d",&a[i],&b[i]),l[i]=1,r[i]=n; top=0; fo(i,1,n) { while (top&&a[stack[top]]<a[i]) { r[stack[top]]=i-1; --top; } stack[++top]=i; } memset(stack,0,sizeof(stack)); top=0; fd(i,n,1) { while (top&&a[stack[top]]<a[i]) { l[stack[top]]=i+1; --top; } stack[++top]=i; } fo(i,1,n) { c[l[i]-1]+=b[i]; c[r[i]+1]+=b[i]; } int ans=0; fo(i,1,n)ans=max(ans,c[i]); printf("%d\n",ans); }