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

You are given circular array a₀,?a₁,?...,?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₀,?a₁,?...,?a_n?-?1 (?-?10⁶?≤?a_i?≤?10⁶), a_i are integer. The third line contains integer m (0?≤?m?≤?200000), m — the number of operartons. Next mlines 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;?-?10⁶?≤?v?≤?10⁶) — 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

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);}elsereturn 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要用i64delseprintf("%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;
}