建立网站ftp是什么,个人网站备案名字不同,做笑话网站赚钱吗,网址登录链接 https://www.luogu.org/problemnew/show/P1552 思路 忍者数量肯定越多越好 那就从下到上的合并它的孩子 左偏树的话 顺便维护一个tot#xff0c;大头堆#xff0c;如果tot大于了m#xff0c;把大的删掉 如果左偏树忘干净了或者没学的话 线段树合并也是个不错的选择 直接… 链接 https://www.luogu.org/problemnew/show/P1552 思路 忍者数量肯定越多越好 那就从下到上的合并它的孩子 左偏树的话 顺便维护一个tot大头堆如果tot大于了m把大的删掉 如果左偏树忘干净了或者没学的话 线段树合并也是个不错的选择 直接权值线段树合并就好内存30倍会炸也许是我没离散化的缘故吧 查询在线段树上面二分 左偏树代码 #include bits/stdc.h
#define FOR(i,a,b) for(int ia;ib;i)
#define ll long long
using namespace std;
const int maxn100047;
inline int read() {int x0,f1;char sgetchar();for(;s9||s0;sgetchar()) if(s-) f-1;for(;s0s9;sgetchar()) xx*10s-0;return x*f;
}
struct edge {int v,nxt;
}e[maxn];
int head[maxn],tot;
void add_edge(int u,int v) {e[tot].vv;e[tot].nxthead[u];head[u]tot;
}
int n,m,mone;
ll sum[maxn],ans;
int size[maxn];
int ch[maxn][2],dis[maxn],val[maxn],xs[maxn];
int work(int a,int b) {if(!a||!b) return ab;if(val[a]val[b]) swap(a,b);ch[a][1]work(ch[a][1],b);if(dis[ch[a][0]]dis[ch[a][1]]) swap(ch[a][0],ch[a][1]);dis[a]dis[ch[a][1]]1;return a;
}
int merge(int x,int y) {int tmpwork(x,y);yx^y^tmp,xtmp;sum[x]sum[y];size[x]size[y];return tmp;
}
int delet(int x) {int tmpwork(ch[x][0],ch[x][1]);size[tmp]size[x]-1;sum[tmp]sum[x]-val[x];return tmp;
}
int dfs(int u) {int rtu;for(int ihead[u];i;ie[i].nxt) {int ve[i].v;int tmpdfs(v);rtmerge(rt,tmp);}while(sum[rt]mone) rtdelet(rt);ansmax(ans,xs[u]*(ll)size[rt]);return rt;
}
int main() {nread(),moneread();int root;FOR(i,1,n) {int xread();val[i]read();xs[i]read();sum[i]val[i];size[i]1;if(x) add_edge(x,i);else rooti;}int wuyongdfs(root);coutans\n;return 0;
} 线段树合并代码 #include iostream
#include cstdio
#include algorithm
#include vector
#include utility
#define ll long long
using namespace std;
const int N1e57;
int read() {int x0,f1;char sgetchar();for(;s9||s0;sgetchar()) if(s-) f-1;for(;s0s9;sgetchar()) xx*10s-0;return x*f;
}
int n,m,money[N],leader[N],rt[N];
vectorint G[N];
struct node {int l,r,siz;ll tot;
}e[N*30];
void pushup(int rt) {e[rt].size[e[rt].l].size[e[rt].r].siz;e[rt].tote[e[rt].l].tote[e[rt].r].tot;
}
int cnt;
void insert(int l,int r,int L,int rt) {rtcnt;if(lr) {e[rt].siz;e[rt].totl;return;}int mid(lr)1;if(Lmid) insert(l,mid,L,e[rt].l);else insert(mid1,r,L,e[rt].r);pushup(rt);
}
int merge(int l,int r,int x,int y) {if(!x||!y) return xy;if(lr) {e[x].size[y].siz;e[x].tote[y].tot;return x;}int mid(lr)1;e[x].lmerge(l,mid,e[x].l,e[y].l);e[x].rmerge(mid1,r,e[x].r,e[y].r);pushup(x);return x;
}
int query(int l,int r,int k,int rt) {if(lr) return ke[rt].tot ? e[rt].siz : 0;int mid(lr)1;if(e[e[rt].l].totk) return query(l,mid,k,e[rt].l);else return e[e[rt].l].sizquery(mid1,r,k-e[e[rt].l].tot,e[rt].r);
}
ll ans;
void dfs(int u) {insert(1,1000000000,money[u],rt[u]);for(vectorint::iterator itG[u].begin();it!G[u].end();it) {dfs(*it);rt[u]merge(1,1000000000,rt[u],rt[*it]);}ansmax(ans,(ll)leader[u]*query(1,1000000000,m,rt[u]));
}
int main() {nread(),mread();for(int i1;in;i) {int xread();money[i]read();leader[i]read();G[x].push_back(i);}dfs(1);printf(%lld,ans);return 0;
} 转载于:https://www.cnblogs.com/dsrdsr/p/10359546.html
