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

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




# 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) {
		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);

inline void Update(int x,int l,int r,int ql,int qr,int qc) {
	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);
	return Query(x*2+1,mid+1,r,ql,qr,qc);

int main() {
	for (int i=1;i<=m;++i) {
		int 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;
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. 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