VEXOBEN
Vexoben
Jul 2, 2018
It takes 5 minutes to read this article.

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=3110

题意

有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c

如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。

N,M<=50000,N,M<=50000

a<=b<=N

1操作中abs(c)<=N

2操作中c<=Maxlongint

题解

一个直观的想法是线段树套线段树,外层维护区间,内层维护权值。但这时我们会发现外层线段树修改时涉及到懒标记处理,在树套树时很难处理。

那么我们把他反过来。外层维护权值,内层维护区间。这样每次修改时对外层线段树来说就是单点修改,暴力修改涉及到的全部O(logn)个节点即可。内层就是一个区间加。

询问时,首先二分一个答案mid,直接查询大于等于mid的数的个数即可。

内层线段树尝试打了标记永久化。

#include<bits/stdc++.h>
#define uint unsigned int
using namespace std;
const int N=3e5+10;

int ql,qr,c,n,m;

namespace T2 {
	int tot=0,ch[N*40][2];
	uint tree[N*40],tag[N*40];
	
	void Updata(int &x,int l,int r) {
		if (!x) x=++tot;
		tree[x]+=min(qr,r)-max(ql,l)+1;
		if (ql<=l&&r<=qr) {
			tag[x]++; return;
		}
		int mid=(l+r)>>1;
		if (mid>=ql) Updata(ch[x][0],l,mid);
		if (mid<qr) Updata(ch[x][1],mid+1,r);
	}

	uint Query(int x,int l,int r,uint add) {
		if (ql<=l&&r<=qr) return tree[x]+add*(r-l+1);
		uint ans=0,mid=(l+r)>>1;
		if (mid>=ql) ans+=Query(ch[x][0],l,mid,add+tag[x]);
		if (mid<qr) ans+=Query(ch[x][1],mid+1,r,add+tag[x]);
		return ans;
	}
}

namespace T1 {
	int rt[N];
	
	void Updata(uint x,int l,int r,int pos) {
		T2::Updata(rt[x],1,n);
		if (l==r) return;
		int mid=(l+r)>>1;
		if (mid>=pos) Updata(x<<1,l,mid,pos);
		else Updata(x<<1|1,mid+1,r,pos);
	}

	uint Query(int x,int l,int r,int ql,int qr) {
		if (ql<=l&&r<=qr) return T2::Query(rt[x],1,n,0);
		uint mid=(l+r)>>1,ans=0;
		if (mid>=ql) ans+=Query(x<<1,l,mid,ql,qr);
		if (mid<qr) ans+=Query(x<<1|1,mid+1,r,ql,qr);
		return ans;
	}
}

int main() {
	scanf("%d%d",&n,&m);
	while (m--) {
		int t; scanf("%d%d%d%d",&t,&ql,&qr,&c);
		if (t==1) {
			T1::Updata(1,1,n*2,c+n);
		}
		else if (t==2) {
			int l=0,r=2*n;
			while (l<r) {
				int mid=(l+r+1)>>1;
				uint num=T1::Query(1,1,2*n,mid,2*n);
				if (num<c) r=mid-1;
				else l=mid;
			}
			printf("%d\n",l-n);
		}
	}
	return 0;
}