CF1998E2 sol
Eternatis
·
·
题解
考虑 E1 的分治解法，其过程相当于一棵笛卡尔树，而笛卡尔树可以通过维护右链 $O(n)$ 建，于是考虑动态维护需要的信息。
注意到在构造笛卡尔树时，一个点一旦被作为某个点的左子树，其信息就**不再改变**，即维护的右链上，每个点的左子树答案确定，考虑对当前栈内每个点，维护**根与左子树**的权值和与贡献和，记作 $sum$ 与 $w$ ，这样从栈中删除点并挂到左儿子上的过程是简单的。
现在考虑加点时，对栈中元素 $sum$ 值的影响。
考虑这相当于对插入的元素到根的链进行链加，但注意到每次插入元素时，其最终会作为右链的结尾，于是可以直接维护一个全局加标记 $tag$ ，再记录一个 $r$ 表示当前元素还需要加多少变为合法，即子树权值和不小于父节点权值。
用一个队列维护上述过程，每次判断队头是否合法，若已经合法就出队，这样每个元素只会入队出队一次。注意初始化每个元素的 $r$ 时消去当前标记的影响即可。
最后只剩求答案的部分，考虑当前队头，即第一个不合法位置，因为每个点都维护了左子树的信息，所以当前的答案相当于栈内元素 $w$ 值的前缀和，在将元素插入栈内时维护即可。
注意因为会从栈顶删数，队列里可能会存在不在栈中的元素，开个数组记录一下就好了。
code：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define int long long
#define db long double
#define pii pair<int,int>
#define st first
#define ed second
#define mkp make_pair
#define pb push_back
#define eps 1e-9
#define mod 998244353
#define mod2 1000000007
#define bs 13131
#define bs2 131
#define INF 0x3f3f3f3f3f3f3f3f
#define il inline
#define vi vector<int>
#define ins insert
#define umap unordered_map
#define uset unordered_set
#define R(x) x.begin(),x.end()
#define B(x) x.begin()
#define E(x) x.end()
#define lb lower_bound
#define ub upper_bound
#define vi vector<int>
il int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int T=1,n,m,q,k;
int s[N],sum[N],w[N]; // sum 和 w 记录栈内左子树信息
int stk[N],top;
int sm[N],val[N]; // sm 与 tag 对应，用来维护栈内元素是否合法，val 记录栈内贡献前缀和
bool instk[N]; // instk 记录是否在栈内，防止队列未及时清空
il void solve(){
n=read();m=read();
for(int i=1;i<=n;i++)
s[i]=read(),sum[i]=w[i]=sm[i]=val[i]=instk[i]=0;
top=0;
int tag=0;
queue<int> q;
for(int i=1;i<=n;i++){
int k=top;
while(k&&s[stk[k]]<s[i])k--;
sum[i]=s[i],w[i]=1;
while(top>k+1){ // 合并栈顶到当前节点
if(sum[stk[top]]>=s[stk[top-1]])
w[stk[top-1]]+=w[stk[top]];
sum[stk[top-1]]+=sum[stk[top]];
instk[stk[top]]=0;
top--;
}
if(top>k){ // 特判最后一个元素是否合并（可能出现当前元素加入即为栈顶的情况）
if(sum[stk[k+1]]>=s[i])
w[i]+=w[stk[k+1]];
sum[i]+=sum[stk[k+1]];
instk[stk[k+1]]=0;
}
stk[k+1]=i;top=k+1;
instk[i]=1;
tag+=s[i];
sm[i]=s[stk[top-1]]+tag-sum[i]; // 消除已有 tag 的影响
val[i]=val[stk[top-1]]+w[i];
q.push(i);
while(!q.empty()){
int x=q.front();
if(tag>=sm[x]||!instk[x])q.pop();
else break;
}
if(q.empty())printf("%lld ",val[i]);
else {
int p=q.front();
printf("%lld ",val[p]-w[p]);
}
}
puts("");
}
signed main(){
T=read();
while(T--)solve();
return 0;
}
```