首页 > 代码库 > 主席树复习
主席树复习
T1 [CQOI2015]任务查询系统
n个任务，每个有运行的时间段和优先级，询问某一时刻，优先级最小的个任务的优先级之和
初做： 2017.2.4 http://www.cnblogs.com/TheRoadToTheGold/p/6366165.html
好像是做了一晚上来
现在：2017.3.27 14:17——15:56
用了接近2个小时做了一道以前做过的题，还是弱啊~~~~(>_<)~~~~
difference：
主席树维护的东西不同，以前直接存储优先级之和，现在存储的是任务个数，其实一个样。。
再就是预处理方式不同
离散化优先级，以时间为下标，以优先级为区间，建立主席树
对主席树理解不透彻，开始离散化优先级，又以优先级为下标，建主席树
离散化了某个值后，它就成了线段树中节点的可控区间范围
个人理解：
主席树中节点有3类属性，下标（自己的、孩子的）、可控区间范围、要维护的值
下标一般存在root[]、lc[]、rc[]中，要维护的值用各种数组存储
在线段树中，可控区间范围是作为节点信息储存的，但主席树一般不存储
在添加或查询时，加上2个参数，表示当前节点的可控区间范围，在递归过程中，范围与当前节点保持一致
代码模板化，所以导致在写的时候
添加节点的pre上来就写root[i-1]，这个题是以自身为参照
查询的时候上来就root[i-1],这里不需要参照
一大问题：
这里要保持时间的连续性，若一个任务在[l,r]时间执行
代码中是l位置+1，r位置-1，
所以在添加操作之前，先令root[i]=root[i-1]
目的有二：
1、若某一个时刻在输入中没有出现，这样可以保持时间的连续性
2、添加节点是以自身为参照
开始40分RE，原因：一个任务往主席树中加入2个点，所以数组应*40
#include<cstdio>#include<algorithm>#define N 200001using namespace std;struct node2{ int time,p,w;}g[N*2];int hash[N];int n,m,tot,id;int root[N*20],lc[N*20],rc[N*20],cnt[N*20];long long ans=1;bool cmp(node2 k,node2 q){ return k.time<q.time;}void discrete(){ sort(hash+1,hash+m+1); tot=unique(hash+1,hash+m+1)-hash-1; for(int i=1;i<=2*m;i++) g[i].p=lower_bound(hash+1,hash+tot+1,g[i].p)-hash;}void insert(int pre,int &now,int l,int r,int pos,int val){ now=++id; cnt[now]=cnt[pre]+val; if(l==r) return; int mid=l+r>>1; if(pos<=mid) { rc[now]=rc[pre]; insert(lc[pre],lc[now],l,mid,pos,val); } else { lc[now]=lc[pre]; insert(rc[pre],rc[now],mid+1,r,pos,val); }}void query(int now,int l,int r,int k){ if(l==r) { ans+=1ll*min(cnt[now],k)*hash[l]; return; } int mid=l+r>>1,tmp=cnt[lc[now]]; query(lc[now],l,mid,k); if(k>tmp) query(rc[now],mid+1,r,k-tmp);}int main(){ /*freopen("cqoi15_query.in","r",stdin); freopen("cqoi15_query.out","w",stdout);*/ scanf("%d%d",&m,&n); int x,k,a,b,c; for(int i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); g[i*2-1].time=a; g[i*2-1].p=c; g[i*2-1].w=1; g[i*2].time=b+1; g[i*2].p=c; g[i*2].w=-1; hash[i]=c; } sort(g+1,g+2*m+1,cmp); discrete(); int last=0; for(int i=1;i<=2*m;i++) { for(int j=last+1;j<=g[i].time;j++) { root[j]=root[j-1]; } insert(root[g[i].time],root[g[i].time],1,tot,g[i].p,g[i].w); last=g[i].time; } for(int i=1;i<=n;i++) { scanf("%d%d%d%d",&x,&a,&b,&c); k=(ans*a+b)%c+1;ans=0; query(root[x],1,tot,k); printf("%lld\n",ans); }}
T2 APIO2012 dispatching
每个点有价值、花费，所有的点构成一棵树，给出资金限制
num[i]=在以i为根的子树中，在资金限制内最多能选的点的个数
最大化 s=i的价值*num[i]
初做：2017.2.5 http://www.cnblogs.com/TheRoadToTheGold/p/6368387.html
现在：2017.3.27
16:31做到19:32 中间吃了个饭听了个听力
主席树+dfs序
离散化费用，以费用为区间，以点的dfs序为下标建立主席树
刚开始想的是枚举每个点，然后二分最多能选的点
其实不用二分
用主席树维护到这个点的费用和、点数
然后求在满足费用和<=资金限制的情况下，最多选多少点
很巧妙的是dfs序的应用，但在这儿不是我关注的重点
由于点又有了dfs序，所以一开始就把点的原编号与dfs序搞混了
最大的错误：
查询时，不思考就int mid=l+r>>1，tmp。。。。。。
这里tmp要用long long，卡了1个多小时
模板背熟了是好，注意应用
#include<cstdio>#include<algorithm>#define N 100001using namespace std;int n,m,se,cnt;int front[N],nextt[N],to[N],tot_ninja;int money[N],hashh[N],tot,lead[N];int in[N],out[N],id[N],s;//id[i]=j :编号为j的是i号忍者 int root[N],lc[N*20],rc[N*20],num[N*20];long long sum[N*20];void add(int u,int v){ nextt[++tot_ninja]=front[u]; front[u]=tot_ninja; to[tot_ninja]=v;}void dfs(int now){ for(int i=front[now];i;i=nextt[i]) { id[++s]=to[i]; in[to[i]]=s; dfs(to[i]); } out[now]=s;}void insert(int pre,int &now,int l,int r,int pos){ now=++se; num[now]=num[pre]+1; sum[now]=sum[pre]+hashh[pos]; if(l==r) return; int mid=l+r>>1; if(pos<=mid) { rc[now]=rc[pre]; insert(lc[pre],lc[now],l,mid,pos); } else { lc[now]=lc[pre]; insert(rc[pre],rc[now],mid+1,r,pos); }}void discrete(){ sort(hashh+1,hashh+n+1); tot=unique(hashh+1,hashh+n+1)-hashh-1; for(int i=1;i<=n;i++) money[i]=lower_bound(hashh+1,hashh+tot+1,money[i])-hashh;}void query(int pre,int now,int l,int r,int limit){ if(l==r) { cnt+=min(limit/hashh[l],num[now]-num[pre]); return; } int mid=l+r>>1; long long tmp=sum[lc[now]]-sum[lc[pre]]; if(limit<=tmp) query(lc[pre],lc[now],l,mid,limit); else { cnt+=num[lc[now]]-num[lc[pre]]; query(rc[pre],rc[now],mid+1,r,limit-tmp); }}int main(){ freopen("dispatching.in","r",stdin); freopen("dispatching.out","w",stdout); scanf("%d%d",&n,&m); int x; for(int i=1;i<=n;i++) { scanf("%d%d%d",&x,&money[i],&lead[i]); hashh[i]=money[i]; add(x,i); } discrete(); dfs(0); for(int i=1;i<=n;i++) insert(root[i-1],root[i],1,tot,money[id[i]]); long long ans=0; for(int i=1;i<=n;i++) { cnt=0; query(root[in[i]-1],root[out[i]],1,tot,m); ans=max(ans,(long long)lead[i]*cnt); } printf("%lld",ans);}
主席树复习