拿到本题rank2。其实rank1好像是评测波动

因为每次查询区间的大小都小于$2*m$，所以块大小设为$\sqrt{2*m}$达到最优，而且修改$O(1)$会很快

但为什么比O(n)贪心还快一点

// SeptEtavioxy
#define re register
#define ll long long
#define il inline
#define rep(i,s,t) for(re int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(re int i=(s);i>=(t);i--)
enum{N=500024};
class SQR{
public:
	int n,block;
	il void init(){
		head[1]= 1;
		for(b=1;b*block<n;b++){
			head[b+1]= b*block+1;
			rep(i,head[b],head[b+1]-1) pos[i]= b;
		}
		head[b+1]= n+1;
		rep(i,head[b],head[b+1]-1) pos[i]= b;
		memset(mn,0x3f,sizeof(mn));
		memset(Mn,0x3f,sizeof(Mn));
	}
	il void add(int x,int k){
		mn[x]= min(mn[x],k);
		Mn[pos[x]]= min(Mn[pos[x]],k);
	}
	il int query(int l,int r){
		int L= pos[l], R= pos[r];
		re int ans= 1e9;
		if( L==R ){
			rep(i,l,r) ans=min(ans,mn[i]);
		}
		else{
			rep(i,L+1,R-1) ans=min(ans,Mn[i]);
			rep(i,l,head[L+1]-1) ans=min(ans,mn[i]);
			rep(i,head[R],r) ans=min(ans,mn[i]);
		}
		return ans;
	}
private:
	int b;
	int mn[N],Mn[N];
	int pos[N],head[N];
}Sqr;

Sqr.n= mx-mn+1;
Sqr.block= max(1,(int)sqrt(m*2));
Sqr.init();
int base= -mn+1;