求助P4137 Rmq Problem / mex莫队re问题
  • 板块学术版
  • 楼主初云悕
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/11/4 20:06
  • 上次更新2023/11/5 09:00:39
查看原帖
求助P4137 Rmq Problem / mex莫队re问题
91381
初云悕楼主2020/11/4 20:06

最后一个点re了,调了两个小时了,发现在sort的地方就无法运行下去了,请问是写法上有什么问题吗

#include <bits/stdc++.h>
#define panhan using
#define no namespace
#define xm std;
#define int long long
panhan no xm;
inline int read(){
	int sum=0,ff=1; char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(isdigit(ch))
		sum=sum*10+(ch^48),ch=getchar();
	return sum*ff;
}
const int N = 2e6+5;
int kun[N] , ton[N] , a[N] , b[N] , n , m , kc , ans, an[N];
struct node {
	int l , r , id;
	bool operator < (const node &p) const {return kun[l] == kun[p.l] ? (kun[r] == kun[p.r] ? l <= p.l : kun[r] <= kun[p.r]) : kun[l] < kun[p.l];}
} cun[N];
void add(int now) {
	if(a[now]>1e5)return ;
	if(++ton[a[now]]==1 && ans == a[now]) 
		while(ton[ans]) 
			ans++;
}
void del(int now) {
	if(a[now]>1e5)return ;
	if(--ton[a[now]]==0 && ans>a[now])
		ans=a[now]; 
}
main() {
	//freopen("s.in","r",stdin);
	//freopen("ans.out","w",stdout);
	n = read() , m = read();
	kc = sqrt(n);
	for(int i = 1 ; i <= n ; i ++) a[i] = read() , kun[i] = (i - 1) / kc + 1;
	for(int i = 1 ; i <= m ; i ++) cun[i].l = read() , cun[i].r = read() , cun[i].id = i;
	sort(cun+1,cun+1+m);
//cout<<"do"<<endl;
	//return 0;
	int l = 1 , r = 0 ;
	
	for(int i = 1 ; i <= m ; i ++) {
		while(l<cun[i].l) del(l++);
		while(l>cun[i].l) add(--l);
		while(r>cun[i].r) del(r--);
		while(r<cun[i].r) add(++r);
		an[cun[i].id] = ans;
	}
	for(int i = 1 ; i <= m ; i ++)  cout << an[i] <<endl;
}
2020/11/4 20:06
加载中...