Codeforces 371D Vessels【思维+并查集】经典套路题

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 ton, in the order from the highest to the lowest, the volume of thei-th vessel is a_i liters.

$Codeforces 371D Vessels【思维+并查集】经典套路题$

Initially, all the vessels are empty. In some vessels water is poured. All the water that overflows from thei-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 x_i liters of water to thep_i-th vessel;
Print the number of liters of water in the k_i-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·10⁵). The second line containsn integers a₁, a₂, ..., a_n — the vessels' capacities (1 ≤ a_i ≤ 10⁹). The vessels' capacities do not necessarily increase from the top vessels to the bottom ones (see the second sample). The third line contains integerm — the number of queries (1 ≤ m ≤ 2·10⁵). Each of the nextm lines contains the description of one query. The query of the first type is represented as "1 p_i x_i", the query of the second type is represented as "2 k_i" (1 ≤ p_i ≤ n,1 ≤ x_i ≤ 10⁹,1 ≤ k_i ≤ n).

Output

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

ExamplesInput

Output

4
5
8

Input

Output

7
10
5

题目大意：

现在有N个杯子，从上到下编号为1~N排列，现在已知每个杯子的容积，现在有两种操作：

①1 x y 在编号为x的杯子中加入容量为y的水、

当这个杯子满了的时候水会向下流到x+1中，如果x+1也满了，那就流到x+2中...............以此类推。

②2 x 查询编号为x的杯子中有多少容积的水。

思路：

维护一个数组sum【i】表示第i个杯子包含的水的体积。

那么对应我们如果暴力去更新杯子中水的含量的话，时间复杂度最高会达到O（nq）;

所以我们考虑优化。

这里不妨考虑将连续序列（都是满状态）的合并成一个集合，使得查询find（i）的结果是第i个杯子之下第一个未满的杯子的编号。

当find（i）这个杯子满了之后，我们将find（i）和find（i）+1合并上，那么再继续考虑在find（i）+1这个杯子上继续加水。依次类推。

更新水量的时候拿并查集跑一下就行了，时间复杂度O（nlogn）；

Ac代码：

#include<stdio.h>
#include<string.h>
using namespace std;
int n;
int sum[1500000];
int a[15000000];
int f[15000000];
int find(int a)
{
    int r=a;
    while(f[r]!=r)
    r=f[r];
    int i=a;
    int j;
    while(i!=r)
    {
        j=f[i];
        f[i]=r;
        i=j;
    }
    return r;
}
void  merge(int x,int y)
{
    int X=find(x);
    int Y=find(y);
    if(X>Y)
    {
        f[Y]=X;
    }
    else f[X]=Y;
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            f[i]=i;
        }
        f[n+1]=n+1;
        int q;
        scanf("%d",&q);
        while(q--)
        {
            int op;
            scanf("%d",&op);
            if(op==1)
            {
                int x,have;
                scanf("%d%d",&x,&have);
                while(have>0)
                {
                    int F=find(x);
                    if(F==n+1)break;
                    if(a[F]-sum[F]>=have)
                    {
                        sum[F]+=have;
                        have=0;
                    }
                    else
                    {
                        have-=a[F]-sum[F];
                        sum[F]=a[F];
                        merge(F,F+1);
                    }
                    x=F;
                }
            }
            if(op==2)
            {
                int x;
                scanf("%d",&x);
                printf("%d\n",sum[x]);
            }
        }
    }
}

秒客网

Codeforces 371D Vessels【思维+并查集】经典套路题

相关文章