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

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

学了学树套树,大概就是,外层是一棵权值线段树,内层是一棵普通线段树,然后对于第一种询问,在外层找到权值为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;
}

 

 

 

question-paper.com 说:
2023年4月22日 22:45

Board Questiion Paper 2023 Aspirants who had Registered for the Board Exam can Download the Previous Paper When Board Announces the Dates to Download the Questiion Paper. question-paper.com Board Sample Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Questiion Paper.


登录 *


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