[题解]cqoi2017老C的任务

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 2.6k | 阅读时长 ≈ 2 分钟

题目描述

洛谷

题解

由于题目不强制在线，我们可以将所有询问离线解决。

思考如果只有一个询问如何解决？显然可以用二维前缀和搞定。

对于每个询问，我们只需要求出四个点的答案，假设对角坐标（左下和右上）为$(a,b),(c,d)$，我们只需要求出$(a-1,b-1),(c,b-1),(a-1,d),(c,d)$左下方的所有基站功率之和即可。

$n<=10^5$，直接$O(n^2)$暴力显然不可取。

假设我们目前求的点为$(x,y)$，需要统计的即所有满足$x_i<=x,y_i<=y$的基站权值之和。

（坐标数值较大，需要先进行离散化。）

可以先将基站的点和每个询问要求的点合在一起。维护一个一维的树状数组$t$，统计横坐标为$x$的基站功率和，按$y$从小到大先排序一遍，然后进行遍历，当遍历到基站时$i$时，对$x_i$进行单点加;当遍历到询问点$j$时，统计$1$~$x_j$区间和即可（此处$1,x_i,x_j$均为离散化后的横坐标），这样保证了两个条件（$x<=x_j,y<=y_j$）

Code

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;

int read()
{
	int sum = 0 , f = 1;
	char c = getchar();
	while(c < '0' or c > '9')
	{
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' and c <= '9')
	{
		sum = sum * 10 + c - '0';
		c = getchar();
	}
	return sum * f;
}

int n , m , cnt , len;
long long ans[100010];
struct Node{
	int x , y;
	int rk ;
	long long power;
	bool p;
}a[500010];

long long tree[100010];
int b[500010];

bool cmp(Node a , Node b)
{
	if(a.y == b.y) 
	{
		if(a.x == b.x) return a.p > b.p;
		return a.x < b.x;
	}
	return a.y < b.y;
}
int lowbit(int x)
{
	return x & -x;
}
void add(int pos , int w)
{
	while(pos <= len) tree[pos] += w , pos += lowbit(pos);
}
long long query(int pos)
{
	long long sum = 0;
	while(pos) sum += tree[pos] , pos -= lowbit(pos);
	return sum;
}

int main()
{
	n = read() , m = read();
	for(int i = 1; i <= n; i ++)
	{
		a[++ cnt].x = read() , a[cnt].y = read() , a[cnt].power = read();
		b[cnt] = a[cnt].x;
		a[cnt].p = 1;
	}
	for(int i = 1; i <= m; i ++)
	{
		int A = read() , B = read() , c = read() , d = read();
		a[++ cnt].x = A - 1 , a[cnt].y = B - 1 , a[cnt].rk = i;
		b[cnt] = a[cnt].x;
		a[++ cnt].x = c , a[cnt].y = B - 1 , a[cnt].rk = -i;
		b[cnt] = a[cnt].x;
		a[++ cnt].x = A - 1 , a[cnt].y = d , a[cnt].rk = -i;
		b[cnt] = a[cnt].x;
		a[++ cnt].x = c , a[cnt].y = d , a[cnt].rk = i;
		b[cnt] = a[cnt].x;
	}	
	sort(b + 1 , b + cnt + 1);
	len = unique(b + 1 , b + cnt + 1) - b - 1;
	for(int i = 1; i <= cnt; i ++) a[i].x = lower_bound(b + 1 , b + len + 1 , a[i].x) - b;
	sort(a + 1 , a + cnt + 1 , cmp);
	for(int i = 1; i <= cnt; i ++)
	{
		if(a[i].p)
		{
			add(a[i].x , a[i].power);
		 } 
		else
		{
			int k = abs(a[i].rk);
			if(a[i].rk < 0) ans[k] -= query(a[i].x);
			else ans[k] += query(a[i].x);
		}
	}
	for(int i = 1; i <= m; i ++) printf("%lld\n" , ans[i]);
	return 0;
}