其实非常好理解..就是可以可以合并起来的两个堆嘛><
嗯这道题XJOI上有然后当时并没有做...看到满屏的splay吓傻
题意大概就是求出每个节点子树中权值加和不大于一个给定值m的最多个数，也就是尽量取小的
之前并不会可并堆..然后脑补了一个每次msort的递归做法，T掉了
实际上我们可以反过来考虑，假设一个节点u的子树的大小为sz，在薪水总数不超过m的情况下能取x个，
也就是有sz-x个数在这个节点的答案中是用不到的
实际上在u以上的节点也用不到，有了这个性质我们就可以用可并堆然后每次不停地把子树中最大的删去直到满足sum<=m
/**************************************************************
Problem: 2809
User: mjy0724
Language: C++
Result: Accepted
Time:1284 ms
Memory:9188 kb
****************************************************************/ #include<cstdio>
#include<cstdlib>
#include<cstring>
#define ll long long
#define maxn 100010
struct node{
int l,r;
ll sum,sz;
}a[maxn];
ll n,e,c[maxn],root[maxn],fa[maxn],next[maxn],link[maxn];
ll ans,l[maxn],k;
ll max(ll x,ll y){
if (x>y) return x;return y;
}
void swap(int &x,int &y){
int tmp=x;x=y;y=tmp;
}
int merge(int x,int y){
if (x==||y==) return x+y;
if (c[x]<c[y]) swap(x,y);
a[x].r=merge(a[x].r,y);
swap(a[x].l,a[x].r);
return x; //这条语句经常忘记写啊tat!
}
void add(int x,int y){
fa[++e]=y;next[e]=link[x];link[x]=e;
}
void dfs(int p){
a[p].sum=c[p];a[p].sz=;root[p]=p;
for (int i=link[p];i;i=next[i]){
dfs(fa[i]);
a[p].sum+=a[fa[i]].sum;
a[p].sz+=a[fa[i]].sz;
root[p]=merge(root[p],root[fa[i]]);
}
while (a[p].sum>k){
a[p].sum-=c[root[p]];a[p].sz--;
root[p]=merge(a[root[p]].l,a[root[p]].r);
}
ans=max(ans,(ll)a[p].sz*l[p]);//边dfs边更新答案
}
int main(){
scanf("%lld%lld",&n,&k);
e=;ans=;int x;
for (int i=;i<=n;i++) scanf("%d%lld%lld",&x,&c[i],&l[i]),add(x,i);
dfs();
printf("%lld\n",ans);
}
也是非常裸的一道题...kill操作的时候不仅要把当前root的fa改成新合并之后的根
新合并之后的根的fa也要及时改掉不然会死循环
其他的就和上一题差不多了..往往要和并查集结合起来做
然后这道题加了两行成了左偏树
/**************************************************************
Problem: 1455
User: mjy0724
Language: C++
Result: Accepted
Time:2320 ms
Memory:21312 kb
****************************************************************/ #include<cstdio>
#include<cstdlib>
#include<cstring>
#define maxn 1000010
struct arr{
int ave,l,r;
}a[maxn];
int fa[maxn],n,m,d[maxn];
bool vis[maxn];
char s[];
int getfa(int x){
if (fa[x]==x) return x;
fa[x]=getfa(fa[x]);
return fa[x];
}
void swap(int &x,int &y){
int tem=x;x=y;y=tem;
}
int merge(int x,int y){
if (x==||y==) return x+y;
if (a[y].ave<a[x].ave) swap(x,y);
a[x].r=merge(a[x].r,y);
if (d[a[x].l]<d[a[x].r]) swap(a[x].l,a[x].r);
d[x]=d[a[x].r]+;
return x;
}
void mer(int x,int y){
if (vis[x]==false||vis[y]==false||getfa(x)==getfa(y)) return;
x=getfa(x);y=getfa(y);
fa[x]=fa[y]=merge(x,y);
}
int sol(int x){
if (vis[x]==false) return ;
int tmp=a[getfa(x)].ave;
vis[fa[x]]=false;
int y=merge(a[fa[x]].l,a[fa[x]].r);
fa[fa[x]]=y;fa[y]=y;
return tmp;
}
int main(){
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d",&a[i].ave);
d[]=-;scanf("%d",&m);
memset(vis,true,sizeof(vis));
for (int i=;i<=n;i++) fa[i]=i;
char ch[];int x,y;
for (int i=;i<=m;i++){
scanf("%s",ch);
if (ch[]=='M') scanf("%d%d",&x,&y),mer(x,y);
else scanf("%d",&x),printf("%d\n",sol(x));
}
return ;
}
这道题的结论证明参见论文
对于求不下降序列最后的做法就是：维护几段连续的序列，使它们的中位数不下降
然而转化到递增序列，我们只需要将每个数读进来的之后减去它的下标就可以了
所以我们对于每一段已求好的序列，既要维护它的中位数，又要支持合并
因为我们合并的前提是：中位数(i)>中位数(i+1)，那么对于合并后的i而言，中位数肯定是不升的
根据这个性质我们又可以用可并堆了，堆顶元素表示该序列中的中位数
当堆的元素个数*2>序列长度+1的时候就可以弹出堆顶
/**************************************************************
Problem: 1367
User: mjy0724
Language: C++
Result: Accepted
Time:8440 ms
Memory:35960 kb
****************************************************************/ #include<cstdio>
#include<cstdlib>
#include<cstring>
#define maxn 1000010
#define ll long long
struct arr{
int l,r,sz,rt;
}a[maxn];
int l[maxn],r[maxn],d[maxn],n,cnt;
ll b[maxn];
void swap(int &x,int &y){
int tmp=x;x=y;y=tmp;
}
int merge(int x,int y){
if (x==||y==) return x+y;
if (b[y]>b[x]) swap(x,y);
r[x]=merge(r[x],y);
if (d[l[x]]<d[r[x]]) swap(l[x],r[x]);
d[x]=d[r[x]]+;
return x;//然而啊这道题又是因为这一句没加调了1h
}
void mer(int x,int y){
int lx=a[x].l,rx=a[y].r,size=a[x].sz+a[y].sz,rt=merge(a[x].rt,a[y].rt);
a[x].l=lx;a[x].r=rx;a[x].sz=size;a[x].rt=rt;cnt--;
while (a[x].sz*>(a[x].r-a[x].l+)){
a[x].rt=merge(l[a[x].rt],r[a[x].rt]);a[x].sz--;
}
}
int main(){
scanf("%d",&n);d[]=-;
for (int i=;i<=n;i++) scanf("%d",&b[i]),b[i]-=i;
cnt=;
for (int i=;i<=n;i++){
a[++cnt].l=i;a[cnt].r=i;a[cnt].sz=;a[cnt].rt=i;
while (cnt>&&b[a[cnt].rt]<b[a[cnt-].rt]) mer(cnt-,cnt);
}
ll ans=;
for (int i=;i<=cnt;i++)
for (int j=a[i].l;j<=a[i].r;j++) ans+=abs(b[a[i].rt]-b[j]);
printf("%lld\n",ans);
return ;
}