转载

[BZOJ2809&1455&1367]解题报告|可并堆

其实非常好理解..就是可以可以合并起来的两个堆嘛><

2809: [Apio2012]dispatching

Description

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。在这个帮派里，有一名忍者被称之为 Master。除了 Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，就不需要支付管理者的薪水。你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。写一个程序，给定每一个忍者 i的上级 Bi，薪水Ci，领导力L i，以及支付给忍者们的薪水总预算 M，输出在预算内满足上述要求时顾客满意度的最大值。

1 ≤N ≤ 100,000 忍者的个数；

1 ≤M ≤ 1,000,000,000 薪水总预算；

0 ≤Bi < i 忍者的上级的编号；

1 ≤Ci ≤ M 忍者的薪水；

1 ≤Li ≤ 1,000,000,000 忍者的领导力水平。

嗯这道题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==0||y==0) 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=1;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=0;ans=0;int x;  for (int i=1;i<=n;i++) scanf("%d%lld%lld",&x,&c[i],&l[i]),add(x,i);  dfs(1);  printf("%lld/n",ans); }

1455: 罗马游戏

Description

罗马皇帝很喜欢玩杀人游戏。他的军队里面有n个人，每个人都是一个独立的团。最近举行了一次平面几何测试，每个人都得到了一个分数。皇帝很喜欢平面几何，他对那些得分很低的人嗤之以鼻。他决定玩这样一个游戏。它可以发两种命令： 1. Merger(i, j)。把i所在的团和j所在的团合并成一个团。如果i, j有一个人是死人，那么就忽略该命令。 2. Kill(i)。把i所在的团里面得分最低的人杀死。如果i这个人已经死了，这条命令就忽略。皇帝希望他每发布一条kill命令，下面的将军就把被杀的人的分数报上来。（如果这条命令被忽略，那么就报0分）

也是非常裸的一道题...kill操作的时候不仅要把当前root的fa改成新合并之后的根

新合并之后的根的fa也要及时改掉不然会死循环

其他的就和上一题差不多了..往往要和并查集结合起来做

然后这道题加了两行成了左偏树

 1 /**************************************************************  2     Problem: 1455  3     User: mjy0724  4     Language: C++  5     Result: Accepted  6     Time:2320 ms  7     Memory:21312 kb  8 ****************************************************************/  9   10 #include<cstdio> 11 #include<cstdlib> 12 #include<cstring> 13 #define maxn 1000010 14 struct arr{ 15     int ave,l,r; 16 }a[maxn]; 17 int fa[maxn],n,m,d[maxn]; 18 bool vis[maxn]; 19 char s[100]; 20 int getfa(int x){ 21     if (fa[x]==x) return x; 22     fa[x]=getfa(fa[x]); 23     return fa[x]; 24 } 25 void swap(int &x,int &y){ 26     int tem=x;x=y;y=tem; 27 } 28 int merge(int x,int y){ 29     if (x==0||y==0) return x+y; 30     if (a[y].ave<a[x].ave) swap(x,y);         31     a[x].r=merge(a[x].r,y); 32     if (d[a[x].l]<d[a[x].r]) swap(a[x].l,a[x].r); 33     d[x]=d[a[x].r]+1; 34     return x; 35 } 36 void mer(int x,int y){ 37     if (vis[x]==false||vis[y]==false||getfa(x)==getfa(y)) return; 38     x=getfa(x);y=getfa(y); 39     fa[x]=fa[y]=merge(x,y);  40 } 41 int sol(int x){ 42     if (vis[x]==false) return 0; 43     int tmp=a[getfa(x)].ave; 44     vis[fa[x]]=false; 45     int y=merge(a[fa[x]].l,a[fa[x]].r); 46     fa[fa[x]]=y;fa[y]=y;     47     return tmp; 48 } 49 int main(){ 50     scanf("%d",&n); 51     for (int i=1;i<=n;i++) scanf("%d",&a[i].ave); 52     d[0]=-1;scanf("%d",&m); 53     memset(vis,true,sizeof(vis)); 54     for (int i=1;i<=n;i++) fa[i]=i; 55     char ch[10];int x,y; 56     for (int i=1;i<=m;i++){ 57         scanf("%s",ch); 58         if (ch[0]=='M') scanf("%d%d",&x,&y),mer(x,y); 59         else scanf("%d",&x),printf("%d/n",sol(x));   60     } 61     return 0; 62 }

1367: [Baltic2004]sequence

Description

这道题的结论证明参见论文

对于求不下降序列最后的做法就是：维护几段连续的序列，使它们的中位数不下降

然而转化到递增序列，我们只需要将每个数读进来的之后减去它的下标就可以了

所以我们对于每一段已求好的序列，既要维护它的中位数，又要支持合并

因为我们合并的前提是：中位数(i)>中位数(i+1)，那么对于合并后的i而言，中位数肯定是不升的

根据这个性质我们又可以用可并堆了，堆顶元素表示该序列中的中位数

当堆的元素个数*2>序列长度+1的时候就可以弹出堆顶

 1 /**************************************************************  2     Problem: 1367  3     User: mjy0724  4     Language: C++  5     Result: Accepted  6     Time:8440 ms  7     Memory:35960 kb  8 ****************************************************************/  9   10 #include<cstdio> 11 #include<cstdlib> 12 #include<cstring> 13 #define maxn 1000010 14 #define ll long long 15 struct arr{ 16     int l,r,sz,rt; 17 }a[maxn]; 18 int l[maxn],r[maxn],d[maxn],n,cnt; 19 ll b[maxn]; 20 void swap(int &x,int &y){ 21     int tmp=x;x=y;y=tmp; 22 } 23 int merge(int x,int y){ 24     if (x==0||y==0) return x+y; 25     if (b[y]>b[x]) swap(x,y); 26     r[x]=merge(r[x],y); 27     if (d[l[x]]<d[r[x]]) swap(l[x],r[x]); 28     d[x]=d[r[x]]+1; 29     return x;//然而啊这道题又是因为这一句没加调了1h 30 } 31 void mer(int x,int y){ 32     int lx=a[x].l,rx=a[y].r,size=a[x].sz+a[y].sz,rt=merge(a[x].rt,a[y].rt); 33     a[x].l=lx;a[x].r=rx;a[x].sz=size;a[x].rt=rt;cnt--; 34     while (a[x].sz*2>(a[x].r-a[x].l+2)){ 35         a[x].rt=merge(l[a[x].rt],r[a[x].rt]);a[x].sz--; 36     } 37 } 38 int main(){ 39     scanf("%d",&n);d[0]=-1; 40     for (int i=1;i<=n;i++) scanf("%d",&b[i]),b[i]-=i; 41     cnt=0;   42     for (int i=1;i<=n;i++){ 43         a[++cnt].l=i;a[cnt].r=i;a[cnt].sz=1;a[cnt].rt=i; 44         while (cnt>1&&b[a[cnt].rt]<b[a[cnt-1].rt]) mer(cnt-1,cnt);     45     } 46     ll ans=0; 47     for (int i=1;i<=cnt;i++)  48         for (int j=a[i].l;j<=a[i].r;j++) ans+=abs(b[a[i].rt]-b[j]); 49     printf("%lld/n",ans); 50     return 0; 51 }