首页 > 代码库 > BZOJ3110 ZJOI2013 K大数查询 线段树套线段树
BZOJ3110 ZJOI2013 K大数查询 线段树套线段树
题意：给定一个数列，维护：1、在a和b之间插入c 2、询问[a,b]中的第c大
题解：
权值线段树套区间线段树
外层的权值线段树中每个节点如果维护[L,R]这个区间，那么该节点所对应的线段树维护的就是[L,R]这些数在每个区间里出现了几次，也就是说如果外层线段树的某个节点维护[L,R]，其所对应的内层线段树中某个节点[l,r]维护的值就是[L,R]这些数在[l,r]这个区间中出现的次数。
最后吐槽一下动态内存+指针版线段树MLE……尼玛我写指针版完全习惯了根本就不会写数组版了QAQ，自己拿数据一个一个对拍了一下程序本身是没问题的。
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int MAXN=50000+2;typedef struct NODE1{ int c,l,r,add; NODE1 *lchild,*rchild; NODE1(){} NODE1(int _l,int _r):l(_l),r(_r),c(0),add(0),lchild(0),rchild(0){}} *TREE1;typedef struct NODE2{ int l,r; TREE1 root; NODE2 *lchild,*rchild; NODE2(){} NODE2(int _l,int _r):l(_l),r(_r),root(0){}} *TREE2;TREE2 root;int N,M;void Build2(TREE2 &x,int l,int r){ x=new NODE2(l,r); if(l==r) return; int m=(l+r)>>1; Build2(x->lchild,l,m),Build2(x->rchild,m+1,r);}void Pushup(TREE1 &x){ x->c=0; if(x->lchild) x->c+=x->lchild->c; if(x->rchild) x->c+=x->rchild->c;}void Pushdown(TREE1 &x,int m){ if(x->add && x->l!=x->r){ if(!x->lchild) x->lchild=new NODE1(x->l,(x->l+x->r)>>1); x->lchild->c+=x->add*(m-(m>>1)),x->lchild->add+=x->add; if(!x->rchild) x->rchild=new NODE1(((x->l+x->r)>>1)+1,x->r); x->rchild->c+=x->add*(m>>1),x->rchild->add+=x->add; x->add=0; }}void Insert1(TREE1 &x,int l,int r,int L,int R){ if(!x) x=new NODE1(L,R); if(x->l>=l && x->r<=r){ x->c+=x->r-x->l+1,x->add++; return; } Pushdown(x,x->r-x->l+1); int m=(L+R)>>1; if(l<=m) Insert1(x->lchild,l,r,L,m); if(r>m) Insert1(x->rchild,l,r,m+1,R); Pushup(x);}void Insert2(TREE2 &x,int l,int r,int v){ Insert1(x->root,l,r,1,N); if(x->l==x->r) return; int m=(x->l+x->r)>>1; if(v<=m) Insert2(x->lchild,l,r,v); else Insert2(x->rchild,l,r,v);}int Query1(TREE1 &x,int l,int r){ if(!x) return 0; if(x->l>=l && x->r<=r) return x->c; Pushdown(x,x->r-x->l+1); int m=(x->l+x->r)>>1,ret=0; if(l<=m) ret+=Query1(x->lchild,l,r); if(r>m) ret+=Query1(x->rchild,l,r); return ret;}int Query2(TREE2 &x,int l,int r,int v){ if(x->l==x->r) return x->l; int m=Query1(x->rchild->root,l,r); if(v<=m) return Query2(x->rchild,l,r,v); else return Query2(x->lchild,l,r,v-m);}int main(){ cin >> N >> M; Build2(root,1,N); for(int i=1,t,a,b,c;i<=M;i++){ cin >> t >> a >> b >> c; if(t==1) Insert2(root,a,b,c); if(t==2) cout << Query2(root,a,b,c) << endl; } return 0;}
BZOJ3110 ZJOI2013 K大数查询 线段树套线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。