cf gym102901K The Stream of Corning 2 离线+bit

题目链接
大意：给你一系列操作
1： $l,val,r$l,val,r，添加一个 $val存在于[l,r]$val存在于[l,r]区间。
2. $index,k$index,k问你存在于 $index$index这个位置的第 $k$k小数，若不存在输出-1；
思路：我们可以将1操作的区间两个端点拆开和2操作的时间放在一个数组中进行排序（小的优先）。用opt标记这是左端点还是右端点还是询问。
然后我们将所有的值进行离散化，（1操作中的val,2操作中的index）。
然后遍历已经排好序的所有操作。若当前是左端点，则在树状数组中加入这个val。若是右端点则删除。若是询问操作的话，先特判是否存在，存在的话则二分查找位置记录答案。
细节见代码

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int t,n;
struct uzi
{
	int opt,x,val,id;
	bool operator <(const uzi & t)const{
		if(x==t.x)return id<t.id;
		return x<t.x;
	}
}p[N];
int dx=0,dy=0,dz=0;
int c[N],a[N],ans[N],len;
int add(int now,int x){
	for(int i=now;i<=len;i+=(i&(-i)))c[i]+=x;
}
int que(int now){
	int sum=0;
	for(int i=now;i;i-=(i&(-i)))sum+=c[i];
	return sum;
}
int get(int sum){
	int l=1,r=len,ans=-1;
	while(l<=r){
		int mid=l+r>>1;
		if(que(mid)>=sum)ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
int now;
int main(){
	for(scanf("%d",&t);t;t--){
		scanf("%d",&n);
		dx=dy=dz=0;
		memset(c,0,sizeof c);
		memset(ans,0,sizeof ans);
		for(int i=1;i<=n;i++){
			int opt,x,y,z;
			scanf("%d%d%d",&opt,&x,&y);
			a[++dz]=y;
			if(opt==1){
				scanf("%d",&z);
				p[++dx]={1,x,y,i};
				p[++dx]={-1,z+1,y,i};
			}else p[++dx]={2,x,y,i};
		}
		sort(a+1,a+1+dz);
		len=unique(a+1,a+1+dz)-a-1;
		for(int i=1;i<=dx;i++)p[i].val=lower_bound(a+1,a+1+len,p[i].val)-a;
		sort(p+1,p+1+dx);
		for(int i=1;i<=dx;i++){
			if(p[i].opt!=2){
				add(p[i].val,p[i].opt);
			}else{
				if(que(len)<p[i].val)ans[i]=-1;
				else ans[i]=get(p[i].val);
			}
		}
		printf("Case %d:\n",++now );
		for(int i=1;i<=dx;i++){
			if(!ans[i])continue;
			if(ans[i]==-1)printf("-1\n");
			else printf("%d\n",a[ans[i]] );
		}
	}
	return 0;
}

又加了一个主席树的在线版本。
用优先队列维护右端点，在需要查询的时候更新已经消失的val。然后直接主席树查询第k小即可。

#include <bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 1e5 +11;
const int M =1e6;
int n,m;
struct uzi
{
	int sum,l,r;
}T[N*40];
int now,a[N],b[N],t[N];
void update(int l,int r,int &x,int y,int pos,int val){
	x=++now;
	T[++x]=T[y];T[x].sum+=val;
	if(l==r)return ;
	int mid=l+r>>1;
	if(mid>=pos)update(l,mid,T[x].l,T[y].l,pos,val);
	else update(mid+1,r,T[x].r,T[y].r,pos,val);
}
int get(int now,int l,int r,int k){
	if(T[now].sum<k)return -1;
	if(l==r)return l;
	int mid=l+r>>1;
	if(T[T[now].l].sum>=k)return get(T[now].l,l,mid,k);
	else return get(T[now].r,mid+1,r,k-T[T[now].l].sum);
}
int ab,noa;
int main(){
	for(scanf("%d",&ab);ab;ab--){
		printf("Case %d:\n",++noa );
		scanf("%d",&n);
		int cnt=0;
		now=0;
		priority_queue<pair<int,int> >q;
		for(int i=1;i<=n;i++){
			int opt,l,r,z,val;
			scanf("%d%d%d",&opt,&l,&val);
			if(opt==1){
				scanf("%d",&r);
				update(1,M+1,cnt,cnt,val,1);
				q.push({-r,val});
			}else{
				while(!q.empty()&&-q.top().fi<l){
					update(1,M+1,cnt,cnt,q.top().se,-1);
					q.pop();
				}
				printf("%d\n",get(cnt,1,M+1,val));
			}
		}
	}
	return 0;
}