BZOJ 3110 [ZJOI2013] K大数查询 【树套树】

tonyfang posted @ 2016年2月27日 16:39 in BZOJ with tags c++ OI , 238 阅读

学了学树套树,大概就是,外层是一棵权值线段树,内层是一棵普通线段树,然后对于第一种询问,在外层找到权值为c的线段树,在内层的a-b上加;对于第二种询问,外层线段树处理后内层再搞即可。

附上代码

 

# include <stdio.h>
# include <algorithm>
using namespace std;

const int M=300010,MM=20000005;
int root[M],ch[MM][2],s[MM],lazy[MM],cnt=0,n,m;

inline void update(int &rt,int l,int r,int ql,int qr) {
	if(rt==0) rt=++cnt;
	if(ql<=l && r<=qr) {
		lazy[rt]++;
		s[rt]+=r-l+1;
		return ;
	}
	int mid=l+r>>1;
	if(ql<=mid) update(ch[rt][0],l,mid,ql,qr);
	if(qr>mid) update(ch[rt][1],mid+1,r,ql,qr);
	s[rt]=s[ch[rt][0]]+s[ch[rt][1]]+lazy[rt]*(r-l+1);
}

inline void Update(int x,int l,int r,int ql,int qr,int qc) {
	update(root[x],1,n,ql,qr);
	if(l==r) return;
	int mid=l+r>>1;
	if(qc<=mid) Update(x*2,l,mid,ql,qr,qc);
	else Update(x*2+1,mid+1,r,ql,qr,qc);
}

inline int query(int rt,int l,int r,int ql,int qr) {
	if(!rt) return 0;
	if(ql<=l && r<=qr) return s[rt];
	int mid=l+r>>1;
	int ret=0;
	if(ql<=mid) ret+=query(ch[rt][0],l,mid,ql,qr);
	if(qr>mid) ret+=query(ch[rt][1],mid+1,r,ql,qr);
	return ret+lazy[rt]*(min(qr,r)-max(ql,l)+1);
}

inline int Query(int x,int l,int r,int ql,int qr,int qc) {
	if(l==r) return l;
	int mid=l+r>>1;
	int ret=query(root[x*2],1,n,ql,qr);
	if (qc<=ret) return Query(x*2,l,mid,ql,qr,qc);
	qc=qc-ret;
	return Query(x*2+1,mid+1,r,ql,qr,qc);
}


int main() {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i) {
		int buf,a,b,c;
		scanf("%d%d%d%d",&buf,&a,&b,&c);
		if(buf==1) c=n-c+1,Update(1,1,n,a,b,c);
		else printf("%d\n",n-Query(1,1,n,a,b,c)+1);
	}
	return 0;
}

 

 

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter