社区讨论
为什么我这里用stable_sort会AC,而用了sort会0pts
P2163[SHOI2007] 园丁的烦恼参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lr7oqxed
- 此快照首次捕获于
- 2024/01/10 19:16 2 年前
- 此快照最后确认于
- 2024/01/10 19:52 2 年前
CPP
#include<bits/stdc++.h>
//#define int long long
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int N=4e6+5;
struct node{
int x,y,id;
}a[N];
int lsh[N],len,n,m,len1,tot[N];
int ans[N][5];
struct Binarytree{
int t[N<<1];
void ud(int x){
while(x<=n){
t[x]++;
x+=x&-x;
}
}
int ask(int x){
int ret=0;
while(x){
ret+=t[x];
x-=x&-x;
}
return ret;
}
}bit;
int lsh_(int x){
return lower_bound(lsh+1,lsh+len+1,x)-lsh;
}
int32_t main(){
std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
rep(i,1,n){
int x,y;
cin>>x>>y;
a[i]={x,y,0};
lsh[++len1]=y;
}
rep(i,1,m){
int x1_,y1_,x2_,y2_;
cin>>x1_>>y1_>>x2_>>y2_;
a[++n]={x1_-1,y1_-1,i};
a[++n]={x2_,y2_,i};
a[++n]={x1_-1,y2_,i};
a[++n]={x2_,y1_-1,i};
lsh[++len1]=y1_-1;lsh[++len1]=y2_;
}
sort(lsh+1,lsh+len1+1);
len=unique(lsh+1,lsh+len1+1)-lsh-1;
///////////////////////////////////////////////////
stable_sort(a+1,a+n+1,[](const node& x_,const node& y_){
return x_.x<y_.x;
});//here turn into sort will get 0pts!!!
///////////////////////////////////////////////////
rep(i,1,n){
if(a[i].id){
ans[a[i].id][++tot[a[i].id]]=bit.ask(lsh_(a[i].y));
}else{
bit.ud(lsh_(a[i].y));
}
}
rep(i,1,m){
sort(ans[i]+1,ans[i]+5);
cout<<ans[i][4]-ans[i][3]-ans[i][2]+ans[i][1]<<'\n';
}
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...