题解 P7870 【「Wdoi-4」兔已着陆】

囧仙 · 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;
}