CF2002E Cosmic Rays \(\star\)
顺着询问想增加二元组 \((a,b)\) 的影响。只需要考虑它的合并情况,即尾部什么时候会出现数字 \(b\),而总时间可以看作是最后一个尾部的存在时间,所以我们只需要关心尾部
用栈维护尾部的数值和存在时间(不难发现这是一个单调栈)
vector<pair<LL,int>> s;
For(i,1,n) {
LL a, mx = 0; int b; cin>>a>>b;
while( sz(s) && (a >= s.back().fi || b == s.back().se) ) {
if( b == s.back().se ) a += s.back().fi - mx;
else mx = s.back().fi;
s.pop_back();
}
s.pb(a,b);
cout<<s.front().fi<<" ";
}
https://codeforces.com/problemset/problem/2002/D2
标签:structures,back,尾部,2400,fi,2100,data,mx From: https://www.cnblogs.com/ft61/p/18391696