微信公司网站,网站建设与管理收获,网站设计主要内容,温州建网站公司题意 火星上有$N$个机器人排成一行#xff0c;第$i$个机器人的位置为$x_{i}$#xff0c;视野为$r_{i}$#xff0c;智商为$q_{i}$。我们认为第$i$个机器人可以看到的位置是$[x_{i}-r_{i},x_{i}r_{i}]$。如果一对机器人相互可以看到#xff0c;且它们的智商$q_{i}$的差距不大…题意 火星上有$N$个机器人排成一行第$i$个机器人的位置为$x_{i}$视野为$r_{i}$智商为$q_{i}$。我们认为第$i$个机器人可以看到的位置是$[x_{i}-r_{i},x_{i}r_{i}]$。如果一对机器人相互可以看到且它们的智商$q_{i}$的差距不大于$K$那么它们会开始聊天。 为了防止它们吵起来请计算有多少对机器人可能会聊天。 题解 先膜一下大佬-这里 我们先按视野降序排序这样一个一个考虑如果后面的能看到前面那前面的也肯定能看到后面 这样就是对于每一个机器人在他前面有几个智商在$[q-k,qk]$位置在$[x-r,xr]$ 那么把这个东西看做一个矩形覆盖就可以了 然后因为智商这一维维数很小我们可以对每一个智商开一个动态开点线段树然后一个一个扫过去统计答案就可以了 1 //minamoto2 #includeiostream3 #includecstdio4 #includealgorithm5 #includemap6 #define ll long long7 using namespace std;8 #define getc() (p1p2(p2(p1buf)fread(buf,1,121,stdin),p1p2)?EOF:*p1)9 char buf[121],*p1buf,*p2buf;
10 inline int read(){
11 #define num ch-0
12 char ch;bool flag0;int res;
13 while(!isdigit(chgetc()))
14 (ch-)(flagtrue);
15 for(resnum;isdigit(chgetc());resres*10num);
16 (flag)(res-res);
17 #undef num
18 return res;
19 }
20 const int N1e55;
21 int n,k,m,b[N*3];ll res;
22 mapint,int rt;int L[N5],R[N5],sum[N5],cnt0;
23 void update(int p,int l,int r,int x){
24 sum[p];if(lr) return;
25 int mid(lr)1;
26 if(xmid) update(L[p]L[p]?L[p]:cnt,l,mid,x);
27 else update(R[p]R[p]?R[p]:cnt,mid1,r,x);
28 }
29 int query(int p,int l,int r,int ql,int qr){
30 if(qllqrr||p0) return sum[p];
31 int mid(lr)1,res0;
32 if(qlmid) resquery(L[p],l,mid,ql,qr);
33 if(qrmid) resquery(R[p],mid1,r,ql,qr);
34 return res;
35 }
36 inline void ins(int q,int x){
37 if(rt.count(q)0) rt[q]cnt;
38 update(rt[q],1,m,x);
39 }
40 inline int get(int q,int ql,int qr){
41 if(rt.count(q)0) return 0;
42 return query(rt[q],1,m,ql,qr);
43 }
44 struct node{
45 int x,r,q;
46 node(){}
47 node(int x,int r,int q):x(x),r(r),q(q){}
48 inline bool operator (const node b)const
49 {return rb.r;}
50 }a[N];
51 int main(){
52 // freopen(testdata.in,r,stdin);
53 nread(),kread();
54 for(int i1;in;i){
55 int xread(),rread(),qread();
56 a[i]node(x,r,q);
57 b[m]x,b[m]x-r,b[m]xr;
58 }
59 sort(b1,b1m),munique(b1,b1m)-b-1;
60 sort(a1,a1n);
61 for(int i1;in;i){
62 int llower_bound(b1,b1m,a[i].x-a[i].r)-b;
63 int rlower_bound(b1,b1m,a[i].xa[i].r)-b;
64 int xlower_bound(b1,b1m,a[i].x)-b;
65 for(int ja[i].q-k;ja[i].qk;j)
66 resget(j,l,r);
67 ins(a[i].q,x);
68 }
69 printf(%lld\n,res);
70 return 0;
71 } 转载于:https://www.cnblogs.com/bztMinamoto/p/9749892.html
