碼蹄集OJ-小碼哥的棧

#include<bits/stdc++.h> 
using namespace std;
#define int long long
const int N=1e6+7;
struct MOOE
{int ll,rr;
};
stack<MOOE>st;
signed main( )
{ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;while(n--){int opt;cin>>opt;if(opt==1){int l,r;cin>>l>>r;st.push({l,r});}if(opt==2){int k;cin>>k;int result=0;while(k){int l=st.top().ll;int r=st.top().rr;int size=r-l+1;if(k<size){result+=(2*r-k+1)*k/2;st.pop();st.push({l,r-k});k=0;}else{result+=(l+r)*size/2;k-=size;st.pop();}}        cout<<result<<endl;}}return 0;
}

定義一個結構體MOOD變量，含有ll與rr兩個成員。定義一個st棧保存節點（棧內節點可以是一個數也可以是一個范圍），每次 push({l, r}) 就是把一個 MOOE 對象壓棧，也就是棧內的每個節點都有兩個成員。

當輸入的opt為1時，將范圍作為節點壓入棧中。

當輸入的opt為2時，要考慮k的兩種情況：一種可能小于棧頂范圍，一種大于棧頂范圍。如果小于棧頂范圍，通過等差數列求和公式得出結果；當大于棧頂范圍時，只要將棧頂范圍的和求出后，再pop出后，反復多次還會回到第一種情況中。在兩種條件外套上大循環，當是第一種情況，循環停止，第二種情況時，將k減去pop出的節點的大小，再進入循環。