本文主要是介绍codeforces #52 C Circular RMQ（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：http://codeforces.com/problemset/problem/52/C
线段树区间更新水题。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>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("\n");*/}else{update(l,r,x,0,n-1,1);/*for(i=1;i<=7;i++)printf("%d ",min1[i]);printf("\n");*/}}else{if(l>r){int ans=min(query(l,n-1,0,n-1,1),query(0,r,0,n-1,1));printf("%d\n",ans);}else{int ans=query(l,r,0,n-1,1);printf("%d\n",ans);}}}return 0;
}
这篇关于codeforces #52 C Circular RMQ（线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
