解题：洛谷2093JZPFAR

1 // luogu-judger-enable-o2
2 #include
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8 const int N&＃61;100005;
9 const long long inf&＃61;1e9;
10 struct a
11 {
12 int id;
13 long long ds;
14 };
15 bool operator < (a x,a y)
16 {
17 return x.ds&＃61;&＃61;y.ds?x.idy.ds;
18 }
19 priority_queue hp;
20 struct b
21 {
22 int ps[2],mn[2],mx[2],sn[2],id,idn;
23 }kdt[N],qry;
24 int n,m,k,r,f,typ;
25 inline void read(int &x)
26 {
27 x&＃61;0,f&＃61;0; char ch&＃61;getchar();
28 while(!isdigit(ch))
29 f|&＃61;ch&＃61;&＃61;&＃39;-&＃39;,ch&＃61;getchar();
30 while(isdigit(ch))
31 x&＃61;(x<<3)&＃43;(x<<1)&＃43;(ch^48),ch&＃61;getchar();
32 x&＃61;f?-x:x;
33 }
34 void write(int x)
35 {
36 if(x>9) write(x/10);
37 putchar(x%10^48);
38 }
39 bool operator < (b x,b y)
40 {
41 return x.ps[typ]<y.ps[typ];
42 }
43 void Pushup(int nde)
44 {
45 kdt[nde].idn&＃61;kdt[nde].id;
46 int lson&＃61;kdt[nde].sn[0],rson&＃61;kdt[nde].sn[1];
47 b ls&＃61;kdt[lson],rs&＃61;kdt[rson];
48 if(lson) kdt[nde].idn&＃61;min(kdt[nde].idn,ls.idn);
49 if(rson) kdt[nde].idn&＃61;min(kdt[nde].idn,rs.idn);
50 for(int i&＃61;0;i<&＃61;1;i&＃43;&＃43;)
51 {
52 kdt[nde].mn[i]&＃61;kdt[nde].mx[i]&＃61;kdt[nde].ps[i];
53 if(lson) kdt[nde].mn[i]&＃61;min(kdt[nde].mn[i],ls.mn[i]),kdt[nde].mx[i]&＃61;max(kdt[nde].mx[i],ls.mx[i]);
54 if(rson) kdt[nde].mn[i]&＃61;min(kdt[nde].mn[i],rs.mn[i]),kdt[nde].mx[i]&＃61;max(kdt[nde].mx[i],rs.mx[i]);
55 }
56 }
57 int Create(int l,int r,int k)
58 {
59 typ&＃61;k; int mid&＃61;(l&＃43;r)/2;
60 nth_element(kdt&＃43;l,kdt&＃43;mid,kdt&＃43;r&＃43;1);
61 if(l0]&＃61;Create(l,mid-1,k^1);
62 if(r>mid) kdt[mid].sn[1]&＃61;Create(mid&＃43;1,r,k^1);
63 Pushup(mid); return mid;
64 }
65 long long calc1(int nde)
66 {
67 long long mnx&＃61;kdt[nde].mn[0]-qry.ps[0],mxx&＃61;kdt[nde].mx[0]-qry.ps[0];
68 long long mny&＃61;kdt[nde].mn[1]-qry.ps[1],mxy&＃61;kdt[nde].mx[1]-qry.ps[1];
69 return max(mnx*mnx,mxx*mxx)&＃43;max(mny*mny,mxy*mxy);
70 }
71 long long calc2(int nde)
72 {
73 long long dsx&＃61;kdt[nde].ps[0]-qry.ps[0];
74 long long dsy&＃61;kdt[nde].ps[1]-qry.ps[1];
75 return dsx*dsx&＃43;dsy*dsy;
76 }
77 inline bool farther(long long x,long long y)
78 {
79 a t&＃61;hp.top();
80 return x>t.ds||(x&＃61;&＃61;t.ds&&y<t.id);
81 }
82 inline bool further(long long x,long long y)
83 {
84 a t&＃61;hp.top();
85 return x>t.ds||(x&＃61;&＃61;t.ds&&kdt[y].idn<t.id);
86 }
87 void Query(int nde)
88 {
89 b tmp&＃61;kdt[nde]; long long dis&＃61;calc2(nde);
90 int idx&＃61;tmp.id,lson&＃61;tmp.sn[0],rson&＃61;tmp.sn[1];
91 if(farther(dis,idx))
92 hp.pop(),hp.push((a){idx,dis});
93 long long d1&＃61;lson?calc1(lson):-inf,d2&＃61;rson?calc1(rson):-inf;
94 if(d1>d2)
95 {
96 if(further(d1,lson)) Query(lson);
97 if(further(d2,rson)) Query(rson);
98 }
99 else
100 {
101 if(further(d2,rson)) Query(rson);
102 if(further(d1,lson)) Query(lson);
103 }
104 }
105 int main()
106 {
107 register int i;
108 read(n);
109 for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
110 read(kdt[i].ps[0]),read(kdt[i].ps[1]),kdt[i].id&＃61;i;
111 r&＃61;Create(1,n,0),scanf("%d",&m);
112 while(m--)
113 {
114 while(!hp.empty()) hp.pop();
115 read(qry.ps[0]),read(qry.ps[1]),read(k);
116 for(i&＃61;1;i<&＃61;k;i&＃43;&＃43;) hp.push((a){0,-inf});
117 Query(r),write(hp.top().id),puts("");
118 }
119 return 0;
120 }