首页 > 代码库 > 【bzoj2809】 Apio2012—dispatching
【bzoj2809】 Apio2012—dispatching
http://www.lydsy.com/JudgeOnline/problem.php?id=2809 (题目链接)
题意：给出一棵树，每个节点有两个权值c，L，分别代表话费和领导力，在树中找到一个点i，并且找到这个点子树中的一些点组成一个集合，使得集合中的所有点的c之和不超过M，且L[i]*集合中元素个数和最大。
solution
听说这道题正解是可并堆，可是并不会做，我们考虑换一种方法。正好最近才学了莫队算法，于是脑洞大开，似乎找到了方法——莫队＋分块，是不是很神。
首先，我们将树上节点按dfs序排序，得到一串序列S，将子树询问转换为在S上的区间询问，总共n棵子树，所以也就只有n个询问，可以承受。
然后我们发现，对于单一节点来说，“使得集合中的所有点的c之和不超过M，且Li*集合中元素个数和最大”可以贪心，也就是尽量选取c小的节点加入集合。于是我们想到了对权值c离散化后进行分块（注意是权值c而不是序列S），对于无修改区间查询用莫队进行转移，权值分块的修改是O(1)的，查询是O(sqrt(n))的，复杂度仍是O(n*sqrt(n))。
接下来就是细节问题。我们先dfs一遍求出dfs序以及区间之后对区间排序（以左端点所在块作为第一关键字，右端点作为第二关键字），之后对树上的节点按照C的大小排序，求出C的值域记录在ma[]数组中，并用p[]数组记录离散化后当前节点的编号。对C的值域建块。
如何插入，删除和询问呢？对于插入和删除，我们用一个数组b[]来记录在C为x的节点有几个在当前询问中，用cnts[]来记录x所在的块中有几个节点在当前询问中，用sumv[]来记录x所在的块中当前的所有C的和。
有了这三个数组询问就很好做了。注意莫队的块与权值分块的区别，别搞混了。
代码：
// bzoj2120#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<vector>#define MOD 1000000007#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;inline LL getint() { LL x=0,f=1;char ch=getchar(); while (ch>‘9‘ || ch<‘0‘) {if (ch==‘-‘) f=-1;ch=getchar();} while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();} return x*f;}const int maxn=100010;struct edge {int next,to;}e[maxn<<2];struct interval {int l,r,id,L;}t[maxn];struct data {int dfn,c,l;}a[maxn];int n,m,M,cnt,mo_block,chunk_block;int L[maxn],head[maxn],cnts[maxn],pos[maxn],sumv[maxn],b[maxn],ma[maxn],p[maxn];void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}void dfs(int u) { t[u].l=a[u].dfn=++cnt; for (int i=head[u];i;i=e[i].next) dfs(e[i].to); t[u].r=cnt;t[u].id=u;t[u].L=a[u].l;}bool ccmp(data a,data b) { return a.c<b.c;}bool poscmp(interval a,interval b) { return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l];}void Mo_build() { mo_block=(int)sqrt(n); for (int i=1;i<=n;i++) pos[i]=(i-1)/mo_block+1;}void chunk_build() { chunk_block=(int)sqrt(cnt); m=(cnt%chunk_block>0) ? cnt/chunk_block+1 : cnt/chunk_block; for (int i=1;i<=cnt;i++) pos[i]=(i-1)/chunk_block+1; for (int i=1;i<=m;i++) L[i]=(i-1)*chunk_block+1;}void update(int x,int val) { b[x]+=val; cnts[pos[x]]+=val; sumv[pos[x]]+=(LL)val*ma[x];}int query() { LL tot=0;int ans=0; for (int i=1;i<=m;i++) { tot+=sumv[i];ans+=cnts[i]; if (tot>M) { tot-=sumv[i];ans-=cnts[i]; for (int j=L[i];;j++) { tot+=(LL)ma[j]*b[j]; ans+=b[j]; if (tot>M) return ans-(int)(tot-M)/ma[j]-((tot-M)%ma[j]!=0); } } } return ans;}int main() { scanf("%d%d",&n,&M); for (int i=1;i<=n;i++) { int x; scanf("%d%d%d",&x,&a[i].c,&a[i].l); insert(x,i); } cnt=0; dfs(e[head[0]].to); Mo_build(); sort(t+1,t+1+n,poscmp); for (int i=1;i<=n;i++) pos[i]=0; sort(a+1,a+1+n,ccmp); cnt=0;ma[p[a[1].dfn]=++cnt]=a[1].c; for (int i=2;i<=n;i++) { if (a[i].c!=a[i-1].c) cnt++; ma[p[a[i].dfn]=cnt]=a[i].c; } LL ans=0; chunk_build(); for (int l=1,r=0,i=1;i<=n;i++) { for (;r<t[i].r;r++) update(p[r+1],1); for (;r>t[i].r;r--) update(p[r],-1); for (;l<t[i].l;l++) update(p[l],-1); for (;l>t[i].l;l--) update(p[l-1],1); ans=max(ans,(LL)query()*t[i].L); } printf("%lld\n",ans); return 0;}
【bzoj2809】 Apio2012—dispatching