社区讨论
为啥我写的sort过不了,归并能过
P2163[SHOI2007] 园丁的烦恼参与者 3已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mkmq77s4
- 此快照首次捕获于
- 2026/01/20 23:05 4 周前
- 此快照最后确认于
- 2026/01/24 15:11 4 周前
下面代码 ,link
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 条回复,欢迎继续交流。
正在加载回复...