来自FallDream的博客，未经允许，请勿转载，谢谢。
---------------------------------------------------
A.dispatching 派遣
上次hzwer出了这道题所以做过了，搬一下以前的博文。
给定一棵n个点的树和一个费用m，每个点有一个忍者，派遣它的费用是ci，它的领导力是li。你要选择一个点作为领导，并且在它的子树中(包括它)选出尽可能多的点，满足费用不超过m且选出的点的数量*领导的领导力最大。n<=100000 m,c,l<=10^9
题解：这道题很多做法吧..首先费用少的肯定先选，我们每次肯定是从费用小的开始选，所以题目可以转换为求所有点的子树中最多能选几个点。
做法1：平衡树/优先队列+启发式合并
把费用装进一个平衡树/优先队列里面，然后启发式合并，合并次数是nlogn，总复杂度nlog^2n
我的做法：树剖那样子标号，满足子树的dfs序连续，然后主席树，复杂度是nlogn
#include<iostream> #include<cstdio> #include<queue> #define MN 100000 #define MM 5000000 #define INF 2000000000 #define ll long long using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int n,dfn=0,cnt=0,mx[MN+5],size[MN+5],nl[MN+5],nr[MN+5],head[MN+5],id[MN+5],rt[MN+5]; ll c[MN+5],l[MN+5],ans=0,m; struct edge{ int to,next; }e[MN+5]; struct TREE{ int l,r,size;ll x; }T[MM+5]; void ins(int f,int t) { e[++cnt]=(edge){t,head[f]};head[f]=cnt; } void dfs1(int x) { size[x]=1;mx[x]=0;int maxn=0; for(int i=head[x];i;i=e[i].next) { dfs1(e[i].to); size[x]+=size[e[i].to]; if(size[e[i].to]>maxn){maxn=size[e[i].to];mx[x]=e[i].to;} } } void dfs2(int x) { nl[x]=++dfn;id[dfn]=x; if(mx[x]) dfs2(mx[x]); for(int i=head[x];i;i=e[i].next) if(e[i].to!=mx[x]) dfs2(e[i].to); nr[x]=dfn; } void ins(int x,int nx,ll c) { T[nx].size=T[x].size+1;T[nx].x=T[x].x+c; ll l=1,r=INF,mid; while(l<r) { mid=l+r>>1; if(c<=mid) { T[nx].r=T[x].r;T[nx].l=++cnt; r=mid;nx=T[nx].l;x=T[x].l; } else { T[nx].l=T[x].l;T[nx].r=++cnt; l=mid+1;nx=T[nx].r;x=T[x].r; } T[nx].size=T[x].size+1;T[nx].x=T[x].x+c; } } int query(int x,int nx,ll cc) { ll l=1,r=INF,mid,num=0; while(l<r) { mid=l+r>>1; if(T[T[nx].l].x-T[T[x].l].x<=cc) { cc-=T[T[nx].l].x-T[T[x].l].x; num+=T[T[nx].l].size-T[T[x].l].size; x=T[x].r;nx=T[nx].r;l=mid+1; } else { x=T[x].l;nx=T[nx].l; r=mid; } } if(T[nx].size-T[x].size>0) { int x=cc/((T[nx].x-T[x].x)/(T[nx].size-T[x].size)); num+=x; } return num; } main() { n=read();m=read(); for(int i=1;i<=n;i++) { int fa=read();c[i]=read();l[i]=read(); if(fa) ins(fa,i); } dfs1(1);dfs2(1);cnt=0; for(int i=1;i<=n;i++) ins(rt[i-1],rt[i]=++cnt,c[id[i]]); for(int i=1;i<=n;i++) ans=max(ans,l[i]*1LL*query(rt[nl[i]-1],rt[nr[i]],m)); cout<<ans; return 0; }
B.guard守卫
有n个草丛(#滑稽）,里面有K个盖伦忍者，有m个条信息，表示一段区间内有没有盖伦忍者，你要求出一定有盖伦忍者的草丛。 $n,m,kleqslant 10^{5}$
一开始我看到这道题就写了一个线段树+大判断，挂了3个点，想了好久才发现忍者数量可能会超过的情况没判。
讲讲正解：先删掉没用的，然后剩下的如果是K个，就直接输出，否则我们重新标号之后，排序，删除无用区间，这样满足信息的左右坐标都递增。很显然，对每段区间选择放在最右边的点是最优的。用F[i]表示前i个区间放在最右的节点至少放几个，g[i]表示后... 然后对每个区间，如果它长度为一，直接输出，否则我们认为放在第二右边是次优的，二分出不能覆盖第二右的节点的区间范围，假设是1..a 和b..m，那么判断f[a]+g[b]+1如果大于K，说明这个最右的节点必须放，否则会超过K个。
#include<iostream> #include<cstdio> #include<algorithm> #define MN 100000 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } struct TREE{int l,r,val,x;}T[MN*4+5]; struct ques{int l,r; bool operator <(const ques&y)const{return l==y.l?r>y.r:l<y.l;} }q[MN+5],s[MN+5]; int n,K,m,cnt=0,f[MN+5],g[MN+5],nl[MN+5],nr[MN+5],cn=0,id[MN+5]; void build(int x,int l,int r) { if((T[x].l=l)==(T[x].r=r)) {T[x].x=1;return;} int mid=l+r>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); T[x].x=T[x<<1].x+T[x<<1|1].x; } void modify(int x,int l,int r) { if(T[x].val)return; if(T[x].l==l&&T[x].r==r) { T[x].val=1;T[x].x=0; return; } int mid=T[x].l+T[x].r>>1; if(r<=mid) modify(x<<1,l,r); else if(l>mid) modify(x<<1|1,l,r); else {modify(x<<1,l,mid);modify(x<<1|1,mid+1,r);} T[x].x=T[x<<1].x+T[x<<1|1].x; } int query(int x,int k) { if(T[x].val)return 0; if(T[x].l==T[x].r)return T[x].x; int mid=T[x].l+T[x].r>>1; return k<=mid?query(x<<1,k):query(x<<1|1,k); } int get(int x,int l,int r) { int ans=0; for(int mid=l+r>>1;l<=r;mid=l+r>>1) if(s[mid].r<x) ans=mid,l=mid+1; else r=mid-1; return f[ans]; } int get2(int x,int l,int r) { int ans=0; for(int mid=l+r>>1;l<=r;mid=l+r>>1) if(s[mid].l>x) ans=mid,r=mid-1; else l=mid+1; return g[ans]; } int main() { n=read();K=read();m=read(); build(1,1,n); for(int i=1;i<=m;i++) { int l=read(),r=read(),x=read(); if(!x) modify(1,l,r); else q[++cnt]=(ques){l,r}; } if(T[1].x==K) { for(int i=1;i<=n;i++) if(query(1,i)==1) printf("%d ",i); return 0; } for(int i=1;i<=n;i++) if(query(1,i)==1) nl[i]=++cn,id[cn]=i; for(int i=n;i;i--) nr[i]=(nl[i]?nl[i]:nr[i+1]); for(int i=1;i<=n;i++) nl[i]=(nl[i]?nl[i]:nl[i-1]); for(int i=1;i<=cnt;i++) q[i].l=nr[q[i].l],q[i].r=nl[q[i].r]; sort(q+1,q+cnt+1);int j=0; for(int i=1;i<=cnt;i++) { while(j&&q[i].r<=s[j].r)--j; s[++j]=q[i]; } for(int i=1,mx=0;i<=j;i++) if(s[i].l>mx) {mx=s[i].r;f[i]=f[i-1]+1;} else f[i]=f[i-1]; for(int k=j,mn=n+1;k;k--) if(s[k].r<mn) {mn=s[k].l;g[k]=g[k+1]+1;} else g[k]=g[k+1]; bool flag=0; for(int i=1;i<=j;i++) { if(f[i]!=f[i-1]+1) continue; if(s[i].l==s[i].r) {flag=1;printf("%d ",id[s[i].l]);continue;} int lt=get(s[i].r-1,1,i-1),rt=get2(s[i].r-1,i+1,j); if(lt+rt+1>K) printf("%d ",id[s[i].r]),flag=1; } if(!flag) puts("-1"); return 0; }
C.苦无
大概就是乱排序每种情况考虑一下，然后堆搞一搞，最后矩形面积并。
傻逼大码农，本来打算码的，现在代码已经被我删了.