专栏文章

差一点场切

NNewMarchqwq
P8987题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioq4xwc
此快照首次捕获于
2025/12/02 23:19
3 个月前
此快照最后确认于
2025/12/02 23:19
3 个月前
查看原文
为啥要凸包，我推不动（（（
注意到当 aa 数列非严格单增时，不管咋操作 aa 还是会非严格单增。
下面称一操作为 checkmin。
注意到成功进行过 checkmin 的点，把他们抽出来后他们的 aa 是单增的。
这启发我们分成两部分考虑，checkmin 前的和后的。考虑每个点只会被 checkmin 一次就会从一变成二，所以你可在每个 checkmin 的时候暴力弹出第一部分最大值尝试 checkmin，如果成功丢到第二个部分。
第一个部分需要支持：区间加等差数列，单点修改，区间 max，区间和。不难发现一个 KTT 和一个线段树就行了。
第二个部分因为 aa 值单增，直接暴力在线段树上二分要修改的区间，然后区间推平。所以需要支持 区间加等差数列，单点修改，区间和，区间推平。这只用一个线段树就行了。
有点细节。支持在线，复杂度三只老哥，但是 ktt 完全无法卡满所以比较轻松地过了。
代码CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...