題干：

There is a system of?n?vessels arranged one above the other as shown in the figure below. Assume that the vessels are numbered from 1 to?n, in the order from the highest to the lowest, the volume of the?i-th vessel is?ai?liters.

Initially, all the vessels are empty. In some vessels water is poured. All the water that overflows from the?i-th vessel goes to the?(i?+?1)-th one. The liquid that overflows from the?n-th vessel spills on the floor.

Your task is to simulate pouring water into the vessels. To do this, you will need to handle two types of queries:

Add?xi?liters of water to the?pi-th vessel;

Print the number of liters of water in the?ki-th vessel.

When you reply to the second request you can assume that all the water poured up to this point, has already overflown between the vessels.

Input

The first line contains integer?n?— the number of vessels (1?≤?n?≤?2·105). The second line contains?n?integers?a1,?a2,?...,?an?— the vessels' capacities (1?≤?ai?≤?109). The vessels' capacities do not necessarily increase from the top vessels to the bottom ones (see the second sample). The third line contains integer?m?— the number of queries (1?≤?m?≤?2·105). Each of the next?m?lines contains the description of one query. The query of the first type is represented as "1?pi?xi", the query of the second type is represented as "2?ki" (1?≤?pi?≤?n,?1?≤?xi?≤?109,?1?≤?ki?≤?n).

Output

For each query, print on a single line the number of liters of water in the corresponding vessel.

Examples

Input

2 5 10 6 1 1 4 2 1 1 2 5 1 1 4 2 1 2 2

Output

4 5 8

Input

3 5 10 8 6 1 1 12 2 2 1 1 6 1 3 2 2 2 2 3

Output

7 10 5

解題報(bào)告：

? ? 先來一發(fā)暴力TLE，然后發(fā)現(xiàn)可以用并查集的區(qū)間合并。

TLE代碼：

#include<bits/stdc++.h>using namespace std; const int MAX = 2e5 + 5; int a[MAX],rest[MAX],ne[MAX];int main() {int n,m,x,y,op;cin>>n;for(int i = 1; i<=n; i++) scanf("%d",a+i),rest[i]=a[i],ne[i]=i;cin>>m;while(m--) {scanf("%d",&op);if(op == 2) {scanf("%d",&x);printf("%d\n",a[x] - rest[x]);}else {scanf("%d%d",&x,&y);while(rest[ne[x]] == 0 && ne[x] <= n) ne[x]++;//ne[x]=ne[x+1];while(y>0 && ne[x]<=n) {if(y>=rest[ne[x]]) {y-=rest[ne[x]];rest[ne[x]]=0;ne[x]++; }else rest[ne[x]]-=y,y=0;}}}return 0 ;} /* in: 10 71 59 88 55 18 98 38 73 53 58 20 1 5 93 1 7 69 2 3 1 1 20 2 1 2 10 1 6 74 1 7 100 1 9 14 2 3 2 4 2 7 1 3 31 2 4 1 6 64 2 2 2 2 1 3 54 2 9 2 1 1 6 86 out: 0 0 0 0 38 0 0 0 53 20*/ #include<bits/stdc++.h>using namespace std; const int MAX = 2e5 + 5; int a[MAX],rest[MAX],ne[MAX];int main() {int n,m,x,y,op;cin>>n;for(int i = 1; i<=n; i++) scanf("%d",a+i),rest[i]=a[i],ne[i]=i;ne[n+1] = n+1;cin>>m;while(m--) {scanf("%d",&op);if(op == 2) {scanf("%d",&x);printf("%d\n",a[x] - rest[x]);}else {scanf("%d%d",&x,&y);while(rest[ne[x]] == 0 && ne[x] <= n) {if(ne[x]!=ne[x+1])ne[x]=ne[x+1];else ne[x]++,ne[x+1]++;}while(y>0 && ne[x]<=n) {if(y>=rest[ne[x]]) {y-=rest[ne[x]];rest[ne[x]]=0;//ne[x]++;//ne[x]=ne[ne[x+1]];if(ne[x]!=ne[x+1])ne[x]=ne[x+1];else ne[x]++,ne[x+1]++; }else rest[ne[x]]-=y,y=0;}}}return 0 ;}

后來發(fā)現(xiàn)可以ne[x]=ne[ne[x+1]]，然后就可以ne[x]=ne[ne[ne[x+1]]]以此類推，再仔細(xì)一看，這不就是并查集的getf函數(shù)的過程嗎。

開搞：

AC代碼：

