两句话意思有差别么,复杂度大了10倍,大佬求解??
查看原帖
两句话意思有差别么,复杂度大了10倍,大佬求解??
458522
wjslaity楼主2021/6/26 16:08

我的代码,然后出错的地方找出来了,在下面

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node{
	int l,r,id,res;
}a[N];

int cnt[N],vis[N],blo[N],bl;

bool cmp(node a,node b){
return (a.l / bl) == (b.l / bl) ? a.r < b.r : a.l < b.l;
/*写成这样复杂度增加10倍超时 
	if(a.l==b.l) return a.r<b.r;
	return a.l<b.l;
*/
}

bool cmp1(node a,node b){
	return a.id<b.id;
} 

int ans=0;
void add(int x){
	if(vis[cnt[x]]==1) ans++;
	vis[cnt[x]]++;
}
void remove(int x){
	vis[cnt[x]]--;
	if(vis[cnt[x]]==1) ans--;
}

int main(){
	memset(vis,0,sizeof(vis));
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&cnt[i]);
	for(int i=1;i<=m;i++){//输入 
		a[i].id=i;
		scanf("%d%d",&a[i].l,&a[i].r);
	}
	
	bl=sqrt(n);//分块 
	
	sort(a+1,a+m+1,cmp);//对数据按照指针进行排序
	 
	
	int L=1,R=0;
	for(int i=1;i<=m;i++){
		while(L<a[i].l) remove(L++);
		while(L>a[i].l) add(--L);
		while(R<a[i].r) add(++R);
		while(R>a[i].r) remove(R--);
		a[i].res=ans;
	}
	
	sort(a+1,a+m+1,cmp1);//以id复原结构体数组 
	
	for(int i=1;i<=m;i++){
		if(a[i].res) printf("No\n");
		else printf("Yes\n");
	}
	return 0;
} 

这是出错的地方

bool cmp(node a,node b){
return (a.l / bl) == (b.l / bl) ? a.r < b.r : a.l < b.l;
/*写成这样复杂度增加10倍超时 
	if(a.l==b.l) return a.r<b.r;
	return a.l<b.l;
*/
}

这两句话意思不都一样么,一个用到了blo,我不清楚这题跟分块有什么关系,哎,各位大佬求解???

2021/6/26 16:08
加载中...