Description

盟军司令决定采用飞机对德军设在海岸线上的机枪阵地进行定点清除。为简化模型，这里将德军防线看成一条直线。而每个阵地都是这条线上的一个点。阵地依次编号为1-N，其中第k个阵地的坐标为X~k~。此外，每个阵地还有一个防御值D~k~。
盟军飞机扔下的炸弹不是完全相同的。每颗炸弹均有一个破坏值A~i~和一个范围值B~i~，对于编号为~i~的炸弹，如果它在防线上坐标为Y~i~的点爆炸，那么它将炸毁坐标在[Y~i~-B~i~,Y~i~+B~i~]范围中所有D~k~<=A~i~的尚未被炸毁的德军阵地。而同时对其他针对不造成任何影响。
现在已知：阵地数，每个阵地的X~k~和D~k~（k=1,2,…,N），以及发射的炮弹数，和按照炮弹爆炸顺序给出的每个炸弹的A~i~，B~i~和Y~i~。（i=1,2,…,M）
你能帮助盟军计算出每颗炸弹究竟能摧毁了多少个阵地吗？

Input

输入文件包含多组输入数据。

对于每组数据，第一行是一个整数N（1<=N<=100000），接下来N行，每行两个整数X,D（0<=X，D<=10^9^），分别是其对应的阵地的坐标和防御值。其次是一个整数M（1<=M<=100000），接下来M行，每行三个整数A,B,Y（0<=A,B,Y<=10^9^），按爆炸先后顺序（没有两颗炸弹在同一时刻爆炸）给出了每颗炸弹的破坏值，范围值和爆炸坐标。

N=0时表示输入结束。

Output

对于输入的每一组数据，输出M行。每行分别是其所对应的炸弹摧毁的阵地的数量。相邻两组数据间不要有空行。

Sample Input

1
2
3
4
5
6
7
8
9
3
1 1
2 2
3 3
3
2 0 1
10 10 10
100 100 0
0

Sample Output

1
2
3
1
2
0

Solution

对于这一道题而言，我们可以发现，每一个阵地最多被摧毁一次，且只会被一次摧毁，因此每一个阵地最多对答案产生1的贡献，所以说我们可以log⁡n\log n暴力修改（删除）。

那总共的时间复杂度为O(nlog⁡n)O(n \log n)

有几种做法：

  • 使用线段树区间查询最小值，++ans，然后把这个点修改为∞\infin，重复循环直到最小值为∞\infin，如果代码打的足够优秀常数就会非常的小，复杂度为O(nlog⁡n)O(n \log n)。
  • 使用setset，快速查询在区间[Yi−Bi,Yi+Bi][Y_i-B_i,Y_i+B_i]的最小值，快速删除，但是常数会有一点点大，需要进行“常数性优化”。复杂度为O(nlog⁡n)O(n \log n)
  • 直接暴力nmnm，（别问我为什么跑得比stdstd还快……）

作为一个懒人，当然是STLSTL大法好，所以嘛……

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 常数性优化……
// ……
#include <set>
#include <cstdio>
#include <algorithm>
#define N 100005
#define sit set<int>::iterator
#define isdigit(x) (x>47 && x<58)
#define lb(a) (lower_bound(x+1,x+n+1,a)-x)
using namespace std;
long long x[N],y[N],d[N];
int n,id[N],m;
inline bool cmp(int i,int j)
	{ return x[i]<x[j]; }
inline int read()
{
	int t = 0; bool f = 0; char v = getchar();
	for (; !isdigit(v); v = getchar()) ;
	for (;  isdigit(v); v = getchar())
		t = (t << 3) + (t << 1) + (v ^ 48);
	return f ? (~t + 1) : t;
}
set<int> s;
int main()
{
	while (1)
	{
		if ((n=read())==0) break;s.clear();
		for (register long long i=1;i<=n;++i) {
			x[i]=read(),d[i]=read(),
			id[i]=i,s.insert(i);
		}sort(id+1,id+n+1,cmp);
		sort(x+1,x+n+1);
		x[n+1]=100000000000000;
		s.insert(n+1),m=read();
		for (int ans=0;m--;ans=0)
		{
			register long long a=read(),b=read(),y=read();
			sit it=s.lower_bound(lb(y-b));
			while (x[*it]<=y+b)
				if (d[id[*it]]<=a)
					s.erase(it++),++ans;
				else ++it;
			printf("%d\n",ans);
		}
	}
}