#include<bits/stdc++.h>using namespace std; const int MAX = 2e5 + 5; int a[MAX],rest[MAX],f[MAX]; int getf(int v) {return f[v] == v ? v : f[v] = getf(f[v]); } void merge(int u,int v) {//默認(rèn)u < vint t1 = getf(u);int t2 = getf(v);if(t1 != t2) f[t1] = t2; } int main() {int n,m,x,y,op;cin>>n;for(int i = 1; i<=n; i++) scanf("%d",a+i),rest[i]=a[i],f[i]=i;f[n+1] = n+1;cin>>m;while(m--) {scanf("%d",&op);if(op == 2) {scanf("%d",&x);printf("%d\n",a[x] - rest[x]);}else {scanf("%d%d",&x,&y);int t1=getf(x);while(y>0 && t1 <= n) {t1 = getf(t1);if(y>=rest[t1] && t1 <= n) {//只能裝rest[t1]的水了 y-=rest[t1];rest[t1]=0;merge(t1,t1+1); }else rest[t1]-=y,y=0;}}}return 0 ;}

別忘處理邊界啊，就是已經(jīng)到最下面那個瓶子哪里了，所以兩個地方都需要t1<=n，給個樣例：

10
71 59 88 55 18 98 38 73 53 58
8
1 5 93
1 7 69
1 1 20
1 6 74
1 7 100
1 9 14
1 6 64
2 2

本該是1，卻輸出13嗎，這其實(shí)是一個越界的值，這里的越界不是因?yàn)闊o限遞歸到2e5+5，而是在merge（10,11）的時候，因?yàn)閒[11]沒有初始化，所以f[11]=0，所以不會報(bào)錯！程序也不會進(jìn)入死循環(huán)但是相當(dāng)于f[..6,7,8,9,10]這些本該=10的，都變?yōu)榱?#61;0;所以覆蓋了之前的結(jié)果！

解決方法也有很多，

1.比如在if中也加上t1<=n。

2.或者初始化的時候for(int i = 1; i<MAX; i++) f[i]=i;而不是只初始化到n，這樣就會在while中給break掉。所以思考問題時要注意整個程序可能用到的下標(biāo)！而不是正解要用到的下標(biāo)，或者說對于輸入數(shù)據(jù)的合法的下標(biāo)！?

3.還是針對初始化，加上rest[n+1] = INT_MAX;

?? ? 即：一般數(shù)組模擬問題都需要初始化一下邊界值，比如從i=1開始讀入數(shù)組，那就需要更新一下a[0],a[n+1]，防止越界！這種題目太多太多，在此不再贅述。總之?dāng)?shù)組模擬真實(shí)情況的場景，最好都處理一下邊界。不然就可能發(fā)生各種無法解釋的腦殘事件。

?

但是針對2和3這兩種方法，會TLE8，不知道為什么、、、

初始化的時候把rest改成全都INT_MAX，也可以AC，，奇怪了

AC代碼：

#include<bits/stdc++.h>using namespace std; const int MAX = 2e5 + 5; int a[MAX],rest[MAX],f[MAX]; int getf(int v) {return f[v] == v ? v : f[v] = getf(f[v]); } void merge(int u,int v) {//默認(rèn)u < vint t1 = getf(u);int t2 = getf(v);if(t1 != t2) f[t1] = t2; } int main() {int n,m,x,y,op;cin>>n;for(int i = 1; i<MAX; i++) f[i]=i,rest[i]=INT_MAX; for(int i = 1; i<=n; i++) scanf("%d",a+i),rest[i]=a[i],f[i]=i;rest[n+1] = INT_MAX;f[n+1] = n+1;cin>>m;while(m--) {scanf("%d",&op);if(op == 2) {scanf("%d",&x);printf("%d\n",a[x] - rest[x]);}else {scanf("%d%d",&x,&y);int t1=getf(x);while(y>0 && t1 <= n) {t1 = getf(t1);if(y>=rest[t1]) {//只能裝rest[t1]的水了 y-=rest[t1];rest[t1]=0;merge(t1,t1+1); }else rest[t1]-=y,y=0;}}}return 0 ;}

總結(jié)：

? ?1WA了啊，因?yàn)闆]加ne[x]<=n這個條件，仔細(xì)想想，為什么要加這個條件。

---

再附一個網(wǎng)絡(luò)版的AC代碼：（是有點(diǎn)記憶化的思想在里面的）

