WOJ 641 Events 线段树解法

 Input file: standard input Output file: standard output Time limit: 1 second Memory limit: 512 mebibytes

Every year, the ACM/ICPC team will hold many contests, some of them are training while others are school contests.

In the year of 2017, there are $n$ contests to be held, and at the beginning of year, we plans the time of each contest.

However, as things are changing. Some other events might affect the time of contest and our team leader wants to know some interesting things about the time of some events.

Input

The first line contains an integer $n$. (0<n≤1050 < n \le 10^50<n≤10​5​​)

The second line contains $n$ integers, the $i$-th one of them is tit_it​i​​, which is the planning time of contest $i$ at the beginning of this year. (0≤ti≤1090\le t_i \le 10^90≤t​i​​≤10​9​​)

The third line contains an integer $q$. And then $q$ lines follows. (0<q≤1050 < q \le 10^50<q≤10​5​​)

Then each line contains three integers. LiL_iL​i​​,RiR_iR​i​​,TiT_iT​i​​, means the time of LiL_iL​i​​-th contest to RiR_iR​i​​-th contest will be changed by TiT_iT​i​​. And then you should output the earlist time of LiL_iL​i​​-th contest to RiR_iR​i​​-th contest in the history after the change of time. (0<Li≤Ri≤n0 < L_i \le R_i \le n0<L​i​​≤R​i​​≤n,∣Ti∣≤109|T_i| \le 10^9∣T​i​​∣≤10​9​​)

Output

Output contains $q$ lines, $i$-th line is the answer after $i$-th query.

Examples

Input 1

4 1 2 3 4 3 1 2 2 2 3 3 3 4 -10

Output 1

1 2 -6

Note

At the beginning, tit_it​i​​ are $(1,2,3,4)$. After the first change on time, tit_it​i​​ becomes $(3,4,3,4)$, and then $(3,7,6,4)$, and at last becomes $(3,7,-4,-6)$.

Be careful that as the times are relative times, so they can be negative.

        这题终于终于终于用线段树TMD AC了！

        想当初在赛场上怒调了三个小时的线段树，然后就是WA……满脸的辛酸……

        这题的分块算法我之前也写了文章，然后虽然分块确实更简单，但是我不甘心赛场上花的时间，于是死磕线段树。然后现在终于A了，虽说过程坎坷。

        通过这题还是发现自己的线段树的深层次的理解还是不够，个人认为此题作为线段树的提升题目非常的好，然后这题其实要考虑的东西挺多的，我都会提到的。

        首先呢，像普通线段树那样去维护区间瞬时的大小，这个没话说。关键在于还有一个区间历史最小，很简单的想法就是用区间瞬时最小更新历史最小，这个就是当场ak的队伍的做法，但是其实这样子是错的（数据错了orz……）。因为这样会导致lazy未下传而使得子区间历史最小没有得到修改，这个例子的话我好像在分块那提到了，我就不再说了。解决的方法就是我再用一个lazytag去标记至上一次更新子区间以来的历史最小增加值，这个和分块的lazy做法差不多。为了方便我们记录区间变化量为lazy1，历史最小增加值为lazy2，每次push_down的时候 用大区间的lazy2 + 小区间的lazy1 更新 小区间的lazy2。并在处理标记的同时维护瞬时最小和历史最小。

        接下来，就要说一些比较重要，容易忽略的地方，这也是曾困扰我几个小时的地方。正常的时候（至少我的习惯是这样），我们修改的时候如果区间没有完全重合，会继续往下找子区间，那么就有可能只更新左区间而未更新右区间。这样在一般情况貌似没什么问题，但是会发现那个未更新的区间的两个lazy都没有下放，这进而会影响大区间的瞬时最小值。这个问题累积起来后就会对后面的历史最小值产生影响从而出错。问题的解决方法也很简单，当只更新一个区间的时候，我们顺带把另一个区间的lazy给push下去。

        小小的问题先是一开始找不到错误，再到后来一遍遍的调试，这些都是非常消耗时间的。事实证明，有一个好的模板很重要，我自己的模板是有点问题的。然后的话，做题的时间还是要好好分配的，这个我已经不想再多说了……犯错并不怕，我还年轻，我还只是大一的！WHU，雪耻之战！ALPC_NeverGiveup……

代码如下：

#include<bits/stdc++.h> using namespace std; struct node { long long nowmin,hismin,lazy1,lazy2; int l,r; } tree[4*100000]; int n,q; long long a[101000]; inline void build(int i,int l,int r) { tree[i].l=l; tree[i].r=r; if (l==r) tree[i].nowmin=tree[i].hismin=a[l]; else { int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); tree[i].hismin=tree[i].nowmin=min(tree[i<<1].nowmin,tree[i<<1|1].nowmin); } } inline void push_down(int i) { if (!tree[i].lazy1 && !tree[i].lazy2) return; if (tree[i].l!=tree[i].r) //这一部分的下传与分块算法类似 { tree[i<<1].lazy2=min(tree[i<<1].lazy2,tree[i<<1].lazy1+tree[i].lazy2); tree[i<<1|1].lazy2=min(tree[i<<1|1].lazy2,tree[i<<1|1].lazy1+tree[i].lazy2); tree[i<<1|1].lazy1+=tree[i].lazy1; tree[i<<1].lazy1+=tree[i].lazy1; } tree[i].hismin=min(tree[i].hismin,tree[i].nowmin+tree[i].lazy2); tree[i].nowmin+=tree[i].lazy1; tree[i].lazy1=tree[i].lazy2=0; } inline void update(int i,int l,int r,long long delta) { push_down(i); if (tree[i].r==r && tree[i].l==l) { tree[i].lazy1+=(long long)delta; tree[i].lazy2=min(tree[i].lazy2,tree[i].lazy1); push_down(i); return; } int mid=(tree[i].l+tree[i].r)>>1; if (r<=mid) {push_down(i<<1|1); update(i<<1,l,r,delta);} //只更新一边就把另外一边的lazy给push下去 else if (l>mid) {push_down(i<<1); update(i<<1|1,l,r,delta);} else { update(i<<1,l,mid,delta); update(i<<1|1,mid+1,r,delta); } tree[i].nowmin=min(tree[i<<1].nowmin,tree[i<<1|1].nowmin); tree[i].hismin=min(tree[i].hismin,tree[i].nowmin); } inline long long getmin(int i,int l,int r) { push_down(i); if (tree[i].l==l && tree[i].r==r) return tree[i].hismin; int mid=(tree[i].l+tree[i].r)>>1; if (r<=mid) return getmin(i<<1,l,r); else if (l>mid) return getmin(i<<1|1,l,r); else return min(getmin(i<<1,l,mid),getmin(i<<1|1,mid+1,r)); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,1,n); scanf("%d",&q); while (q--) { long long l,r,x; scanf("%lld%lld%lld",&l,&r,&x); update(1,l,r,x); printf("%lld\n",getmin(1,l,r)); } return 0; }