留了几天的坑终于填了。。。
这个东西是线段树取区间最值问题。。。在吉司机16的论文里面。。。
其实就是让修改值和区间次大比较，假如次大较小就可以只改最大值，维护一下就可以了
注意到标记大小是按深度递增递增的
#include#include #include #include #include #include using namespace std;typedef long long LL;struct node{ LL mx,mxc,sx,sum,md;}tr[2100000];int trlen,a[1100000];void update(int now){ int lc=now<<1,rc=now<<1|1; tr[now].sum=tr[lc].sum+tr[rc].sum; tr[now].mx=max(tr[lc].mx,tr[rc].mx); tr[now].mxc=0; if(tr[lc].mx==tr[now].mx)tr[now].mxc+=tr[lc].mxc; if(tr[rc].mx==tr[now].mx)tr[now].mxc+=tr[rc].mxc; tr[now].sx=max(tr[lc].sx,tr[rc].sx); if(tr[lc].mx!=tr[rc].mx) tr[now].sx=max(tr[now].sx,min(tr[lc].mx,tr[rc].mx));}void pushdown(int now){ if(tr[now].md!=0) { int lc=now<<1,rc=now<<1|1; if(tr[lc].mx>tr[now].md) { tr[lc].sum-=tr[lc].mxc*(tr[lc].mx-tr[now].mx); tr[lc].mx=tr[lc].md=tr[now].md; } if(tr[rc].mx>tr[now].md) { tr[rc].sum-=tr[rc].mxc*(tr[rc].mx-tr[now].mx); tr[rc].mx=tr[rc].md=tr[now].md; } }}//~~~~~~~~~~~~~~tool~~~~~~~~~~~~~~~~~~~~~~~~~void bt(int now,int ql,int qr){ if(ql==qr) { tr[now].mx=tr[now].sum=a[ql]; tr[now].mxc=1; tr[now].sx=-1; } else { int mid=(ql+qr)/2; int lc=now<<1,rc=now<<1|1; bt(lc,ql,mid),bt(rc,mid+1,qr); update(now); } tr[now].md=0;}void change(int now,int ql,int qr,int l,int r,LL k){ if(tr[now].mx<=k)return ; if(ql==qr){tr[now].mx=tr[now].sum=k;return ;} int mid=(ql+qr)/2; int lc=now<<1,rc=now<<1|1; if(ql==l&&qr==r) { if(tr[now].sx