题面
机翻题目描述
有一天，流浪者 Qwerty 目睹了两艘运输船相互碰撞。结果，他们所有货物的容纳物散落在整个空间中。现在，Qwerty 希望选择尽可能多的丢失物品，以便以后出售。
事实是，两艘船上都有很多新的重力式抓爪，已运往市场。抓取器是一种可以安装在宇宙飞船上的设备，然后将其从太空中吸取到并将其运输到船上的货舱。
总体而言，坠毁的船舶失去了 $n$ 个重力抓取器：第 $i$ 个抓取器位于坐标为 $(x_i,y_i)$ 的点上。每个抓取器都有两个特征- $p_i$（力量）和 $r_i$（动作半径），并且可以抓握质量不超过 $p_i$ 且距离不超过 $r_i$ 的任何物品。抓取器本身也是一个项目，其质量为mi。
Qwerty 的船位于 $(x,y)$ 点，并安装了旧的电磁夹具，其特征为 $p$ 和 $r$。船上的货舱中没有其他抓爪。
找到 Qwerty 可以容纳的最大数量的抓手。当他拾取物品时，他可以任意地在船上的货舱中安装任何抓爪，包括他刚刚抓起的抓爪。在任何时候，船舶只能安装一个抓爪。我们会考虑所有物品，当护林员拿起物品时，将考虑 Qwerty 的船舶是不动的，除了当抓爪移动物品时–然后物品移至货舱并且船舶仍然不动。我们可以假设船上的货舱有足够的空间容纳所有抓爪。Qwerty可以任意多次使用找到的任何夹具或初始夹具。
简化版题目描述
给你一个二维地图，船的坐标为 $(x,y)$，船上预置了一个磁铁，周边有 $n$ 个磁铁。对于每个磁铁，有自己的质量（船上预置的可视为0）、可吸引的最大质量，可吸引的距离。（不考虑衰减啥的）
问最后最多能吸引多少磁铁。
输入格式
第一行包含五个整数 $x,y,p,r,n$（$-10^9 \leq x,y \leq 10^9, 1 \leq p, r \leq 10^9，1 \leq n \leq 250000$）—船的初始位置，初始抓手的特征和 碰撞过程中进入空间的抓爪数量。
接下来的 $n$ 行包含抓取器的描述：第 $i$ 行包含五个整数 $x_i,y_i,m_i,p_i,r_i$（$-10^9 \leq x_i,y_i \leq 10^9, 1 \leq m_i,p_i,r_i \leq 10^9$）—第 $i$ 行抓手的坐标和特征。
确保所有抓爪都位于不同的位置。 与 Qwerty 的船不在同一地点。
输出格式
打印一个数字- Qwerty 可以吸引到他的飞船的最大抓手数量。您无需计算最初的旧磁铁夹具。
样例输入
0 0 5 10 5
5 4 7 11 5
-7 1 4 7 8
0 2 13 5 6
2 -3 9 3 4
13 5 1 9 9
样例输出
3
题解
思路
这个题很容易做一些简单的转化，例如所有 $(x,y)$ 只是用来求到船的距离 $dis$ ，因此可以将 $dis$ 求出。
之后的抓取磁铁，可以发现如果船上存在一个磁铁 $i$，那么它可以吸引任何满足 $ m \leq p_i, dis \leq r_i $ 的磁铁。
那么应该如何解决这个问题呢？如果只用满足单个条件，我们知道可以用树状数组等东西就可以求出了；但现在有了两个条件，因此需要用到神奇的树状数组+堆（算某种意义上的树套树吧）
在树状数组的每一个节点，我们存储此节点区间内的所有磁铁，并按照它们的质量从小到大排序。这样我们在判断一个已有的磁铁能吸取哪些其他磁铁时，就只需要在 query 过程中，将每个节点上的堆顶弹到大于 $p$，弹出的元素即是可以吸取的磁铁。
而为了避免重复弹出，可以再在磁铁上存储一个 $del$ 属性。
所以我们只用将所有磁铁插入到这样的结构中，然后将船上预置的磁铁先插入队列中，用队列来不断吸取新的磁铁，使用旧的磁铁，最后即可得到答案。
代码(1308ms, 47MB)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int x,y,p,r,n;
struct gripper{
int dis,m,p,r;
ll disori;
bool del=false;
}gp[250020];
int lshcnt;
ll lsh[500050];
priority_queue<pair<int,int> > c[500050];
queue<int> availgp;
inline int lowbit(int x){return x&-x;}
inline void insert(int p,int x){
for(;p<=lshcnt;p+=lowbit(p)){
c[p].push(make_pair(-gp[x].m,x));
}
}
inline int query(int r,int m){
int res=0;
for(;r;r-=lowbit(r)){
while(c[r].size()&&c[r].top().first>=-m){
int x = c[r].top().second;
c[r].pop();
if(!gp[x].del){
gp[x].del=true;
availgp.push(x);
++res;
}
}
}
return res;
}
int main(){
scanf("%d%d%d%d%d",&x,&y,&p,&r,&n);
lsh[1]=r;
for(int i=1,xi,yi;i<=n;++i){
scanf("%d%d%d%d%d",&xi,&yi,&gp[i].m,&gp[i].p,&gp[i].r);
gp[i].disori=ceil(sqrt(pow((double)(xi-x),2) +
pow((double)(yi-y),2)));
lsh[i*2]=gp[i].disori;
lsh[i*2+1]=gp[i].r;
}
sort(lsh+1,lsh+1+n*2+1);
lshcnt=unique(lsh+1,lsh+1+2*n+1)-lsh-1;
for(int i=1;i<=n;++i){
gp[i].dis=lower_bound(lsh+1,lsh+1+lshcnt,gp[i].disori)-lsh;
gp[i].r=lower_bound(lsh+1,lsh+1+lshcnt,gp[i].r)-lsh;
insert(gp[i].dis,i);
}
r=lower_bound(lsh+1,lsh+1+lshcnt,r)-lsh;
int ans=query(r,p);
while(!availgp.empty()){
int f=availgp.front();availgp.pop();
ans+=query(gp[f].r,gp[f].p);
}
printf("%d\n",ans);
}
大佬代码(374ms 13.7MB)
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define fill(A,B) memset(A,B,sizeof(A))
#define For(i,A,B) for(int i=(A);i<(int)(B);i++)
#define rep(i,A,B) for(int i=(A);i<=(B);i++)
#define dep(i,B,A) for(int i=(B);i>=(A);i--)
#define re(i,A) for(int i=0;i<(int)(A);i++)
#define de(i,A) for(int i=(A)-1;~i;i--)
#define inf (1<<30)
#define mn 250011
#define P 1000000007
#define si(x) ((int)x.size())
#define MAX(A,B) A=max(A,B)
#define MIN(A,B) A=min(A,B)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline ll pow(ll a,ll b,ll mo){if(!a)return 0;ll tmp=1;for(;b;b>>=1){if(b&1)tmp=(ll)tmp*a%mo;a=(ll)a*a%mo;}return tmp;}
template<class T>inline void R(T &xx){xx=0;char ch=getchar();bool F=0;while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')F=1,ch=getchar();while(ch>='0'&&ch<='9')xx=xx+xx+(xx<<3)+ch-48,ch=getchar();if(F)xx=-xx;}
int n,x0,y0,p,l1,rr=1;pair<ll,int>q[mn];ll r;
struct nod{int p,m;ll d,r;inline bool operator<(const nod&b)const{return d<b.d;}}a[mn];
int seg[mn<<2];
#define ls (x<<1)
#define rs (x<<1|1)
void build(int x,int l,int r){
if(l==r){
seg[x]=a[l].m;return;
}
int mid=l+r>>1;
build(ls,l,mid);build(rs,mid+1,r);
seg[x]=min(seg[ls],seg[rs]);
}
void modi(int x,int l,int r,ll R,int p){
if(seg[x]>p)return;
if(l==r){
q[rr++]=mp(a[l].r,a[l].p);
seg[x]=inf;
return;
}
int mid=l+r>>1;
modi(ls,l,mid,R,p);modi(rs,mid+1,r,R,p);
seg[x]=min(seg[ls],seg[rs]);
}
void que(int x,int l,int r,ll R,int p){
if(a[l].d>R)return;
if(a[r].d<=R){modi(x,l,r,R,p);return;}
int mid=l+r>>1;
que(ls,l,mid,R,p);que(rs,mid+1,r,R,p);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
//freopen("2.out","w",stdout);
#endif
R(x0),R(y0);R(p),R(r),R(n);r*=r;
int x,y;rep(i,1,n)R(x),R(y),R(a[i].m),R(a[i].p),R(a[i].r),a[i].r*=a[i].r,a[i].d=(ll)(x0-x)*(x0-x)+((ll)y0-y)*(y0-y);
sort(a+1,a+1+n);
build(1,1,n);
for(q[0]=mp(r,p);l1<rr;){
// cout<<q[l1].X<<" "<<q[l1].Y<<endl;
que(1,1,n,q[l1].X,q[l1].Y);l1++;
}
printf("%d\n",rr-1);
return 0;
}
大致分析了一下，大佬以排序后磁铁的下标建树，用线段树维护区间最小质量，个人认为非常巧妙的地方，就是将 $dis$ 与 $r$ 进行比较来选取应修改的子树，之后将线段树维护的最小质量同 $p$ 比较，找到适当的磁铁并加入队列，之后直接将其质量赋为 $inf$ 来自然删除。
总结
线段树在使用时不用按照我传统的思维，去单纯通过下标来进行各种操作，而完全可以通过比较其他的单调信息来操作。
在重构时也应当对上一版本程序固化的一些思维进行清理，如这道题一开始我打算通过堆来错误地贪心选取磁铁，但后面想到正确解法时却无法舍弃堆这个思维，导致题虽然做对了但并不优，还去使用了一些自己不太熟悉的东西，不过收获就是略微明白了一些树套树的概念。