题目
2809: [Apio2012]dispatching
题解
最近开始了刷水题计划。
这题第一个想法是treap启发式合并。
第二个是左偏树（不会写）
第三个是线段树合并。
第四个是dfs序上主席树。
可能，，这题跟天天爱跑步很像啊。
想找个线段树合并的。但是没有人写。我就写了。
写完发现。一共5s,excuse me??我怕是算了假的复杂度噢。
不知道为啥。。而且节点合并没有return 合并后的节点debug了0.5h
我发表了才发现我并没有写题解。
就是要你求每个子树内，找一个最大的k，使得子树权值前k小的和小于给定的值。然后一万种数据结构可以做。
代码
//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;const int maxn=200000+10;
const int maxm=200000+10;
typedef long long ll;int n,m,tk,c[maxn],led[maxn],t[maxn];struct Edge{
int u,v;Edge(int u=0,int v=0):u(u),v(v){}}e[maxm];
int first[maxn],next[maxm],ecnt;
inline void add_edge(int u,int v){next[ecnt]=first[u];first[u]=ecnt;e[ecnt++]=Edge(u,v);
}inline void init_data()
{cin>>n>>m;memset(first,-1,sizeof first);for(int i=1,u;i<=n;++i){scanf("%d%d%d",&u,c+i,led+i);t[i]=c[i];if(u) add_edge(u,i);}sort(t+1,t+n+1);tk=unique(t+1,t+n+1)-t-1;for(int i=1;i<=n;++i) c[i]=lower_bound(t+1,t+tk+1,c[i])-t;
}struct Node{int sz;ll sum;Node *lc,*rc;Node(){sz=sum=0;lc=rc=NULL;}inline void up(){sz=sum=0;if(lc) sz+=lc->sz,sum+=lc->sum;if(rc) sz+=rc->sz,sum+=rc->sum;}
};#define mid ((l+r)>>1)
Node* merge(Node *a,Node *b,int l,int r)
{if(!a) return b;if(!b) return a;Node *ret=new Node();if(l==r) {ret->sz=a->sz+b->sz;ret->sum=a->sum+b->sum;return ret;}ret->lc=merge(a->lc,b->lc,l,mid);ret->rc=merge(a->rc,b->rc,mid+1,r);ret->up();return ret;//就是这里
}void updata(Node* &p,int l,int r,int pos,int v1,ll v2)
{if(!p) p=new Node();if(l==r){p->sz+=v1;p->sum+=v2;return ;}if(pos<=mid) updata(p->lc,l,mid,pos,v1,v2);else updata(p->rc,mid+1,r,pos,v1,v2); p->up();
}int query(Node* p,int l,int r,ll k)
{if(!p) return 0;if(l==r) {if(!p->sz) return 0;return k/(p->sum/p->sz);}if(p->lc&&p->lc->sum < k) return p->lc->sz+query(p->rc,mid+1,r,k-p->lc->sum);else return query(p->lc,l,mid,k);
}ll ans=0;Node *tmp;
Node* dfs(int u)
{Node *rt=NULL;for(int i=first[u];i!=-1;i=next[i]) {tmp=dfs(e[i].v);rt=merge(rt,tmp,1,tk);}updata(rt,1,tk,c[u],1,t[c[u]]);if(m >= rt->sum) ans=max(ans,1ll*led[u]*rt->sz);else ans=max(ans,1ll*led[u]*query(rt,1,tk,m));return rt;
}int main()
{init_data();dfs(1);cout<<ans;return 0;
}
?