Codeforces 52 C 解题报告
题意:
给你n个数,你要区间操作:
区间+v
求区间最小值
链接:http://www.codeforces.com/contest/52/problem/C
PS:因为这n个数是环状的,所以可能区间修改会比较奇葩
不过一样...
一个裸的线段树,没啥好说的了..
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | #include<set>#include<map>#include<list>#include<queue>#include<stack>#include<string>#include<math.h>#include<time.h>#include<vector>#include<bitset>#include<memory>#include<utility>#include<fstream>#include<stdio.h>#include<sstream>#include<iostream>#include<stdlib.h>#include<string.h>#include<algorithm>using namespace std;long long val[1<<19];long long tag[1<<19];int a[1<<18];const long long inf=999999999999999999ll;void build_tree(int num,int l,int r){ if (l==r-1) { val[num]=a[l]; return; } int mid=(l+r)/2; build_tree(num*2+1,l,mid); build_tree(num*2+2,mid,r); val[num]=min(val[num*2+1],val[num*2+2]);}void change(int num,int l,int r,int l0,int r0,int k){ if ((l0<=l)&&(r<=r0)) { tag[num]+=k; return; } int mid=(l+r)/2; if (l0<mid) change(num*2+1,l,mid,l0,r0,k); if (mid<r0) change(num*2+2,mid,r,l0,r0,k); val[num]=min(val[num*2+1]+tag[num*2+1],val[num*2+2]+tag[num*2+2]);}long long query(int num,int l,int r,int l0,int r0){ if ((l0<=l)&&(r<=r0)) { return val[num]+tag[num]; } int mid=(l+r)/2; long long ans=inf; if (l0<mid) ans=min(ans,query(num*2+1,l,mid,l0,r0)); if (mid<r0) ans=min(ans,query(num*2+2,mid,r,l0,r0)); return ans+tag[num];}int main(){ #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif ios::sync_with_stdio(false); int n; scanf("%d",&n); int i; for (i=0;i<n;i++) { scanf("%d",&a[i]); } build_tree(0,0,n); int q; scanf("%d",&q); for (i=0;i<q;i++) { int x,y; scanf("%d%d",&x,&y); y++; char t=getchar(); if (t==' ') { int z; scanf("%d",&z); if (x>=y) { change(0,0,n,x,n,z); change(0,0,n,0,y,z); } else { change(0,0,n,x,y,z); } } else { if (x>=y) { cout<<min(query(0,0,n,x,n),query(0,0,n,0,y))<<'\n'; } else { cout<<query(0,0,n,x,y)<<'\n'; } } } return 0;} |
评论 (0)