程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> codeforces #52 C Circular RMQ（線段樹）

codeforces #52 C Circular RMQ（線段樹）

編輯：C++入門知識

codeforces #52 C Circular RMQ（線段樹）

線段樹區間更新水題。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 

using namespace std;
const int INF=0x3f3f3f3f;
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
int min1[1000000], lazy[1000000];
void PushUp(int rt)
{
    min1[rt]=min(min1[rt<<1],min1[rt<<1|1]);
}
void PushDown(int rt)
{
    if(lazy[rt])
    {
        min1[rt<<1|1]+=lazy[rt];
        min1[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        lazy[rt<<1]+=lazy[rt];
        lazy[rt]=0;
    }
}
void build(int l, int r, int rt)
{
    if(l==r)
    {
        scanf(%d,&min1[rt]);
        return ;
    }
    int mid=l+r>>1;
    build(lson);
    build(rson);
    PushUp(rt);
}
void update(int ll, int rr, int x, int l, int r, int rt)
{
    if(ll<=l&&rr>=r)
    {
        lazy[rt]+=x;
        min1[rt]+=x;
        return ;
    }
    PushDown(rt);
    int mid=l+r>>1;
    if(ll<=mid) update(ll,rr,x,lson);
    if(rr>mid) update(ll,rr,x,rson);
    PushUp(rt);
}
int query(int ll, int rr, int l, int r, int rt)
{
    if(ll<=l&&rr>=r)
    {
        return min1[rt];
    }
    PushDown(rt);
    int ans=INF, mid=l+r>>1;
    if(ll<=mid) ans=min(ans,query(ll,rr,lson));
    if(rr>mid) ans=min(ans,query(ll,rr,rson));
    return ans;
}
int main()
{
    int n, l, r, x, q, i;
    scanf(%d,&n);
    build(0,n-1,1);
    scanf(%d,&q);
    memset(lazy,0,sizeof(lazy));
    while(q--)
    {
        scanf(%d%d,&l,&r);
        if(getchar()==' ')
        {
            scanf(%d,&x);
            if(l>r)
            {
                update(l,n-1,x,0,n-1,1);
                update(0,r,x,0,n-1,1);
                /*for(i=1;i<=7;i++)
                    printf(%d ,min1[i]);
                printf(
);*/
            }
            else
            {
                update(l,r,x,0,n-1,1);
                /*for(i=1;i<=7;i++)
                    printf(%d ,min1[i]);
                printf(
);*/
            }
        }
        else
        {
            if(l>r)
            {
                int ans=min(query(l,n-1,0,n-1,1),query(0,r,0,n-1,1));
                printf(%d
,ans);
            }
            else
            {
                int ans=query(l,r,0,n-1,1);
                printf(%d
,ans);
            }
        }
    }
    return 0;
}