C++ 解法, 执行用时: 74ms, 内存消耗: 4744KB, 提交时间: 2021-08-25

#include<stdio.h>
#include<functional>
using namespace std;
using ll = long long;
#define N 200001
ll v[N];
ll p[N];
int to[N];
int main()
{
    int n, m;
    while (~scanf("%d%d", &n, &m))
    {
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &v[i]);
            p[i] = 0;
            to[i] = i;
        } 
        function<int(int,ll,int)> Add = [&](int x, ll y, int k)
        {
            if (x > n) return n+1;
            if (p[x] == v[x] && to[x] != x)
            {
                to[x] = Add(to[x], y, k+1);
            }
            else 
            {
                if (p[x]+y >= v[x])
                    to[x] = Add(x+1, p[x]+y-v[x], k+1);
                p[x] = min(p[x]+y, v[x]);
            }
            return to[x];
        };
        int t;
        for (int i = 0; i < m; ++i)
        {
            int x, y;
            scanf("%d%d", &t, &x);
            if (t == 2) scanf("%d", &y);
            if (t == 1) printf("%d\n", p[x]);
            else Add(x, y, 0);
        }
    }
}

C++ 解法, 执行用时: 79ms, 内存消耗: 3192KB, 提交时间: 2020-10-29

#include<bits/stdc++.h>

const int MAXN=200015;

using namespace std;
int mark[MAXN],a[MAXN],b[MAXN];

int _find(int x){
    if(x==0)return x;
    if(a[x]!=b[x])return x;
    return mark[x]=mark[x+1]=_find(mark[x+1]);
}

int main(){
    int n,m,x,y,d;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=0;
        mark[i]=i;
    }
    int op;
    while(m--){
        scanf("%d",&op);
        if(op==2){
            scanf("%d%d",&x,&y);
            while(y){
                x=_find(x);
                if(x==0)break;
                d=min(a[x]-b[x],y);
                b[x]+=d;
                y-=d;
            }
        }else{
            scanf("%d",&x);
            printf("%d\n",b[x]);
        }
    }
    return 0;
}