未曾设想的道路

C++(g++ 7.5.0) 解法, 执行用时: 5761ms, 内存消耗: 311796K, 提交时间: 2022-10-24 21:38:45

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10,K=100,inf=0x3f3f3f3f,cp=-1e7;
struct node{
    int l,r;
    int v[K],s[K],add,a[K];
}tr[N<<2];
int a[N];
int n,m;
void add(int a[], int b[], int c[]) {
    priority_queue <pair<int, int>> P;
    for (int i=0; i<K; i++) {
        P.push({a[0] + b[i], 0});
    }
    for (int i=0; i<K; i++) {
        auto u = P.top(); P.pop();
        c[i] = u.first;
        if (i == K - 1) break;
        P.push({u.first - a[u.second] + a[u.second + 1], u.second + 1});
    }
}
void merge(int a[],int b[],int c[]){
    for(int i=0,j=0,k=0;i<K;){
        if(a[j]>=b[k])c[i++]=a[j++];
        else c[i++]=b[k++];
    }
}
void merge(int a[],int b[]){
    int f[K];
    for(int i=0,j=0,k=0;i<K;){
        if(a[j]>=b[k])f[i++]=a[j++];
        else f[i++]=b[k++];
    }
    for(int i=0;i<K;++i)a[i]=f[i];
}
void pushdown(int rt){
    if (tr[rt].s[0] > cp) {
        for (auto ch : {rt<<1, rt<<1|1}) {
            int f[K];
 
            add(tr[ch].v, tr[rt].s, f);
            merge(tr[ch].a, f);
 
            for (int i=0; i<K; i++) f[i] = tr[ch].add + tr[rt].s[i];
            merge(tr[ch].s, f);
 
            tr[ch].add += tr[rt].add;
            for (int i=0; i<K; i++) tr[ch].v[i] += tr[rt].add;
        }
 
        tr[rt].add = 0;
        for (int i=0; i<K; i++) tr[rt].s[i] = -inf;
    }
}
void build(int k,int l,int r){
    tr[k]={l,r};
    for(int i=0;i<K;++i)tr[k].s[i]=-inf;
    if(l==r){
        tr[k].v[0]=a[l];
        for(int i=1;i<K;++i)tr[k].v[i]=-inf;
        for(int i=0;i<K;++i)tr[k].a[i]=tr[k].v[i];
        return ;
    }
    int mid=l+r>>1;
    build(k<<1,l,mid);build(k<<1|1,mid+1,r);
    merge(tr[k<<1].v,tr[k<<1|1].v,tr[k].v);
    for(int i=0;i<K;++i)tr[k].a[i]=tr[k].v[i];
}
void update(int k,int l,int r,int x){
    if(tr[k].l>=l&&r>=tr[k].r){
        for(int i=0;i<K;++i)tr[k].v[i]+=x;
        merge(tr[k].a,tr[k].v);
        tr[k].add+=x;
        for(int i=0;i<K;++i){
            if(tr[k].add>tr[k].s[i]){
                for(int j=K-1;j>i;j--){
                    tr[k].s[j]=tr[k].s[j-1];
                }
                tr[k].s[i]=tr[k].add;
                break;
            }
        }
        return ;
    }
    pushdown(k);
    int mid=tr[k].l+tr[k].r>>1;
    if(mid>=l)update(k<<1,l,r,x);
    if(mid<r)update(k<<1|1,l,r,x);
    merge(tr[k<<1].v,tr[k<<1|1].v,tr[k].v);
    merge(tr[k<<1].a,tr[k<<1|1].a,tr[k].a);
}
int ans[K];
void query(int k,int l,int r){
    if(tr[k].l>=l&&tr[k].r<=r){
        merge(ans,tr[k].a);
        return;
    }
    pushdown(k);
    int mid=tr[k].l+tr[k].r>>1;
    if(mid>=l)query(k<<1,l,r);
    if(mid<r)query(k<<1|1,l,r);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    build(1,1,n);
    while(m--){
        int op,l,r,k;
        cin>>op>>l>>r>>k;
        if(!op){
            update(1,l,r,k);
        }
        else{
            for(int i=0;i<K;++i)ans[i]=-inf;
            query(1,l,r);
            while(k&&ans[k-1]<cp)k--;
            cout<<ans[k-1]<<"\n";
            //for(int i=0;i<K;++i)cout<<ans[i]<<" ";
        }
    }
}

