差一点场切
NewMarchqwq · · 题解
为啥要凸包，我推不动（（（
注意到当
下面称一操作为 checkmin。
注意到成功进行过 checkmin 的点，把他们抽出来后他们的
这启发我们分成两部分考虑，checkmin 前的和后的。考虑每个点只会被 checkmin 一次就会从一变成二，所以你可在每个 checkmin 的时候暴力弹出第一部分最大值尝试 checkmin，如果成功丢到第二个部分。
第一个部分需要支持：区间加等差数列，单点修改，区间 max，区间和。不难发现一个 KTT 和一个线段树就行了。
第二个部分因为
有点细节。支持在线，复杂度三只老哥，但是 ktt 完全无法卡满所以比较轻松地过了。
::::info[代码]
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;
constexpr ll inf=1e18,piv=1e13;
int n,q;
ll a[200010];
namespace KTT{
int L[800010],R[800010];
ll tag[800010];
struct line{
ll k,b;
friend line operator+(line p,line q){return {p.k+q.k,p.b+q.b};}
};
inline pair<line,ll>gmx(line x,line y){
if (x.k<y.k||(x.k==y.k&&x.b<y.b))swap(x,y);
if (x.b>=y.b)return {x,inf};
else return {y,(y.b-x.b)/(x.k-y.k)};
}
struct node{
line l;
ll x;
friend node operator+(node p,node q){
node t;
t.x=min(p.x,q.x);
auto [nl,nx]=gmx(p.l,q.l);
t.x=min(t.x,nx);
t.l=nl;
return t;
}
}t[800010],base={{-inf,-inf},inf};
void bld(int p,int l,int r){
L[p]=l,R[p]=r,tag[p]=0;
if (l==r){
line z={l,a[l]};
t[p]={z,inf};
return ;
}
int mid=(l+r)>>1;
bld(p<<1,l,mid);
bld(p<<1|1,mid+1,r);
t[p]=t[p<<1]+t[p<<1|1];
// cout<<l<<' '<<r<<' '<<t[p].x<<'\n';
}
void get(int p,ll w){
tag[p]+=w,t[p].x-=w;
t[p].l.b+=t[p].l.k*w;
}
void chg(int p,ll w){
// cout<<p<<' '<<L[p]<<' '<<R[p]<<' '<<t[p].x<<'\n';
if (w<=t[p].x){
get(p,w);
return ;
}
ll ww=tag[p]+w;
tag[p]=0;
chg(p<<1,ww);
chg(p<<1|1,ww);
t[p]=t[p<<1]+t[p<<1|1];
}
void down(int p){
if (tag[p]){
get(p<<1,tag[p]);
get(p<<1|1,tag[p]);
tag[p]=0;
}
}
void upd(int p,int ql,int qr,ll w){
if (L[p]>qr||R[p]<ql||ql>qr)return ;
if (ql<=L[p]&&R[p]<=qr)return chg(p,w);
down(p);
upd(p<<1,ql,qr,w);
upd(p<<1|1,ql,qr,w);
t[p]=t[p<<1]+t[p<<1|1];
}
void mdf(int p,int o,line w){
if (L[p]==R[p]){
t[p].l=w;
return ;
}
down(p);
int mid=(L[p]+R[p])>>1;
if (o<=mid)mdf(p<<1,o,w);
else mdf(p<<1|1,o,w);
t[p]=t[p<<1]+t[p<<1|1];
}
node ask(int p,int ql,int qr){
if (L[p]>qr||R[p]<ql||ql>qr)return base;
if (ql<=L[p]&&R[p]<=qr)return t[p];
down(p);
return ask(p<<1,ql,qr)+ask(p<<1|1,ql,qr);
}
}
namespace sgt{
struct line{
ll k,b;
friend line operator+(line p,line q){return {p.k+q.k,p.b+q.b};}
}t[800010];
int L[800010],R[800010];
ll tag[800010];
void bld(int p,int l,int r){
L[p]=l,R[p]=r,tag[p]=0;
if (l==r){
t[p]={l,a[l]};
return ;
}
int mid=(l+r)>>1;
bld(p<<1,l,mid);
bld(p<<1|1,mid+1,r);
t[p]=t[p<<1]+t[p<<1|1];
}
void get(int p,ll x){
t[p].b+=t[p].k*x;
tag[p]+=x;
}
void down(int p){
get(p<<1,tag[p]);
get(p<<1|1,tag[p]);
tag[p]=0;
}
void upd(int p,int ql,int qr,ll x){
if (ql>R[p]||qr<L[p]||ql>qr)return ;
if (ql<=L[p]&&R[p]<=qr)return get(p,x);
down(p);
upd(p<<1,ql,qr,x);
upd(p<<1|1,ql,qr,x);
t[p]=t[p<<1]+t[p<<1|1];
}
void mdf(int p,int o,line x){
if (L[p]==R[p]){
t[p]=x;
return ;
}
down(p);
int mid=(L[p]+R[p])>>1;
if (o<=mid)mdf(p<<1,o,x);
else mdf(p<<1|1,o,x);
t[p]=t[p<<1]+t[p<<1|1];
}
line ask(int p,int ql,int qr){
if (ql>R[p]||qr<L[p]||ql>qr)return {0,0};
if (ql<=L[p]&&R[p]<=qr)return t[p];
down(p);
return ask(p<<1,ql,qr)+ask(p<<1|1,ql,qr);
}
}
namespace sgt2{
struct line{
ll k,b;
friend line operator+(line p,line q){return {p.k+q.k,p.b+q.b};}
}t[800010];
int L[800010],R[800010],cnt[800010];
ll tag[800010],tag2[800010];
void bld(int p,int l,int r){
L[p]=l,R[p]=r,tag[p]=0,tag2[p]=-1,cnt[p]=0;
if (l==r){
t[p]={0,0};
return ;
}
int mid=(l+r)>>1;
bld(p<<1,l,mid);
bld(p<<1|1,mid+1,r);
t[p]=t[p<<1]+t[p<<1|1];
}
void get(int p,ll x){
t[p].b+=t[p].k*x;
tag[p]+=x;
}
void get2(int p,ll x){
t[p].b=cnt[p]*x;
tag[p]=0;
tag2[p]=x;
}
void down(int p){
if (~tag2[p]){
get2(p<<1,tag2[p]);
get2(p<<1|1,tag2[p]);
tag2[p]=-1;
}
get(p<<1,tag[p]);
get(p<<1|1,tag[p]);
tag[p]=0;
}
void upd(int p,int ql,int qr,ll x){
if (ql>R[p]||qr<L[p]||ql>qr)return ;
if (ql<=L[p]&&R[p]<=qr)return get(p,x);
down(p);
upd(p<<1,ql,qr,x);
upd(p<<1|1,ql,qr,x);
t[p]=t[p<<1]+t[p<<1|1];
cnt[p]=cnt[p<<1]+cnt[p<<1|1];
}
void spec(int p,int ql,int qr,ll x){
if (ql>R[p]||qr<L[p]||ql>qr)return ;
if (ql<=L[p]&&R[p]<=qr)return get2(p,x);
down(p);
spec(p<<1,ql,qr,x);
spec(p<<1|1,ql,qr,x);
t[p]=t[p<<1]+t[p<<1|1];
cnt[p]=cnt[p<<1]+cnt[p<<1|1];
}
void mdf(int p,int o,line x){
if (L[p]==R[p]){
t[p]=x;
cnt[p]=t[p].k!=0;
return ;
}
down(p);
int mid=(L[p]+R[p])>>1;
if (o<=mid)mdf(p<<1,o,x);
else mdf(p<<1|1,o,x);
t[p]=t[p<<1]+t[p<<1|1];
cnt[p]=cnt[p<<1]+cnt[p<<1|1];
}
line ask(int p,int ql,int qr){
if (ql>R[p]||qr<L[p]||ql>qr)return {0,0};
if (ql<=L[p]&&R[p]<=qr)return t[p];
down(p);
return ask(p<<1,ql,qr)+ask(p<<1|1,ql,qr);
}
line ask_to(int p,int o){
// cout<<"??? "<<p<<' '<<o<<' '<<t[p].k<<'\n';
if (!t[p].k||o<L[p])return {0,0};
if (L[p]==R[p])return t[p];
down(p);
line now=ask_to(p<<1|1,o);
if (!now.k)return ask_to(p<<1,o);
return now;
}
void op1(ll v){
// cout<<"Checkmin "<<v<<'\n';
// rep(i,1,n)cout<<ask(1,i,i).b<<" \n"[i==n];
int lo=1,hi=n,mi,res=0;
while (lo<=hi){
mi=(lo+hi)>>1;
// cout<<mi<<' '<<ask_to(1,mi).b<<'\n';
if (ask_to(1,mi).b<v){
res=mi;
lo=mi+1;
}else
hi=mi-1;
}
// cout<<"GOT "<<res<<'\n';
spec(1,res+1,n,v);
// rep(i,1,n)cout<<ask(1,i,i).b<<" \n"[i==n];
}
void op2(){
// cout<<"Range +i\n";
upd(1,1,n,1);
// rep(i,1,n)cout<<ask(1,i,i).b<<" \n"[i==n];
}
ll op3(int l,int r){
return ask(1,l,r).b;
}
void ins(int i,ll x){
mdf(1,i,{i,x});
}
}
int main() {
#ifdef LOCAL
freopen("datastruct.in","r",stdin);
freopen("datastruct.out","w",stdout);
#endif
scanf("%d%d",&n,&q);
rep(i,1,n)scanf("%lld",&a[i]);
KTT::bld(1,1,n);
sgt::bld(1,1,n);
sgt2::bld(1,1,n);
while (q--){
int o;
scanf("%d",&o);
if (o==1){
ll v;
scanf("%lld",&v);
sgt2::op1(v);
while (1){
auto [id,z]=KTT::ask(1,1,n).l;
if (z>=v){
// cout<<"$ "<<id<<'\n';
sgt2::ins(id,v);
KTT::mdf(1,id,{0,-piv});
sgt::mdf(1,id,{0,0});
}else
break;
}
}else if (o==2){
KTT::upd(1,1,n,1);
sgt2::op2();
sgt::upd(1,1,n,1);
}else{
int l,r;
scanf("%d%d",&l,&r);
printf("%lld\n",sgt2::op3(l,r)+sgt::ask(1,l,r).b);
}
// rep(i,1,n)cout<<sgt2::ask(1,i,i).k<<" \n"[i==n];
}
return 0;
}::::