欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

NEFU 1111 线段树区间更新+懒惰标记相关介绍

程序员文章站 2022-04-01 23:38:12
题意:中文题目不解释 思路:就是简单的区间更新,可以在网上看看别人对于懒惰标记的解释,这里不多说了 #include #include #include...
题意:中文题目不解释
思路:就是简单的区间更新,可以在网上看看别人对于懒惰标记的解释,这里不多说了
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
long long  num[1000010];
long long num1[1000010];
void buildtree(int le,int ri,int node){
    if(le==ri){
        scanf("%lld",&num[node]);
        return ;
    }
    int t=(le+ri)>>1;
    buildtree(le,t,node<<1);
    buildtree(t+1,ri,node<<1|1);
    num[node]=min(num[node<<1],num[node<<1|1]);
}
void pushdown(int node){
    if(num1[node]){
        num1[node<<1]+=num1[node];
        num1[node<<1|1]+=num1[node];
        num[node<<1]+=num1[node];
        num[node<<1|1]+=num1[node];
        num1[node]=0;
    }
}
void add(int d,int a,int b,int le,int ri,int node){
    if(a<=le&&ri<=b){
        num1[node]+=d;
        num[node]+=d;
        return ;
    }
    pushdown(node);
    int t=(le+ri)>>1;
    if(a<=t) add(d,a,b,le,t,node<<1);
    if(b>t) add(d,a,b,t+1,ri,node<<1|1);
    num[node]=min(num[node<<1],num[node<<1|1]);
}
long long query(int a,int b,int le,int ri,int node){
    if(a<=le&&ri<=b){
        return num[node];
    }
    pushdown(node);
    long long ans=999999999;
    int t=(le+ri)>>1;
    if(a<=t) ans=min(ans,query(a,b,le,t,node<<1));
    if(b>t) ans=min(ans,query(a,b,t+1,ri,node<<1|1));
    return ans;
}
int main(){
    int n,m,a,b,c,d;
    while(scanf("%d",&n)!=-1){
        buildtree(1,n,1);
        scanf("%d",&m);
        while(m--){
            scanf("%d",&a);
            if(a==1){
                scanf("%d%d",&b,&c);
                b++;c++;
                if(b<=c)
                printf("%lld\n",query(b,c,1,n,1));
                else{
                    long long ans1=query(b,n,1,n,1);
                    long long ans2=query(1,c,1,n,1);
                    printf("%lld\n",min(ans1,ans2));
                }
            }else{
                scanf("%d%d%d",&b,&c,&d);
                b++;c++;
                if(b<=c){
                    add(d,b,c,1,n,1);
                }
                else{
                    add(d,b,n,1,n,1);
                    add(d,1,c,1,n,1);
                }
            }
//            for(int i=1;i<=4*n;i++)
//            cout<