CCPC－Wannafly & Comet OJ 夏季欢乐赛（2019）D
|
题面 ? ? ? 一开始想到一个 O(N^2) 做法，先把x排序，然后顺次枚举x最大的点，看向前最多可以保留多少点 (也就是先不管正方形的上下长度限制，先考虑左右的限制)。然后再对这些点做一遍类似的。。(等等这么一说感觉怎么成 O(N^2 logN)的了23333)。 ? ? 但反正这样肯定是不行的，数据太大了，我们要做一些优化。 ? ? 我们保留限制左右边界的这个过程，看能不能优化一下限制y坐标找答案的过程。 ? ? 显然，加入纵坐标为y的点之后，第 y 到 第 y+k 的叶子的答案都会 +1；删点反之。 ? ? 于是我们把x坐标排序后单调扫一遍，边扫边维护线段树最大值&更新答案就可以了。 ? ? 不过现在还有一点小问题:线段树的叶子节点有多大 2*10^9多个。 ? ? 直接写的话因为涉及的边界叶子不多，所以动态开点线段树应该是可以过的；但我们想要时空复杂度更低的算法，那么考虑一下是否可以离散化呢？ ? ? 像这种叶子过多的线段树想要离散化的话，必须可以证明出其正确性：比如这个题，我们称一个没有被任何y[i]与y[i]+k覆盖到的纵坐标为空点，其余为非空点。如果离散化的话，我们就默认最后的答案一定是在非空点处取到。事实也的确是这样的，考虑一个空点，如果它要被区间+1覆盖到，它两边最近的非空点肯定也会被覆盖到；区间-1的话可能看成之前那个区间+1被撤销了，所以不用考虑。 ? ? ? 恩，这样就可以很舒服的AC，代码也很好写。 #include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005;
#define lc (o<<1)
#define mid (l+r>>1)
#define rc ((o<<1)|1)
inline int read(){
int x=0; char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘;
return x;
}
struct node{
int x,y,z;
bool operator <(const node &u)const{
return x<u.x;
}
}a[N];
int n,k,num[N*2],ky,ans,w;
int mx[N*8+1],tag[N*8+1],le,ri;
inline void Get(int o,int ad){ tag[o]+=ad,mx[o]+=ad;}
inline void pushdown(int o){ Get(lc,tag[o]),Get(rc,tag[o]=0;}
void update(int o,int l,int r){
if(l>=le&&r<=ri){ Get(o,w); return;}
pushdown(o);
if(le<=mid) update(lc,l,mid);
if(ri>mid) update(rc,mid+1,r);
mx[o]=max(mx[lc],mx[rc]);
}
inline void solve(){
sort(a+1,a+n+1);
for(int i=1;i<=n;i++) num[++ky]=a[i].y,num[++ky]=a[i].z;
sort(num+1,num+ky+1),ky=unique(num+1,num+ky+1)-num-1;
for(int i=1;i<=n;i++){
a[i].y=lower_bound(num+1,num+ky+1,a[i].y)-num;
a[i].z=lower_bound(num+1,a[i].z)-num;
}
for(int i=1,l=1;i<=n;ans=max(ans,mx[1]),i++){
while(a[i].x-a[l].x>k) le=a[l].y,ri=a[l].z,w=-1,update(1,1,ky),l++;
le=a[i].y,ri=a[i].z,w=1,ky);
}
}
int main(){
n=read(),k=read();
for(int i=1;i<=n;i++)
a[i].x=read(),a[i].y=read(),a[i].z=a[i].y+k;
solve(),printf("%dn",ans);
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |