慢慢变小的序列

C++14(g++5.4) 解法, 执行用时: 329ms, 内存消耗: 38104K, 提交时间: 2019-05-24 11:44:46

#include<bits/stdc++.h>
using namespace std;
#define N 1000000+100
//typedef long long ll;

#define int long long
int tree[12][N*4],a[N];

const int INF=1e9;
void add(int i,int l,int r,int x,int y,int k,int Tree[])
{
    if(l>=x&&r<=y){
        Tree[i]=min(k,Tree[i]);
        return ;
    }
    int mid=(l+r)/2;
    if(mid>=x)add(i*2,l,mid,x,y,k,Tree);
    if(mid+1<=y)add(i*2+1,mid+1,r,x,y,k,Tree);
}
int query(int i,int x,int l,int r,int Tree[])
{
    if(l==r)
    return Tree[i];
    int mid=(l+r)/2;
    if(x>=mid+1)return  min(query(i*2+1,x,mid+1,r,Tree),Tree[i]);
    else return min(query(i*2,x,l,mid,Tree),Tree[i]);
}
signed  main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=0;i<=10;i++)
    for(int j=0;j<=n*4;j++)
    tree[i][j]=INF;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    int flag;
    while(q--)
    {
        cin>>flag;
        if(flag==1){
            int l,r,x,y;
            cin>>l>>r>>x>>y;
            add(1,1,n,l,r,x-y*l,tree[y+5]);
        }
        else{
            int x;
            cin>>x;
            int ans=a[x];
            for(int i=0;i<=10;i++)
            {
                ans=min(ans,(i-5)*x+query(1,x,1,n,tree[i]));
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 108ms, 内存消耗: 19876K, 提交时间: 2023-03-23 18:11:01

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e5+10;
const int INF = 1e9+10;
int tree[12][maxn<<2],a[maxn],n,q;
int MIN(int x,int y){
	return x<y?x:y;
}
void Init(){
	for(int i=0;i<12;i++)
		for(int j=0;j<(maxn<<2);j++) tree[i][j] = INF;
}
void Update(int L,int R,int C,int ta[],int rt,int l,int r){
	if(L<=l&&r<=R){
		ta[rt] = MIN(ta[rt],C);
		return ;
	}
	int mid = (l+r)>>1;
	if(L<=mid) Update(L,R,C,ta,rt<<1,l,mid);
	if(R>mid) Update(L,R,C,ta,rt<<1|1,mid+1,r);
}
int Query(int pos,int ta[],int rt,int l,int r){
	if(l==r) return ta[rt];
	int mid = (l+r)>>1;
	if(pos<=mid) return MIN(ta[rt],Query(pos,ta,rt<<1,l,mid));
	else return MIN(ta[rt],Query(pos,ta,rt<<1|1,mid+1,r));
}
int main(void){
	Init();
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=q;i++){
		int op;scanf("%d",&op);
		if(op==1){
			int l,r,x,y;scanf("%d%d%d%d",&l,&r,&x,&y);
			Update(l,r,x-l*y,tree[y+5],1,1,n);
		}else{
			int x;scanf("%d",&x);
			for(int i=0;i<=10;i++) a[x] = MIN(a[x],(i-5)*x+Query(x,tree[i],1,1,n));
			printf("%d\n",a[x]);
		}
	}
	
	return 0;
}

详情