CF2002E Cosmic Rays 题解
int08
·
·
题解
前言
你觉得你是 *2300 吗？
我觉得我是。
简要题意
一个序列，每次消掉所有极长连续相等段的第一个数，问多少秒消完。
现在序列初始为空动态添加 n 次，每次在末尾加入 a_i 个 b_i，每次加入都回答一次这个问题。
# Solution
第一反应是 $\max a_i$，但是不对，因为后面可能跟前面相等的数合并（当中间全部消耗完的时候），合并之后两段合起来了，每次只消一个数，用时就会变长。
然后发现两个同颜色段能合并当且仅当中间都比他们短，而且一旦合并了，中间就没有意义了（因为已经完全被隔开了），不可能再和后面加入的合并或者影响答案的。
另外如果后面添加的比前面的多，前面也不可能和后面加入的合并，也没必要留着了。
于是想到维护一个单调栈，这题就结束了。
具体的，维护一个数量依次递减的单调栈，每次从最后一个一个把栈顶不同色且更小的弹出，碰到同色就吸收，具体的，设现在加入的数量为 $a$，栈顶同色的为 $x$，刚刚弹出的异色栈顶为 $y$，则合并为 $a+x-y$ 继续下传。
每次答案就是栈底。
## AC Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 333664
pair<int,int> sta[N];
int pt,n,i,j,a[N],b[N],T;
signed main()
{
cin>>T;
while(T--)
{
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i]>>b[i];b[i]++;
while(pt>0&&sta[pt].first<=a[i])
{
if(sta[pt-1].second==b[i]) a[i]+=sta[pt-1].first-sta[pt].first,pt--;
pt--;
}
sta[++pt]={a[i],b[i]};
cout<<sta[1].first<<" ";
}
cout<<endl;
pt=0;
}
return 0;
}
```
The End.