[DS记录]P5073 [Ynoi2015] 世上最幸福的女孩

command_block · 2021-02-16 18:58:12 · 个人记录

题意 : 全局加，求区间最大子段和。

允许离线，n\leq 3\times 10^5,m\leq 6\times 10^5 ，时限\texttt{1s}，空限\texttt{128Mb}。

考虑经典的维护最大子段和的线段树，需要记录下列四个值 : 最大前缀 sl，最大后缀 sr ，最大子段和 m ，区间和 s 。

然而，仅记录这几个值并不能支持快速打标记。

考虑改而记录成四个函数， sl(t),sr(t),m(t),s(t) ，分别表示该区间整体加上 t 后的最大前缀，最大后缀，最大子段和，区间和。

其中 s(t) 显然等于 s+t*len。

而 sl,sr,m 可以通过经典的转移得到 :

对于区间 [l,r] ，在整体加上 t 之后的和会增加 len*t ，故一个区间对函数的贡献是一条直线。

这里 sl,sr,m 都是若干候选区间取 \max 的形式，可以用若干直线的 \max 来描述，为下凸壳。

将直线 y=kx+b 视作点 (k,b) ，对偶后转化为维护上凸壳。

由于不同的 k 的数目是 r-l+1 的，故凸壳的大小也是 O(r-l+1) 的，求个和就是 O(n\log n)。

于是，大力求出所有的分段函数，时空复杂度均为 O(n\log n)。

在查询时，根据全局标记，在对应区间的函数求值，并按照经典的最大子段和合并方法计算答案。

分段函数求值需要二分，这样复杂度就是 O(q\log^2 n) 的，无法通过。

考虑离线，将全局加标记从小到大排序，这样求值就能线性扫描了。

除此之外，高达 O(n\log n) 的空间复杂度很可能导致 \rm MLE ，考虑优化。

将原序列分成大小为 O(\log n) 个块，区间询问会被拆分成 O(\log n) 个整块询问和 O(1) 个零散询问，即 O(\log n) 次函数求值，没有增加复杂度。

逐块处理即可将空间降至 O(n)。

