https://ac.nowcoder.com/acm/contest/11244/C

题解：

考虑只需要区间修改，求历史最大值

那么用线段树的话我们需要维护历史标记最大值，当前标记，区间当前最大值，历史区间最大值

其实现在变成求历史K大可以类似维护

我们维护历史标记最大的K个，当前标记，区间当前最大的K个，区间历史最大的K个

这样子updata的时候是比较显然的两个数组扫一下 复杂度O(logn*K)

down的时候一方面要维护历史标记最大值，这个是O(logn*K)的

另一方面要更新历史区间最大值，这是个堆的经典问题 复杂度O(logn*logk*k)

所以总时间复杂度O(nlognK+mlogn*logk*k)

因为down是瓶颈注意标记判一下有标记再down

代码：

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

//#include <immintrin.h>
//#include <emmintrin.h>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
#define mep(x,y) memcpy(x,y,sizeof(y))
#define IL inline
#define rint register int
#define mp make_pair
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
char ss[1<<24],*A=ss,*B=ss;
IL char gc()
{
    return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;
}
template<class T>void maxa(T &x,T y)
{
    if (y>x) x=y;
}
template<class T>void mina(T &x,T y)
{
    if (y<x) x=y;
}
template<class T>void read(T &x)
{
    int f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48);
    while(c=gc(),c>47&&c<58) x=x*10+(c^48); x*=f;
}
const int mo=1e9+7;
ll fsp(int x,int y)
{
    if (y==1) return x;
    ll ans=fsp(x,y/2);
    ans=ans*ans%mo;
    if (y%2==1) ans=ans*x%mo;
    return ans;
}
struct cp {
    ll x,y;
    cp operator +(cp B)
    {
        return (cp){x+B.x,y+B.y};
    }
    cp operator -(cp B)
    {
        return (cp){x-B.x,y-B.y};
    }
    ll operator *(cp B)
    {
        return x*B.y-y*B.x;
    }
    int half() { return y < 0 || (y == 0 && x < 0); }
};
struct re{
    int a,b,c;
};
const int N=1.1e5;
int a[N];
const int Mx=100;
#define mid ((h+t)/2)
struct sgt{
    int v1[N*4][101],v2[N*4][101],lz1[N*4],lz[N*4][101];
    sgt()
    {
        rep(i,0,N*4-1)
        {
          rep(j,0,100) v2[i][j]=lz[i][j]=v1[i][j]=-1e9;
          v1[i][1]=0;
        }
    }
    inline void g(int *a,int *b)
    {
        int c[101];
        int x=1,y=1;
        rep(i,1,Mx)
          if (a[x]>b[y]) c[i]=a[x++];
          else c[i]=b[y++];
        mep(a,c);
    }
    inline void updata(int x)
    {
        mep(v2[x],v2[x*2]);
        g(v2[x],v2[x*2+1]);
        mep(v1[x],v1[x*2]);
        g(v1[x],v1[x*2+1]);
    }
    void build(int x,int h,int t)
    {
        if (h==t)
        {
            v1[x][1]=v2[x][1]=a[h];
            return;
        }
        build(x*2,h,mid); build(x*2+1,mid+1,t);
        updata(x);
    }
    inline void g2(int *a,int *b,int *c)
    {
        priority_queue<pair<int,int> > M; 
        int h[101];
        rep(i,1,Mx) M.push(mp(b[i]+c[1],i)),h[i]=1;
        rep(i,1,Mx)
        {
            auto x=M.top();
            a[i]=max((int)(-1e9),x.first);
            M.pop();
            int y=x.second;
            h[y]++;
            M.push(mp(b[y]+c[h[y]],y));
        }
    }
    inline void down(int x)
    {
        if (lz[x][1]>-1e8)
        {
          rep(r,x*2,x*2+1)
          {
            int b[101];
            rep(i,1,Mx) b[i]=lz[x][i]+lz1[r];
            g(lz[r],b);
            lz1[r]+=lz1[x];
            g2(b,v1[r],lz[x]);
            g(v2[r],b);
            rep(i,1,Mx) v1[r][i]=v1[r][i]+lz1[x];
          }
          lz1[x]=0;
          rep(i,1,Mx) lz[x][i]=-1e9;
        }
    }
    void add(int x,int h,int t,int h1,int t1,int k)
    {
        if (h1<=h&&t<=t1)
        {
            lz1[x]+=k;
            int h[101];
            h[1]=lz1[x]; rep(i,2,100) h[i]=-1e9;
            g(lz[x],h);
            rep(i,1,Mx) v1[x][i]=v1[x][i]+k;
            g(v2[x],v1[x]);
            return;
        }
        down(x);
        if (h1<=mid) add(x*2,h,mid,h1,t1,k);
        if (mid<t1) add(x*2+1,mid+1,t,h1,t1,k);
        updata(x);
    }
    void query(int x,int h,int t,int h1,int t1,int *a)
    {
        if(h1<=h&&t<=t1)
        {
            g(a,v2[x]); return;
        }
        down(x);
        if (h1<=mid) query(x*2,h,mid,h1,t1,a);
        if (mid<t1) query(x*2+1,mid+1,t,h1,t1,a);
    }
}S;
int main()
{
   freopen("11.in","r",stdin);
   freopen("11.out","w",stdout);
   ios::sync_with_stdio(false);
   int n,m;
   cin>>n>>m;
   rep(i,1,n) cin>>a[i];
   S.build(1,1,n);
  /* rep(i,1,n)
   { 
     if (i==2e4) return 0;
     cout<<i<<endl;
     S.add(1,1,n,i,i,a[i]);
   } */
   //return 0;
   rep(i,1,m)
   {
   //    if (i%100==0) cerr<<i<<endl;
        int kk,l,r,x;
        cin>>kk>>l>>r>>x;
        if (kk==0) S.add(1,1,n,l,r,x);
        else
        {
            int ans[101];
            rep(i,1,100) ans[i]=-1e9;
            S.query(1,1,n,l,r,ans);
            int pp;
        //    rep(i,1,x) cout<<ans[i]<<" ";
       //     cout<<endl;
            rep(i,1,x) if (ans[i]>-1e8) pp=ans[i];
            cout<<pp<<endl;
        }
   }
   return 0;
}

View Code