题意：有一篇博客。一共有n个人，心中有他们期望该博客得到的赞数a[i]。当某个时刻该博客的获赞数a[i]，该人会使得赞数-1，当赞数=a[i]，不做任何改变。

对于1<=k<=n，询问1~k个人按一定的顺序给该博客从0开始点赞或点踩，该博客的最大获赞数。

-1e5<=a[i]<=1e5,n<=1e5。

标程：

#include
#define mid ((l+r)>>1)
using namespace std;
const int N=;
const int inf=0x3f3f3f3f;
int tag1[N<<],tag2[N<<],Max[N<<],Min[N<<],n,ax;

void build1(int k,int l,int r)
{
if (l==r) {Max[k]=l;return;}
build1(k<<,l,mid);build1(k<<|,mid+,r); Max[k]=max(Max[k<<],Max[k<<|]); } void build2(int k,int l,int r) { if (l==r) {Min[k]=l;return;} build2(k<<,l,mid);build2(k<<|,mid+,r); Min[k]=min(Min[k<<],Min[k<<|]); } void down1(int k) { if (tag1[k]) { tag1[k<<]+=tag1[k],tag1[k<<|]+=tag1[k]; Max[k<<]+=tag1[k],Max[k<<|]+=tag1[k]; tag1[k]=; } } void down2(int k) { if (tag2[k]) { tag2[k<<]+=tag2[k],tag2[k<<|]+=tag2[k]; Min[k<<]+=tag2[k],Min[k<<|]+=tag2[k]; tag2[k]=; } } void add1(int k,int l,int r,int x) { if (x<=l) {tag1[k]++;Max[k]++;return;} down1(k); if (x<=mid) add1(k<<,l,mid,x); add1(k<<|,mid+,r,x); Max[k]=max(Max[k<<],Max[k<<|]); } void add2(int k,int l,int r,int x) { if (r<=x) {tag2[k]++;Min[k]++;return;} down2(k); if (x>mid) add2(k<<|,mid+,r,x); add2(k<<,l,mid,x); Min[k]=min(Min[k<<],Min[k<<|]); } int qry1(int k,int l,int r)//找到恰好为0的位置 { if (l==r) return l; down1(k); if (Max[k<<]>=) return qry1(k<<,l,mid);
else return qry1(k<<|,mid+,r);
}
int qry2(int k,int l,int r,int x)
{
if (x<=l) return Min[k];
down2(k); int res=inf;
if (x<=mid) res=min(res,qry2(k<<,l,mid,x));
res=min(res,qry2(k<<|,mid+,r,x));
return res;
}
int main()
{
build1(,-N,);
build2(,-N,N);
scanf("%d",&n);
for (int i=;i<=n;i++)
{
scanf("%d",&ax);
if (ax<) add1(,-N,,ax);
add2(,-N,N,ax-);
int l=qry1(,-N,);
printf("%d\n",qry2(,-N,N,l));
}
return ;
}

易错点：1.add1前缀++时，最后一个位置是不加的，所以应该从ax-1开始。

题解：线段树优化dp展开

发现一定是升序过来给赞是最优的，而这样一定存在一个分界点，该点之前x--，该点之后x单调不减。具体地,当a[x]<=-x时，x=x-1。我们设a[x]=-x的点为分界点。

之后的单调不减怎么求答案？设f[i]为第i个人点赞后，该博客的获赞数。f[i]=min(f[i-1]+1,a[i])。

展开：设分界点为x，分界点右边的第一个人为第l个，右端点为r，则f[r]=min(x+(r-l+1),a[l]+r-l,…,a[r-1]+1,a[r])。也可以用线段树优化掉。

开两棵权值线段树，一棵用来寻找分界点，维护a[x]+x的值，插入时后缀区间+1，查询时求a[x]=x的点。一棵用来维护f数组，插入时前缀区间+1(不包括右端点)，查询时求后缀最小值。

不管是否实际加入元素，权值线段树的区间都是整体加，因为有单调性不会冲突。