为什么固定左端点往右找就行,固定右端点往左找就不行?
查看原帖
为什么固定左端点往右找就行,固定右端点往左找就不行?
564225
dontwannacry楼主2024/9/19 11:12

固定左端点往右找,AC的solve:

void solve(int l,int r,int L,int R){
	if(l > r) return;
	int mid = (l+r)>>1,ml = L;long long maxn = 0x8000000000000000;
	for(int i = max(L,mid+K-1);i <= R;++i){
		result res = findk(K,root[mid-1],root[i],1,tot);
		res.l = mid;res.r = i;
		res = res+(sum[mid-1]-sum[i]);
		if(res.sum >= maxn){ml = i;maxn = res.sum;}
		if(res.sum > ans){Re.clear();ans = res.sum;}
		if(res.sum == ans){Re.push_back(res);}
	}
	solve(l,mid-1,L,ml);
	solve(mid+1,r,ml,R);
}
......
solve(1,N-K+1,K,N);

固定右端点往左找,85tps,WA on #18\

void solve(int l,int r,int L,int R){
	if(l > r) return;
	int mid = (l+r)>>1,ml = L;long long maxn = 0x8000000000000000;
	for(int i = min(R,mid-K+1);i >= L;--i){
		result res = findk(K,root[i-1],root[mid],1,tot);
		res.l = i;res.r = mid;
		res = res+(sum[i-1]-sum[mid]);
		if(res.sum >= maxn){ml = i;maxn = res.sum;}
		if(res.sum > ans){Re.clear();ans = res.sum;}
		if(res.sum == ans){Re.push_back(res);}
	}
	solve(l,mid-1,L,ml);
	solve(mid+1,r,ml,R);
}
......
solve(K,N,1,N-K+1);

从CEOI2023官网把数据下下来后,以下数据能把的错误代码卡掉(写的是目录)
(trade\subtasks\Subtask_4\Group_1\Case_26)
即(trade\cases_by_hash\60fd86b51dcfd8-c5af73c457d3ee)

2024/9/19 11:12
加载中...