题意
在管道的焦点处有N个种群数目为Pi的鼠群，N<20000，现在要在某个焦点处放一个炸弹，炸弹效力范围是以炸弹为中点的2d*2d的矩形。问炸弹放在哪里可以炸死最多的老鼠，如果有重复则优先保证X坐标最小，如果还有重复就Y坐标最小。
解法
这种题目一般是采用X扫描线+平衡树/树状数组统计的方法。但是这题由于还有第二和第三优先级，我们必须扫描线移动一下就统计一下，不能等到扫描线距离达到2d再统计，然后小x坐标就是后扫描线坐标减去d。用平衡树/树状数组统计时也要注意这个问题。详细情况见代码（我依然很猥琐的用了STL MAP）
PS，好不容易一题在poj rank进前3，不容易啊。。
1
# include <cstdio>
2# include <map>
3# include <algorithm>
4using namespace std;
5struct node
6
{
7
int x,y,num;
8 bool operator<(const node &pos) const
9
{
10 return x<pos.x;
11
}
12
}data[20005];
13int d,n;
14map<int,int> refer;
15void calbest(int nx,int &best,int &x,int &y)
16{
17 map<int,int>::iterator s=refer.begin(),e=refer.begin();
18 int total=0,last=e->first;
19 while(e!=refer.end())
20 {
21 while(e!=refer.end()&&e->first<=s->first+2*d)
22 {
23 total+=e->second;
24 last=e->first;
25 e++;
26 }
27 if(total>best||total==best&&nx-d<x||total==best&&nx-d==x&&last-d<y)
28 best=total,x=nx-d,y=last-d;
29 total-=s->second;
30 s++;
31 }
32}
33int main()
34{
35 //freopen("ans.txt","w",stdout);
36 int test;
37 scanf("%d",&test);
38 while(test--)
39 {
40 scanf("%d%d",&d,&n);
41 for(int i=0;i<n;i++)
42 scanf("%d%d%d",&data[i].x,&data[i].y,&data[i].num);
43 sort(data,data+n);
44 int s=0,e=0;
45 refer.clear();
46 int best=-1,y,x;
47 while(e<n)
48 {
49 int tmp;
50 while(true)
51 {
52 if(e>=n||data[e].x-data[s].x>2*d) break;
53 tmp=data[e].x;
54 while(e<n&&data[e].x==tmp)
55 {
56 refer[data[e].y]+=data[e].num;
57 e++;
58 }
59 calbest(data[e-1].x,best,x,y);
60 }
61 tmp=data[s].x;
62 while(data[s].x==tmp&&s<n)
63 {
64 refer[data[s].y]-=data[s].num;
65 if(refer[data[s].y]==0) refer.erase(data[s].y);
66 s++;
67 }
68 }
69 printf("%d %d %d\n",x>=0?x:0,y>=0?y:0,best);
70
71 }
72 return 0;
73}
74
75