目录
BZOJ2809 dispatching题解ｃｏｄｅ
BZOJ2809 dispatching
题目传送门
题解
这道题目的题解很多，但大多都是用左偏树/主席书做的。这里再介绍一个莫队的做法。首先这题的题目就是在树上选定一个点，然后在这个点的子树中选出一些点，使这些点的\(\sum c[i]\)不超过\(M\)，求\(Li*\)选中点的个数最大。对于选择的部分，我们可以贪心的选择\(c\)比较小的那部分，使得元素个数最多。然后如果我们暴力枚举每个区间的话，那么时限肯定是不够了，所以我们可以处理出这棵树的\(DFS\)序，将枚举的每一个区间当做一次询问，然后套用莫队进行转移就行了，是一个比较简单的无修改莫队，复杂度为\(O(n\sqrt{n})\)。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int maxn=100010;
struct edge {
int nxt,to;
}E[maxn<<2];
int blo[maxn];
struct query {
int l,r,L;
bool operator < (const query &rhs) const {
return blo[l]==blo[rhs.l]?r<rhs.r:blo[l]<blo[rhs.l];
}
}q[maxn];
struct ninja {
int dfn,cost,l;
bool operator < (const ninja &rhs) const {
return cost<rhs.cost;
}
}a[maxn];
int n,cntblock,m,tot,block,cblock,rt,dfnclck;
int L[maxn],head[maxn],cnt[maxn],sum[maxn],b[maxn],val[maxn],p[maxn];
/*==================Define Area================*/
void addedge(int u,int v) {
E[++tot].to=v;E[tot].nxt=head[u];head[u]=tot;
}
void dfs(int u) {
q[u].l=a[u].dfn=++dfnclck;
for (int i=head[u];~i;i=E[i].nxt) dfs(E[i].to);
q[u].r=dfnclck;q[u].L=a[u].l;
}
void Buildblock() {
cblock=sqrt(dfnclck);
cntblock=(dfnclck+1)/cblock;
for(int i=1;i<=dfnclck;i++) blo[i]=(i-1)/cblock+1;
for(int i=1;i<=cntblock;i++) L[i]=(i-1)*cblock+1;
}
void Modify(int x,int v) {
b[x]+=v;
cnt[blo[x]]+=v;
sum[blo[x]]+=1ll*v*val[x];
}
void Getc() {
dfnclck=0;val[p[a[1].dfn]=++dfnclck]=a[1].cost;
for (int i=2;i<=n;i++) {
if(a[i].cost!=a[i-1].cost) dfnclck++;
val[p[a[i].dfn]=dfnclck]=a[i].cost;
}
}
ll Query() {
ll tot=0;
ll ans=0;
for(int i=1;i<=cntblock;i++) {
tot+=sum[i];ans+=cnt[i];
if (tot>m) {
tot-=sum[i];ans-=cnt[i];
int now=L[i];
while(1) {
tot+=1ll*val[now]*b[now];
ans+=b[now];
if(tot>m) return ans-(tot-m)/val[now]-((tot-m)%val[now]!=0);
now++;
}
}
}
return ans;
}
int main() {
memset(head,-1,sizeof head);
read(n);read(m);
for (int i=1;i<=n;i++) {
int fa;
read(fa);read(a[i].cost);read(a[i].l);
if(!fa) rt=i;
addedge(fa,i);
}
dfnclck=0;
dfs(rt);
block=sqrt(n);
for (int i=1;i<=n;i++) blo[i]=(i-1)/block+1;
sort(q+1,q+1+n);
memset(blo,0,sizeof blo);
sort(a+1,a+1+n);
Getc();
Buildblock();
ll ans=0;
int l=1,r=0;
for (int i=1;i<=n;i++) {
while(r<q[i].r) Modify(p[r+1],1),r++;
while(r>q[i].r) Modify(p[r],-1),r--;
while(l<q[i].l) Modify(p[l],-1),l++;
while(l>q[i].l) Modify(p[l-1],1),l--;
ans=max(ans,1ll*Query()*q[i].L);
}
printf("%lld\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9434962.html
相关资源：JAVA上百实例源码以及开源项目
