自动搬运

查看原文

来自洛谷，原作者为

	囧仙 你做东方鬼畜音MAD，好吗？

搬运于2025-08-24 22:33:50，当前版本为作者最后更新于2021-09-23 21:52:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解

考虑使用一个二元组 $(l,r)$ 表示压入栈中的数据 $l,l+1,l+2\cdots r-1,r$。队列里直接存储这样的二元组。

• 对于操作 $1$，直接压入栈中。

• 对于操作 $2$，不断取出栈顶元素 $(l_0,r_0)$。若它的长度 $r_0-l_0+1$ 不大于当前的 $k$，那么就直接弹出该元素，计入答案，并让 $k$ 减去这个区间的长度；否则我们需要将 $(l_0,r_0)$ 裂成两个二元组 $(l_0,r_0-k)$ 和 $(r_0-k+1,r_0)$。前者重新压入栈中，后者计入答案，然后终止循环。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
const int MAXN=1e6+3;
i64 qread(){
    i64 w=1,c,ret;
    while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0';
    return ret*w;
}
int n,p; pair<int,int> P[MAXN];
int main(){
    n=qread(); up(1,n,i){
        int op=qread();
        if(op==1){
            int l=qread(),r=qread(); P[++p]=make_pair(l,r);
        } else {
            i64 k=qread(); i64 ans=0;
            while(k){
                int l=P[p].first,r=P[p].second,t=r-l+1;
                if(t<=k) ans+=1ll*t*(l+r)/2,k-=t,--p;
                else {
                    ans+=1ll*k*(r-k+1+r)/2;
                    P[p]=make_pair(l,r-k),k=0;
                }
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}