CodeForces 52C Circular RMQ （线段树的区间更新+lazy tag）

忘是亡心i 2022-06-12 02:44 147阅读 0赞

You are given circular array *a*0, *a*1, ..., *a**n* - 1. There are two types of operations with it:

*  *inc*(*lf*, *rg*, *v*) — this operation increases each element on the segment \[*lf*, *rg*\](inclusively) by *v*;
 *  *rmq*(*lf*, *rg*) — this operation returns minimal value on the segment \[*lf*, *rg*\](inclusively).

Assume segments to be circular, so if *n* = 5 and *lf* = 3, *rg* = 1, it means the index sequence: 3, 4, 0, 1.

Write program to process given sequence of operations.

Input

The first line contains integer *n* (1 ≤ *n* ≤ 200000). The next line contains initial state of the array: *a*0, *a*1, ..., *a**n* - 1 ( - 106 ≤ *a**i* ≤ 106), *a**i* are integer. The third line contains integer *m* (0 ≤ *m* ≤ 200000), *m* — the number of operartons. Next *m*lines contain one operation each. If line contains two integer *lf*, *rg* (0 ≤ *lf*, *rg* ≤ *n* - 1) it means *rmq* operation, it contains three integers *lf*, *rg*, *v* (0 ≤ *lf*, *rg* ≤ *n* - 1; - 106 ≤ *v* ≤ 106) — *inc* operation.

Output

For each *rmq* operation write result for it. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).

Example

Input

4
    1 2 3 4
    4
    3 0
    3 0 -1
    0 1
    2 1

Output

1
    0
    0

题解：

现在还在比赛。。但我已经写不出来题了，就来写博客了，好高兴线段树的题没看题解就写出来了，这几天线段树和树状数组的题没白刷，这题就是如果输入区间不是从小到大就分成两个区间做，然后要注意一下区间更新要lazy tag，延迟更新，然后输入的时候做点判断处理这题就ac了

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    struct node
    {
        int l,r;
        long long minn;
        long long tag;
    };
    node t[200005*4];
    int a[200005];
    void Build(int l,int r,int num)//日常建树
    {
        t[num].l=l;
        t[num].r=r;
        t[num].tag=0;
        if(l==r)
        {
            t[num].minn=a[l];
            return;
        }
        int mid=(l+r)/2;
        Build(l,mid,num*2);
        Build(mid+1,r,num*2+1);
        t[num].minn=min(t[num*2].minn,t[num*2+1].minn);//更新下最小值
    }
    void update(int l,int r,int num,int v)
    {
        if(t[num].l==l&&t[num].r==r)
        {
            t[num].minn+=v;
            t[num].tag+=v;
            return;
        }
        if(t[num].tag!=0)//除了这个都是日常更新，这个可以写成一个函数lazy tag，将上次没有更新的东西向下子节点更新
        {
            t[num*2].minn+=t[num].tag;
            t[num*2+1].minn+=t[num].tag;
            t[num*2].tag+=t[num].tag;
            t[num*2+1].tag+=t[num].tag;
            t[num].tag=0;//清除状态
        }
        int mid=(t[num].l+t[num].r)/2;
        if(r<=mid)
            update(l,r,num*2,v);
        else if(l>mid)
            update(l,r,num*2+1,v);
        else
        {
            update(l,mid,num*2,v);
            update(mid+1,r,num*2+1,v);
        }
        t[num].minn=min(t[num*2].minn,t[num*2+1].minn);//更新最小值
    }
    long long query(int l,int r,int num)//访问
    {
        if(t[num].l==l&&t[num].r==r)
        {
            return t[num].minn;
        }
          if(t[num].tag!=0)//和上面一样，pushdown
        {
            t[num*2].minn+=t[num].tag;
            t[num*2+1].minn+=t[num].tag;
            t[num*2].tag+=t[num].tag;
            t[num*2+1].tag+=t[num].tag;
            t[num].tag=0;
        }
        int mid=(t[num].l+t[num].r)/2;
        if(r<=mid)
            return query(l,r,num*2);
        else if(l>mid)
        {
            return query(l,r,num*2+1);
        }
        else
            return min(query(l,mid,num*2),query(mid+1,r,num*2+1));
    }
    int main()
    {
        int i,j,n,m,x,y,z,tag,flag;
        char s[100];
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        Build(0,n-1,1);
        scanf("%d",&m);
        getchar();//吸收回车
        for(i=0;i<m;i++)
        {
            tag=0;
            gets(s);
            x=0,y=0,z=0;
            flag=0;
            for(j=0;j<strlen(s);j++)
            {
                if(s[j]==' ')//根据空格数目判断情况，储存数据
                {
                    tag++;
                    continue;
                }
                if(tag==0)
                {
                    x=x*10+s[j]-'0';
                }
                else if(tag==1)
                {
                    y=y*10+s[j]-'0';
                }
                else
                {
                    if(s[j]=='-')
                        flag=1;
                    else
                    {
                        z=z*10+s[j]-'0';
                    }
                }
            }
            if(flag)//z处有负号
                z=-z;
            if(tag==1)
            {
                if(x<=y)
                    printf("%I64d\n",query(x,y,1));//codeforce要用i64d
                else
                    printf("%I64d\n",min(query(0,y,1),query(x,n-1,1)));//如果输入的y大于x，就分成两个部分
            }
            else
            {
                if(x<=y)
                    update(x,y,1,z);
                else
                {
                    update(0,y,1,z);//同理分成两个部分
                    update(x,n-1,1,z);
                }
            }
        }
        return 0;
    }