雅礼集训2019 D7T2 Subsequence
直接贴题解：
平衡树代码：
#include<bits/stdc++.h>
#define ll long long
#define N 100005using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n;
ll a[N];
int ch[N][2],fa[N];
int size[N];
ll p[N];
#define ls ch[v][0]
#define rs ch[v][1]
int rt;
void update(int v) {size[v]=size[ls]+size[rs]+1;}
ll add[N];void Add(int v,ll f) {p[v]+=f;add[v]+=f;
}void down(int v) {if(add[v]) {if(ls) Add(ls,add[v]);if(rs) Add(rs,add[v]);add[v]=0;}
}void rot(int v) {int f=fa[v],gr=fa[f];int sn=v==ch[f][1],son=ch[v][!sn];if(gr) ch[gr][f==ch[gr][1]]=v;ch[f][sn]=son;ch[v][!sn]=f;fa[v]=gr,fa[f]=v;if(son) fa[son]=f;update(f),update(v);
}void splay(int v) {static int st[N],top;st[top=1]=v;for(int i=v;fa[i];i=fa[i]) st[++top]=fa[i];for(int i=top;i>=1;i--) down(st[i]);while(fa[v]) {int f=fa[v],gr=fa[f];if(gr) rot(f==ch[gr][1]^v==ch[f][1]?v:f);rot(v);}rt=v;
}int tot;
int Find(int k) {int v=rt;while(1) {if(size[ls]+1==k) return v;if(size[ls]>=k) v=ls;else k-=size[ls]+1,v=rs;}
}int Find_rk(int v) {splay(v);return size[ls]+1;
}void Insert(int &v,int k,int id) {if(!v) {v=id;update(v);return ;}if(size[ls]>=k-1) {Insert(ls,k,id);fa[ls]=v;} else {Insert(rs,k-size[ls]-1,id);fa[rs]=v;}update(v);
}int pos;
void binary(int v,ll a,int pre,int &pos) {if(!v) return ;down(v);ll now=pre+size[ls]+1;if(a*now>=p[v]) {pos=v;binary(ls,a,pre,pos);} else binary(rs,a,pre+size[ls]+1,pos);
}void out(int v,ll &ans) {if(!v) return ;down(v);out(ls,ans);ans+=p[v];cout<<ans<<" ";out(rs,ans);
}int main() {n=Get();for(int i=1;i<=n;i++) a[i]=Get();rt=1;update(rt);p[rt]=a[1];for(int i=2;i<=n;i++) {binary(rt,a[i],0,pos=i);if(pos!=i) splay(pos);int rk=pos==i?i:Find_rk(pos);p[i]=a[i]*rk;Insert(rt,rk,i);splay(i);if(ch[i][1]) Add(ch[i][1],a[i]);}ll ans=0;out(rt,ans);return 0;
}
转载于:https://www.cnblogs.com/hchhch233/p/11085339.html
本文链接：https://my.lmcjl.com/post/19985.html
展开阅读全文
4 评论