C. Trip to Saint Petersburg（线段树 区间包含 区间最大值以及位置）

http://codeforces.com/problemset/problem/1250/C

题意： 有多段区间，每段区间有价值$val$，你现在自己定义一个区间，其价值为：${\sum }_{val}-len\ast k$，求最大价值。

解析：

经典模型，从前往后枚举左端点，实时维护。

首先每个点花费k，所以初始化每个点-k，对于一段$[L,R]val$的区间，$a[R]+=val$，然后做前缀和就是初始数组。

假设到了第i个点，那么左端点小于x的区间$[L,R]val$，更新$[R+1,inf]$减去$val$。然后求$[i,inf]$的最大值，再加上$(i-1)\ast k$。

代码：

#include<bits/stdc++.h> using namespace std; #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) LL rd(){ LL ans=0; char last=' ',ch=getchar(); while(ch<'0' || ch>'9')last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; return ans; } #define rd rd() const int maxn=2e5+9; struct node{ int l,r,id;LL v; bool operator<(const node &A)const { return l<A.l; } }e[maxn]; int l[maxn],r[maxn];LL v[maxn]; LL sf[maxn]; LL mx[maxn<<2],laz[maxn<<2]; #define ls (rt<<1) #define rs (rt<<1|1) #define mid (l+r>>1) void build(int rt,int l,int r){ if(l==r){ return (void)(mx[rt]=sf[l]); } build(ls,l,mid); build(rs,mid+1,r); mx[rt]=max(mx[ls],mx[rs]); } void down(int rt){ if(laz[rt]){ laz[ls]+=laz[rt]; laz[rs]+=laz[rt]; mx[ls]+=laz[rt]; mx[rs]+=laz[rt]; laz[rt]=0; } } void update(int rt,int l,int r,int L,int R,LL val){ if(l>=L&&r<=R){ mx[rt]+=val; laz[rt]+=val; return; } down(rt); if(L<=mid)update(ls,l,mid,L,R,val); if(R>mid)update(rs,mid+1,r,L,R,val); mx[rt]=max(mx[ls],mx[rs]); } LL tmp; int pos; void query(int rt,int l,int r,int L,int R){ if(mx[rt]<=tmp)return; if(l>=L&&r<=R){ if(mx[rt]>tmp){ if(l==r){ tmp=mx[rt]; pos=l; return; } down(rt); if(L<=mid&&r>mid){ if(mx[ls]>mx[rs])query(ls,l,mid,L,R); else query(rs,mid+1,r,L,R); return; } if(L<=mid)query(ls,l,mid,L,R); if(R>mid)query(rs,mid+1,r,L,R); } return ; } down(rt); if(L<=mid)query(ls,l,mid,L,R); if(R>mid)query(rs,mid+1,r,L,R); } int main(){ int n=rd;LL k=rd; rep(i,1,2e5)sf[i]=-k; rep(i,1,n){ e[i].l=rd,e[i].r=rd,e[i].v=rd; e[i].id=i; sf[e[i].r]+=e[i].v; } rep(i,1,2e5)sf[i]+=sf[i-1]; build(1,1,2e5); sort(e+1,e+1+n); LL ans=0; int ansL,ansR; int L,R; int ar=1; rep(i,1,2e5){ while(ar<=n&&e[ar].l<i){ update(1,1,2e5,e[ar].r,2e5,-e[ar].v); ar++; } tmp=-2e18; query(1,1,2e5,i,2e5); if(tmp+(1ll*i-1)*k>ans){ ans=tmp+(1ll*i-1)*k; ansL=i,ansR=pos; } } if(ans==0){ puts("0"); return 0; } printf("%lld %d %d ",ans,ansL,ansR); vector<int>V; rep(i,1,n){ if(e[i].l>=ansL&&e[i].r<=ansR)V.push_back(e[i].id); } printf("%d\n",V.size()*1); for(auto p:V){ printf("%d ",p); } puts(""); }