放在前面

  这次比赛的表现十分拉胯，高光点只有13分钟做出了前两题，然后直接罚坐。
  经常遇到这类问题但是总是感觉少点东西才能做出来，总会有些地方不知道应该怎么处理。其实总结来看，无非就是这么几种情况，有些情况之前的博客已经说过了。例如二分和尺取，但是尺取往往用处十分优先，仅在某些特性数据量比较小且十分有限的情况下，例如英文字母。>经常遇到这类问题但是总是感觉少点东西才能做出来，总会有些地方不知道应该怎么处理。其实总结来看，无非就是这么几种情况，有些情况之前的博客已经说过了。例如二分和尺取，但是尺取往往用处十分优先，仅在某些特性数据量比较小且十分有限的情况下，例如英文字母。

补充

这类问题往往可以使用线段树等数据结构进行维护，这自然是不用说的。也存在某些题既可以使用线段树也可以根据其中的其他特性通过别的数据结构进行维护，例如堆数据结构。这个题可以使用上述两种方法同时也可以使用差分（这里没看出=.=）。

Tea Tasting

题意

大意是给出n种茶的数量，有n个人品尝这些茶，依次排队进行（详细看题意）每个人最多喝bi数量的茶，最后求出每个人的喝茶量。

解决方法1线段树

通过线段树进行维护，对于每个ai，我们查找一次前缀和，然后对某个区间进行维护bi的数量，对于多余数量直接存到一个数组即可。线段树维护+1即可，最后直接算这个数存在的值的倍数然后加上re数组。

code：

void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],w[i]=0,re[i]=0;
    for(int i=1;i<=n;i++){
        cin>>b[i];
        s[i] = s[i-1] + b[i];
    }
    ll sum = 0;
    build(1,1,n);
    for(int i=1;i<=n;i++){
        int pos = upper_bound(s+i,s+n+1,a[i]+sum) - s;
        if(s[pos-1]==a[i]+sum){
            modify(1,i,pos-1,1);
        }else{
            if(pos-1<i) ;
            else modify(1,i,pos-1,1);
            ll tt = a[i]+sum-s[pos-1];
            re[pos] += min(b[pos],tt);
        }
        sum+=b[i];
    }
    for(int i=1;i<=n;i++){
        ll tt = query(1,i,i);
        cout<<tt*b[i]+re[i]<<' ';
    }
    cout<<endl;
}

解决方法2优先队列维护

感觉很神奇的方法，十分巧妙。大部分选手都是用的差分数组来做的，大佬的话直接上线段树去维护也没什么问题。用优先队列维护，维护的是当前第i个人品尝完之后还可以继续被品尝的数据。这里可以直接用一个数累计统计，这里初始化与否并不影响实际答案。但是经过思考后认为直接开longlong类型记录所有更好一些。

code:

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    ll t = 0;
    priority_queue<ll, vector<ll>, greater<ll>> q;
    ll res = 0;
    for(int i=1;i<=n;i++){
        res = 0;
        q.push(a[i]+t);
        while(q.top()<b[i]+t&&!q.empty()){
            res+=q.top()-t;
            q.pop();
        }
        if(q.size()){
            t+=b[i];
            res+=q.size()*b[i];
        }
        cout<<res<<' ';
    }
    cout<<endl;
}

解决方法3差分数组

说不会吧也不是不会，但是考虑不到，差分的题还是做的少。大概的意思就是我们总能通过前缀和差分来巧妙的找到某个bi的倍数。我们只需要根据ai来确定在哪个位置停下即可，剩下的对差分数组进行前缀和，ans用来处理一些剩余的边边角角。

code:

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=b[i]=d[i]=ans[i] = 0;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        s[i] = s[i-1] + b[i];
    }
    for(int i=1;i<=n;i++){
        ll sum = s[i-1]+a[i];
        int pos = lb(s+i,s+n+1,sum) - s;
        d[i]++;
        if(pos>n) continue;
        d[pos]--;
        ans[pos]+=a[i]-(s[pos-1]-s[i-1]);
    }
    for(int i=1;i<=n;i++){
        d[i]+=d[i-1];
    }
    for(int i=1;i<=n;i++){
        ans[i]+=d[i]*b[i];
        cout<<ans[i]<<' ';
    }
    cout<<endl;
}