P7870 「Wdoi-4」兔已着陆

P7870 「Wdoi-4」兔已着陆 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：发现 k k k很大，不能暴力，但是对于放入的 l . . . r l...r l...r来说可以整段整段的取出来。因此将 ( l , r ) (l,r) (l,r)存入栈中，取出时依次出栈即可。

令 l e n = r − l + 1 len = r - l + 1 len=r−l+1

• 如果 k ≥ l e n k \ge len k≥len：这整段全部用上的值为：
  l e n × l + l e n × ( l e n − 1 ) / 2 len \times l + len \times (len - 1) /2 len×l+len×(len−1)/2

• 如果 k < l e n k \lt len k<len：只用一部分，并将 [ l , r ] [l, r] [l,r]修改为 [ l , r − k ] [l, r - k] [l,r−k]
  k × r − k × ( k − 1 ) / 2 k \times r - k \times (k - 1) / 2 k×r−k×(k−1)/2

代码如下：

#include <bits/stdc++.h>
using namespace std;
struct no {
    int l, r;
};
int main()
{
    int n; cin>>n;
    vector<no> stk;
    for(int i = 0; i < n; ++i) {
        int op; cin>>op;
        if(op == 1) {
            int l, r; cin>>l>>r;
            stk.push_back({l, r});
        } else {
            long long k,sum = 0; cin>>k;
            while(stk.size() && k) {
                auto t = stk.back(); stk.pop_back();
                long long len = t.r - t.l + 1;
                if(k >= len) {
                    sum += len * t.l + len * (len - 1) / 2;
                    k -= len;
                } else {
                    sum += k * t.r - k * (k - 1) / 2;
                    t.r -= k;
                    stk.push_back(t);
                    k = 0;
                }
            }
            cout<<sum<<'\n';
        }
    }
}

感觉用结构体比用stl容器的pair<int,int>或array<int,2>要方便的多（