时间复杂度 O((n+q)\log n) ，空间复杂度 O(n)。

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define pb push_back
#define ll long long
#define MaxN 300500
#define MaxS 30050
using namespace std;
int read(){
  int X=0;char ch=0,fl=0;
  while(ch<48||ch>57)ch=getchar(),fl|=(ch=='-');
  while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
  return fl?-X:X;
}
struct Line{
  ll k,b;
  inline ll get(ll x)
  {return k*x+b;}
  bool operator < (const Line &B) const
  {return k==B.k ? b<B.b : k<B.k;}
}Z=(Line){0,0};
inline Line operator + (const Line &A,const Line &B)
{return (Line){A.k+B.k,A.b+B.b};}
inline Line operator - (const Line &A,const Line &B)
{return (Line){A.k-B.k,A.b-B.b};}
bool chk(const Line &A,const Line &B,const Line &C){
  ll x1=A.k-B.k,y1=A.b-B.b
    ,x2=C.k-B.k,y2=C.b-B.b;
  return x1*y2-y1*x2>0; 
}//以线代点构成上凸壳
struct Hull{
  Line *l;int siz;
  Line& operator [] (int i){return l[i];}
  void clear(){siz=0;}
  inline void pb(const Line &x){l[siz++]=x;}
  inline void pop_back(){--siz;}
};
Line s1[MaxS],s2[MaxS],s3[MaxS];
void max(Hull A,Hull B,Hull &C)
{
  merge(A.l,A.l+A.siz,B.l,B.l+B.siz,s1);
  int n=A.siz+B.siz;
  C.clear();
  Line sav=C[-1];C[-1]=Z;
  for (int i=0;i<n;i++){
    while(C.siz>=1&&!chk(C[C.siz-2],C[C.siz-1],s1[i]))C.pop_back();
    C.pb(s1[i]);
  }C[-1]=sav;
}
inline bool cmp2(const Line &A,const Line &B)
{return A.k*B.b<A.b*B.k;}
void add(Hull A,Hull B,Hull &C)
{
  memcpy(s1,A.l,sizeof(Line)*A.siz);
  memcpy(s2,B.l,sizeof(Line)*B.siz);
  for (int i=A.siz-1;i;i--)s1[i]=s1[i]-s1[i-1];
  for (int i=B.siz-1;i;i--)s2[i]=s2[i]-s2[i-1];
  C.siz=A.siz+B.siz;
  merge(s1,s1+A.siz,s2,s2+B.siz,C.l,cmp2);
  for (int i=1;i<C.siz;i++)C[i]=C[i-1]+C[i];
}
void add(Hull C,Line l)
{for (int i=0;i<C.siz;i++)C[i]=C[i]+l;}
Line o[3][16][MaxS],_sav[MaxS];
struct Node{
  Hull sl,sr,m;
  Line s;int psl,psr,pm;
}a[1<<16|500];
Hull sav=(Hull){_sav+1,0};
inline void cpy(Hull &A,Hull B)
{memcpy(A.l,B.l,sizeof(Line)*B.siz);A.siz=B.siz;}
void up(int u)
{
  int l=u<<1,r=u<<1|1;
  a[u].s=a[l].s+a[r].s;
  cpy(a[u].sl,a[r].sl);add(a[u].sl,a[l].s);
  max(a[u].sl,a[l].sl,a[u].sl);
  cpy(a[u].sr,a[l].sr);add(a[u].sr,a[r].s);
  max(a[u].sr,a[r].sr,a[u].sr);
  add(a[l].sr,a[r].sl,a[u].m);
  max(a[l].m,a[r].m,sav);
  max(sav,a[u].m,a[u].m);
}
void build(int l,int r,int u,int dep,int *x)
{
  a[u].sl.l=&o[0][dep][l];a[u].sl.clear();
  a[u].sr.l=&o[1][dep][l];a[u].sr.clear();
  a[u].m.l=&o[2][dep][l];a[u].m.clear();
  a[u].psl=a[u].psr=a[u].pm=0;
  if (l==r){
    a[u].s=(Line){1,x[l]};
    a[u].sl.pb(a[u].s);
    a[u].sr.pb(a[u].s);
    a[u].m.pb(a[u].s);
    return ;
  }int mid=(l+r)>>1;
  build(l,mid,u<<1,dep+1,x);
  build(mid+1,r,u<<1|1,dep+1,x);
  up(u);
}
ll get(ll x,int &p,Hull &l){
  while(p<l.siz-1&&l[p].get(x)<l[p+1].get(x))p++;
  return max(0ll,l[p].get(x));
}
int wfl,wfr;ll wfx,rsr,rm;
void qry(int l,int r,int u)
{
  if (wfl<=l&&r<=wfr){
    ll tsl=get(wfx,a[u].psl,a[u].sl)
      ,tsr=get(wfx,a[u].psr,a[u].sr)
      ,tm=get(wfx,a[u].pm,a[u].m);
    rm=max(rm,max(rsr+tsl,tm));
    rsr=max(tsr,rsr+a[u].s.get(wfx));
    return ;
  }int mid=(l+r)>>1;
  if (wfl<=mid)qry(l,mid,u<<1);
  if (mid<wfr)qry(mid+1,r,u<<1|1);
}
struct QData{ll t;int p,l,r;}b[MaxN<<1];
bool cmp(const QData &A,const QData &B)
{return A.t<B.t;}
ll asr[MaxN<<1],am[MaxN<<1];
int n,m,tn,BS,x[MaxN];ll tg;
int main()
{
  n=read();m=read();
  BS=1.8*n/log2(n)+5;
    for (int i=1;i<=n;i++)x[i]=read();
    for (int i=1;i<=m;i++){
      if (read()==1)tg+=read();
    else {
      int l=read(),r=read();
      ++tn;b[tn]=(QData){tg,tn,l,r};
    }
  }sort(b+1,b+tn+1,cmp);
  for (int k=0;k*BS<n;k++){
    int m=min(BS,n-k*BS);
    build(1,m,1,0,x+k*BS);
    for (int i=1;i<=tn;i++){
      wfl=max(b[i].l-k*BS,1);
      wfr=min(b[i].r-k*BS,m);
      wfx=b[i].t;
      if (wfl<=wfr){
        rsr=asr[b[i].p];rm=am[b[i].p];
        qry(1,m,1);
        asr[b[i].p]=rsr;am[b[i].p]=rm;
      }
    }
  }for (int i=1;i<=tn;i++)
    printf("%lld\n",am[i]);
    return 0;
}