经过一系列卡常，终于在POJ过了，但还是困惑，为什么我用时需要1.2s这么长
by Austra @ 2023-06-02 11:08:07
@[Austra](/user/124564) 把unordered_map扔了，学习使用lower_bound的离散化写法
by yhk1001 @ 2023-08-10 09:37:35
@[yhk1001](/user/191754) 理论上来说lower_bound复杂度是log，unordered_map是O(1)吧
by Austra @ 2023-08-10 09:58:32
@[Austra](/user/124564) 但是换了之后，洛谷1.27s $\to$ 1.13s
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#define int long long
using namespace std;
const int MAX=5e5+5;
int q,n,m,ans;
double w,h,val[MAX];
unordered_map<double,int>hs;
struct tree{
int l,r,tag,ans;
//ans表示这个区间的答案，tag懒标记
}t[MAX*4];
struct segement{
double y,x1,x2;
int k;
}c[MAX];
void build(int p,int l,int r){
t[p].l=l,t[p].r=r,t[p].ans=0,t[p].tag=0;
if(l==r)return ;
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}
void spread(int p){
if(t[p].tag){
t[p*2].tag+=t[p].tag;
t[p*2+1].tag+=t[p].tag;
t[p*2].ans+=t[p].tag;
t[p*2+1].ans+=t[p].tag;
t[p].tag=0;
}
}
void change(int p,int l,int r,int d){
spread(p);
if(t[p].l>=l&&t[p].r<=r){t[p].ans+=d,t[p].tag+=d;return ;}
int mid=(t[p].l+t[p].r)/2;
if(mid>=l)change(p*2,l,r,d);
if(mid<r)change(p*2+1,l,r,d);
t[p].ans=max(t[p*2].ans,t[p*2+1].ans);
}
bool cmp(segement a,segement b){return a.y<b.y;}
signed main(){
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
scanf("%lld",&q);
while(q--){
scanf("%lld%lf%lf",&n,&w,&h);
m=2*n,w-=0.5,h-=0.5,ans=0;
build(1,1,m);
for(int i=1;i<=n;i++){
double x,y; int l;
scanf("%lf%lf%lld",&x,&y,&l);
int a=2*(i-1)+1,b=2*i;
val[a]=x,val[b]=x+w;
c[a].y=y,c[a].x1=x,c[a].x2=x+w,c[a].k=l;
c[b].y=y+h,c[b].x1=x,c[b].x2=x+w,c[b].k=-l;
}
sort(c+1,c+m+1,cmp);
sort(val+1,val+m+1);
m=unique(val+1,val+m+1)-val-1;
// for(int i=1;i<=m;i++)hs[val[i]]=i;
for(int i=1;i<2*n;i++){
// int l=hs[c[i].x1],r=hs[c[i].x2];
int l, r;
l = lower_bound(val + 1, val + m + 1, c[i].x1) - val;
r = lower_bound(val + 1, val + m + 1, c[i].x2) - val;
change(1,l,r-1,c[i].k);
ans=max(t[1].ans,ans);
}
printf("%lld\n",ans);
}
return 0;
}
```
by yhk1001 @ 2023-08-10 10:16:03