bzoj-3110 K大数查询
题意: 给出一段长为n的区间和m个操作; 1是向[l,r]区间中每个点加入一个权值为k (k<=50000)的数; 2是查询[l,r]区间中的第k大数; 注意1操作是加入而不是加上,就是说此题是在n个盒子里放小球的意思; 题解: 此题自己并yy不动,所以想法都是各位神犇的; /*自己想的是外层线段树维护区间,内层treap维护排名; 然而只能做到单点的修改,区间修改暴力搞势必不行; 打标记也并不会,在节点上挂个标记链会妥妥的被卡飞吧;*/ 所以我们要在外层建立维护权值的线段树,内层建立维护区间的线段树; 这样对于每个修改,对于外层树就都是单点的了; 而内层就用延迟标记,对[l,r]这个区间+1; 当然,如果把整棵树都建出来,空间O(n^2)还带巨大常数瞬间爆炸,所以动态开点; 查询就用treap上求前驱的思想,在外层的线段树上递归找; 对每个节点求出其右半段也就是权值比当前mid大的部分的个数; 与k比较考虑向左子树还是向右子树走,细节考虑一下就好了; 时间复杂度O(mlog^2n),空间复杂度O(n+mlog^2n) HINT: 动态开点的线段树是没有Pushup的,所以在插入时不要忘了在树的路径上加个数; 关于空间复杂度: O(n)的外层线段树没有问题,而对于每次插入,在外层的logn个节点上分别建线段树,所以是O(mlog^2n); 然而事实上,在每次操作中并不只是开了这些节点,有一些多余的节点建立,所以大概要开到三千万的样子(这已经完全脱离分析了吧!); 代码: #include<stdio.h> #include<string.h> #include<algorithm> #define N 50005 #define M 30000000 #define lson l,mid,L[no] #define rson mid+1,r,R[no] using namespace std; int n,m,ans,tot; int root[N<<2]; int L[M],R[M],cov[M],sum[M]; void Pushdown(int no,int len) { if(!L[no]) L[no]=++tot; if(!R[no]) R[no]=++tot; if(cov[no]) { cov[L[no]]+=cov[no]; cov[R[no]]+=cov[no]; sum[L[no]]+=cov[no]*(len-(len>>1)); sum[R[no]]+=cov[no]*(len>>1); cov[no]=0; } } void insert(int l,int r,int &no,int st,int en,int val) { if(st<=l&&r<=en) { cov[no]+=val; sum[no]+=(r-l+1)*val; } else { int mid=(l+r)>>1; Pushdown(no,r-l+1); sum[no]+=(min(r,en)-max(l,st)+1)*val; if(en<=mid) insert(lson,st,en,val); else if(st>mid) insert(rson,val); else insert(lson,val),insert(rson,val); } } void update(int l,int no,int k,int val) { if(!root[no]) root[no]=++tot; insert(1,n,root[no],val); if(l==r) return ; int mid=(l+r)>>1; if(k<=mid) update(l,no<<1,k,val); else update(mid+1,no<<1|1,val); } int getsum(int l,int en) { if(!no) no=++tot; if(st<=l&&r<=en) return sum[no]; int mid=(l+r)>>1; Pushdown(no,r-l+1); if(en<=mid) return getsum(lson,en); else if(st>mid) return getsum(rson,en); else return getsum(lson,en)+getsum(rson,en); } void query(int l,int k) { if(l==r) return ; int mid=(l+r)>>1,rank=getsum(1,root[no<<1|1],en); if(k>=rank) ans=mid,query(l,k-rank); else query(mid+1,k); } int main() { int i,j,op,l,r; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d%d%d",&op,&l,&r,&k); if(op==1) update(1,50000,1,1); else { ans=0; query(1,k-1); printf("%dn",ans); } } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |