社区讨论

为啥我写的sort过不了,归并能过

P2163[SHOI2007] 园丁的烦恼参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mkmq77s4
此快照首次捕获于
2026/01/20 23:05
4 周前
此快照最后确认于
2026/01/24 15:11
4 周前
查看原帖
下面代码 80pts80ptslink
CPP
#include<bits/stdc++.h>
using namespace std;
struct tree{
	int x;
	int yt;
	int y;
}a[500005];
struct que{
	int x;
	int yt;//一开始
	int y;//离散化后的 
	int ans;
	int b;
}q[2000005];
bool cmp0(tree a1,tree a2){
	return a1.yt<a2.yt;
} 
bool cmp1(tree a1,tree a2){
	return a1.x<a2.x;
}
bool cmp2(que a1,que a2){
	return a1.x<a2.x;
}
bool cmp3(que a1,que a2){
	return a1.b<a2.b;
}
bool cmp4(que a1,que a2){
	return a1.yt<a2.yt;
}
int n,Q;

//树状数组 
int s[500005];
int lowbit(int n){
	return n&(-n);
} 
void add(int rt){
	while (rt<=n){
		s[rt]++;
		rt+=lowbit(rt);
	}
}
int sum(int rt){
	int ans=0;
	while (rt>0){
		ans+=s[rt];
		rt-=lowbit(rt);
	}
	return ans;
}
int main(){
	cin>>n>>Q;
	for (int i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].yt);
	}
	for (int i=1;i<=Q;i++){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);;
		q[i*4-3]=(que){c,d,0,0,i*4-3};
		q[i*4-2]=(que){a-1,b-1,0,0,i*4-2};
		q[i*4-1]=(que){a-1,d,0,0,i*4-1};
		q[i*4]=(que){c,b-1,0,0,i*4};
	}
	//离散化 
	sort(a+1,a+n+1,cmp0);
	sort(q+1,q+4*Q+1,cmp4);
	int pt=0;
	a[0].y=0,a[0].yt=-2; 
	for (int i=1;i<=n;i++){
		if (a[i].yt==a[i-1].yt){
			a[i].y=a[i-1].y;
		}
		else{
			a[i].y=a[i-1].y+1;
			while (pt<4*Q&&q[pt+1].yt<a[i].yt){
				pt++;
				q[pt].y=a[i-1].y;
			}
		}
	}
	for (int i=pt+1;i<=4*Q;i++)
		q[i].y=a[n].y;
	//离线树状数组 
	sort(a,a+n+1,cmp1);
	sort(q,q+4*Q+1,cmp2);
	pt=0;
	for (int i=1;i<=4*Q;i++){
		while (pt<n&&a[pt+1].x<=q[i].x){
			pt++;
			add(a[pt].y);
		}
		q[i].ans=sum(q[i].y);
	} 
	//恢复原序输出 
	sort(q,q+4*Q+1,cmp3);
	for (int i=1;i<=Q;i++){
		printf("%d\n",q[i*4-3].ans+q[i*4-2].ans-q[i*4-1].ans-q[i*4].ans);
	}
	return 0;
} 
把全部改成 stable_sort 就过了,sort跑不过归并? 要睡了,可能明天才能回,抱歉。

回复

5 条回复,欢迎继续交流。

正在加载回复...