//wlb 記憶化的 也算是并查集吧 #include<bits/stdc++.h> using namespace std; int num[210000],pre[210000],now[210000]; int pour(int x,int y) {if(x==-1) return x;if(now[x]==num[x]) return pre[x]=pour(pre[x],y);else if(now[x]<num[x]) {now[x]+=y;if(now[x]>num[x]) {int t=now[x]-num[x];now[x]=num[x];return pre[x]=pour(pre[x],t);} else return x;} } int main() {int n,a,b,m;cin>>n;for(int i=1; i<=n; i++) {scanf("%d",&num[i]);pre[i]=i+1;now[i]=0;}pre[n]=-1;scanf("%d",&m);while(m--) {int op;scanf("%d",&op);if(op==1) {scanf("%d%d",&a,&b);pour(a,b);} else {scanf("%d",&a);printf("%d\n",now[a]);}}return 0 ; }

---

終于找到了上面那些方法TLE的真正原因！

其實(shí)，改成這樣就好了。

#include<bits/stdc++.h>using namespace std; const int MAX = 2e5 + 5; int a[MAX],rest[MAX],f[MAX]; int getf(int v) {return f[v] == v ? v : f[v] = getf(f[v]); } void merge(int u,int v) {//默認(rèn)u < vint t1 = getf(u);int t2 = getf(v);if(t1 != t2) f[t1] = t2; } int main() {int n,m,x,y,op;cin>>n;for(int i = 1; i<=n; i++) scanf("%d",a+i),rest[i]=a[i],f[i]=i; // rest[n+1] = INT_MAX;f[n+1] = n+1;cin>>m;while(m--) {scanf("%d",&op);if(op == 2) {scanf("%d",&x);printf("%d\n",a[x] - rest[x]);}else {scanf("%d%d",&x,&y);int t1=getf(x);while(t1 <= n && y>0) {if(y>=rest[t1]) {//只能裝rest[t1]的水了 y-=rest[t1];rest[t1]=0;merge(t1,t1+1); t1 = getf(t1); }else rest[t1]-=y,y=0;}}}return 0 ;}

聰明的你一定看得出來，其實(shí)就是把t1 = getf(t1); 移到if里面了，想一下，確實(shí)是啊！我操作完了之后需要準(zhǔn)備出下一個狀態(tài)并交由while去判斷，而不是while完了之后再找下一個狀態(tài)！你如果while完了再轉(zhuǎn)移到下一個狀態(tài)，那肯定要加if(...&& t1<=n)啊！因?yàn)檫@里就需要再判斷一遍while里面的東西！！而因?yàn)橐粋€t1=getf(t1)，其中y沒有參與，所以if里面不需要加上while里面的(y>0)，所以就有了第一個AC代碼的樣子、、、但是其實(shí)你要知道這是不對的！

至于為什么不在if中加(t1<=n)而是在rest[n+1]=INT_MAX這樣是TLE的，我是這樣認(rèn)為，還沒有驗(yàn)證正確性：

? ? ?因?yàn)槟愕南敕ㄊ桥粋€無窮大來表示可以盛放無窮多的水，但是INT_MAX在這里不是無窮大了！這不是圖論啊！每一次倒水的范圍是1e9！所以倒兩次1e9，你這個rest[n+1]無窮大就減沒了，甚至rest[n+1]變成負(fù)數(shù)了，，就進(jìn)入無限遞歸了? ?，因?yàn)閕f(y>=rest[n+1])這個永遠(yuǎn)成立，進(jìn)入if后，y變大了？！然后rest[t1]=0，然后下一層還是可以進(jìn)。。。（不不不，可能就退出while了）

? ?emmm并且如果你沒有for(i=0 -> MAX) f[i]=i的話，那到t1=n的時候，merge(n,n+1)了之后因?yàn)閒[n+1]=n+1了所以沒事，然后到while這里，注意這時候t1還是n！所以還是可以進(jìn)入while，然后merge(n+1,n+2)，，這時候涼涼了，所有以n為根節(jié)點(diǎn)的節(jié)點(diǎn)全都變?yōu)閚+2的祖先節(jié)點(diǎn)，而f[n+2]=0,（因?yàn)闆]有初始化！）所以涼涼，在這之后的操作，我要找倒水的位置了，結(jié)果跑回0節(jié)點(diǎn)這個非法節(jié)點(diǎn)了，然后因?yàn)閞est[0]=0，所以肯定還會進(jìn)這個if，然后merge(0,1)，，這就真涼了，繞圈了。

? ??

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 371D】Vessels（思维，元素合并，并查集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。