CF940F Machine Learning

CF940F Machine Learning

首先显然可以直接树套树做，在权值线段树上二分即可。

但是这里数据 1e5 并且可以离线，我们可以想到直接莫队/值域分块来做。

那么直接带修莫队暴力维护即可。

代码：

#include
const int M=1e5+5;
template 
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return ;
}
template 
inline void write(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
	return ;
}
int n,m,p,len,cnt1,cnt2,a[M],lsh[M<<1],ans[M];
int CB[M],num[M<<1];
int L=1,R=0,T=0;
struct Query{
	int L,R,t,p1,p2,id;
	inline bool operator<(const Query&it)const{return p1==it.p1?p2==it.p2?tQL)Add(a[--L]);
		while(LQR)Del(a[R--]);
		while(TQT)Modify(T--);
		for(int&cur=ans[q[i].id]=1;CB[cur];++cur);
	}
	for(int i=1;i<=cnt1;++i) write(ans[i]),putchar('\n');
	return 0;
}