There is a system ofn vessels arranged one above the otheras 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 thei-th vessel isai liters.
Initially, all the vessels are empty. In some vessels water ispoured. All the water that overflows from thei-th vessel goes to the(i + 1)-th one. The liquid thatoverflows from the n-th vessel spills on the floor.
Your task is to simulate pouring water into the vessels. To dothis, you will need to handle two types of queries:
1. Addxi liters of water to the pi-th vessel;
2. Print the number of liters of water in theki-th vessel.
When you reply to the second request you can assume that all thewater poured up to this point, has already overflown between the vessels.
Input
The first line contains integern — the number of vessels (1 ≤ n ≤ 2·105). The second line containsn integersa1, a2, ..., an — the vessels' capacities(1 ≤ ai ≤ 109). The vessels' capacitiesdo not necessarily increase from the top vessels to the bottom ones (see thesecond sample). The third line contains integerm — the number of queries (1 ≤ m ≤ 2·105). Each of the next m lines contains the description of onequery. The query of the first type is represented as "1 pi xi", the query of thesecond 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 thecorresponding 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
【题意】有n个有固定容积的容器从下往上依次堆叠，从上往下为他们编号：1~n，现在有q个两种操作，一种是往第i个盘子中注水(如果满出，则多余的水流入第i+1个盘子，以此类推，如果最后一个盘子满出，多余的水流向地面，不再计算)，还有一种操作是输出第i个盘子现在的水量。
【分析】由于n,q较大，如果利用暴力去更新水量的话，复杂度高达O(n*q)显然会超时，那我们就要想办法去掉在一系列都已经盛满的容器间转移的时间。所以我们就需要把连续的装满水的容器合并成一个，这样就能大大优化时间。
具体实现方法就是利用并查集，如果注水时当前容器已满，那么就把与下一个容器合并，即pre[i]=i+1，(其实应该是pre[find(i)]=find(i+1),即并查集里的 join ()函数)，而且我们每次开始注水时，应该直接对find(i)注水。
这样的做法就可以在O(nlogn)的时间复杂度下出结果啦。
#include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; #define mst(a,b) memset((a),(b),sizeof(a)) #define f(i,a,b) for(int i=(a);i<=(b);++i) #define rush() int T;scanf("%d",&T);while(T--) typedef long long ll; const int maxn=200005; const ll mod = 1e9+7; const int INF = 0x3f3f3f3f; const double eps = 1e-6; int pre[maxn]; int a[maxn]; int ans[maxn]; int find(int x) { int t,r=x; while(pre[x]!=x) { x=pre[x]; } while(r!=x) { t=pre[r]; pre[r]=x; r=t; } return x; } void join(int a,int b) { int A=find(a); int B=find(b); if(A>B) { pre[B]=A; } else pre[A]=B; } int main() { int n,m; int order; int pos,w; scanf("%d",&n); mst(ans,0); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); pre[i]=i; } pre[n+1]=n+1; //特别注意 scanf("%d",&m); for(int i=0;i<m;i++) { scanf("%d",&order); if(order==1) { scanf("%d%d",&pos,&w); while(w>0) { pos=find(pos); if(pos==n+1) //特别注意 break; if(a[pos]-ans[pos]>w) { ans[pos]+=w; w=0; } else { w-=(a[pos]-ans[pos]); ans[pos]=a[pos]; join(pos,pos+1); } } } else if(order==2) { scanf("%d",&pos); printf("%d\n",ans[pos]); } } return 0; }