C++ 解法, 执行用时: 6783ms, 内存消耗: 205048K, 提交时间: 2021-06-13 15:48:17

#pragma GCC optimize(2)
#include <cstdio>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
const int M = 100005;
#define pii pair<int,int>
#define make make_pair
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,a[M];
struct zxy
{
	int lazy;vector<int> v;
	void clear() {lazy=0;v.clear();}
	zxy() {clear();}
	zxy(int r) {v.resize(1);v[0]=lazy=r;}
	void operator += (const zxy &b)
	{
		vector<int> tmp;
		int A=v.size(),B=b.v.size(),i=0,j=0;
		tmp.resize(A+B);
		while(i!=A && j!=B)
		{
			if(b.v[j]+lazy>v[i])
				tmp[i+j]=b.v[j]+lazy,j++;
			else
				tmp[i+j]=v[i],i++;
		}
		for(;i!=A;i++) tmp[i+j]=v[i];
		for(;j!=B;j++) tmp[i+j]=b.v[j]+lazy;
		v=tmp;lazy+=b.lazy;
		if(v.size()>100) v.resize(100);
	}
};
//
zxy mx[4*M],all[4*M],tag[4*M];
void up(int i)
{
	mx[i]=mx[i<<1];
	mx[i]+=mx[i<<1|1];
	all[i]=all[i<<1];
	all[i]+=all[i<<1|1]; 
}
void addtag(int x,zxy t)
{
	if(t.v.empty()) return ;
	priority_queue<pii> q;zxy tmp;
	for(int i=0;i<mx[x].v.size();i++)
		q.push(make(mx[x].v[i]+t.v[0],0));
	while(!q.empty() && tmp.v.size()<100)
	{
		pii u=q.top();q.pop();
		tmp.v.push_back(u.first);
		if(u.second<t.v.size()-1)
		{
			u.first-=t.v[u.second];
			u.first+=t.v[++u.second];
			q.push(u);
		}
	}
	all[x]+=tmp;
	for(int i=0;i<mx[x].v.size();i++)
		mx[x].v[i]+=t.lazy;
	tag[x]+=t;
}
void down(int i)
{
	addtag(i<<1,tag[i]);
	addtag(i<<1|1,tag[i]);
	tag[i].clear();
}
void build(int i,int l,int r)
{
	if(l==r)
	{
		mx[i]=all[i]=zxy(a[l]);
		mx[i].lazy=all[i].lazy=0;
		return ;
	}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	up(i);
}
void upd(int i,int l,int r,int L,int R,int v)
{
	if(L>r || l>R) return ;
	if(L<=l && r<=R)
	{
		addtag(i,zxy(v));
		return ;
	}
	int mid=(l+r)>>1;down(i);
	upd(i<<1,l,mid,L,R,v);
	upd(i<<1|1,mid+1,r,L,R,v);
	up(i);
}
zxy ask(int i,int l,int r,int L,int R)
{
	if(L<=l && r<=R) return all[i];
	int mid=(l+r)>>1;down(i);
	if(mid>=R) return ask(i<<1,l,mid,L,R);
	if(mid<L) return ask(i<<1|1,mid+1,r,L,R);
	zxy tmp=ask(i<<1,l,mid,L,R);
	tmp+=ask(i<<1|1,mid+1,r,L,R);
	return tmp;
}
signed main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	build(1,1,n);
	while(m--)
	{
		int op=read(),l=read(),r=read(),k=read();
		if(op==0) upd(1,1,n,l,r,k);
		else
		{
			zxy tmp=ask(1,1,n,l,r);
			int x=tmp.v.size();x=min(x,k);
			printf("%d\n",tmp.v[x-1]);
		}
	}
}

详情