A - 子段求和
给出一个长度为N的数组，进行Q次查询，查询从第i个元素开始长度为l的子段所有元素之和。
例如，1 3 7 9 -1，查询第2个元素开始长度为3的子段和，1 {3 7 9} -1。3 + 7 + 9 = 19，输出19。
Input
第1行：一个数N，N为数组的长度(2 <= N <= 50000)。 第2 至 N + 1行：数组的N个元素。(-10^9 <= Ni <= 10^9) 第N + 2行：1个数Q，Q为查询的数量。 第N + 3 至 N + Q + 2行：每行2个数，i，l（1 <= i <= N，i + l <= N)
Output
共Q行，对应Q次查询的计算结果。
Sample Input
5
1
3
7
9
-1
4
1 2
2 2
3 2
1 5
Sample Output
4
10
16
19
/*-------------A - 子段求和---------------*/
#include<iostream>
using namespace std;
int main() {
long long n, m;
long long a[50010], b[50010] = { 0 };
cin >> n;
for (long long i = 0; i < n; i++) {
cin >> a[i];
b[i + 1] = b[i] + a[i];//求前缀和;
}
cin >> m;
while (m--) {
int c, d;
cin >> c >> d;
cout << b[d + c - 1] - b[c - 1] << '\n';
}
}B - 子矩阵求和
给出一个m * n的矩阵a，矩阵元素ai,j小于1000，进行q次查询，每次查询给出子矩阵的4个边界（上下左右），求该子矩阵所有元素之和。
样例中第一个查询：1 3 1 2 表示从第1行到第3行，从第1列到第2列，对应的子矩阵是：
1 2
5 6
9 10求和等于33
Input
第一行2个整数n, m，中间用空格分割，分别对应数组的行数n、列数m(1 <= m,n <= 100) 接下来n行，每行m个整数表示矩阵的内容ai,j 。(0 <= ai,j <= 1000) 接下来1行，一个数q，对应查询的数量。(1 <= q <= 1000) 接下来q行，每行4个整数，对应矩阵的上下左右边界u,d,l,r。(1 <= u <= d <= n, 1 <= l <= r <= m)
Output
输出共q行，对应q个询问的求和结果。
Sample Input
3 4
1 2 3 4
5 6 7 8
9 10 11 12
3
1 3 1 2
1 2 1 3
1 3 1 3
Sample Output
33
24
54
/*-------------B - 子矩阵求和---------------*/
#include<iostream>
using namespace std;
int main() {
int h, l;
int sic[105][105];
int ans[105][105] = { 0 };
int s, x, z, y;
int q, all = 0;
cin >> h >> l;
for (int i = 0; i < h; i++) {
for (int j = 0; j < l; j++) {
cin >> sic[i][j];
ans[i][j + 1] += sic[i][j] + ans[i][j];
}
}
cin >> q;
while (q--) {
cin >> s >> x >> z >> y;
all = 0;
for (int i = s - 1; i < x; i++) {
all += (ans[i][y] - ans[i][z - 1]);
}
cout << all << '\n';
}
return 0;
}C - 天上的星星
在一个星光摧残的夜晚，蒜头君一颗一颗的数这天上的星星。
蒜头君给在天上巧妙的画了一个直角坐标系，让所有的星星都分布在第一象。天上有 n 颗星星，他能知道每一颗星星的坐标和亮度。现在，蒜头君问自己 q 次，每次他问自己每个矩形区域的星星的亮度和是多少（包含边界上的星星）。
输入格式
第一行输入一个整数
n(1≤n≤50000)表示星星的数量。
接下里 n 行，每行输入三个整数 x,y,w(0≤x,y,w≤2000)，表示在坐标 (x,y) 有一颗亮度为 w 的星星。注意一个点可能有多个星星。请在这里输入引用内容接下来一行输入一个整数 q(1≤q≤50000)，表示查询的次数。
接下来 q 行，每行输入四个整数 x1,y1,x2,y2，其中 (x1,y1) 表示查询的矩形的左下角的坐标，(x2,y2) 表示查询的矩形的右上角的坐标，0≤x1≤x2≤2000，0≤y1≤y2≤2000。输出格式
对于每一次查询，输出一行一个整数，表示查询的矩形区域内的星星的亮度总和。Sample Input
5
5 0 6
7 9 7
8 6 13
9 7 1
3 0 19
4
0 8 7 9
0 0 7 10
2 7 10 9
5 4 7 5
Sample Output
7
32
8
0
/*-------------C - 天上的星星---------------*/
#include<iostream>
using namespace std;
int sic[2005][2005] = { 0 }, ans[2005][2005] = { 0 };
int main() {
int n, m;
int x, y, w;
int x1, x2, y1, y2;
int a = 0, b = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x >> y >> w;
if (x > a)
a = x;
if (y > b)
b = y;
sic[x][y] += w;//可重复，先累加
}
for (int i = 0; i <= a; i++) {
for (int j = 0; j <= 2000; j++) {
ans[i][j + 1] = ans[i][j] + sic[i][j];//求前缀和
}
}
cin >> m;
while (m--) {
int all = 0;
cin >> x1 >> y1 >> x2 >> y2;
for (int i = x1; i <= x2; i++) {
all = (ans[i][y2 + 1] - ans[i][y1]) + all;
}
cout << all << endl;
}
return 0;
}D - Color the ball
N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？
Input
每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。
当N = 0，输入结束。
Output
每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。
Sample Input
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
Sample Output
1 1 1
3 2 1
/*-------------D - Color the ball---------------*/
#include<iostream>
using namespace std;
int main() {
int n;
int a, b;
while (scanf("%d", &n) != EOF) {
int sic[100010] = { 0 };
if (n == 0)
break;
for (int j = 0; j < n; j++) {
cin >> a >> b;
sic[a]++;
sic[b + 1]--;
}
for (int i = 1; i <= n; i++){
sic[i] += sic[i - 1];
cout << sic[i];
if (i != n)
cout << ' ';
}
cout << '\n';
}
return 0;
}E - Covered Points Count
You are given n segments on a coordinate line; each endpoint of every segment has integer coordinates. Some segments can degenerate to points. Segments can intersect with each other, be nested in each other or even coincide.
Your task is the following: for every k∈[1..n], calculate the number of points with integer coordinates such that the number of segments that cover these points equals k. A segment with endpoints li and ri covers point x if and only if li≤x≤ri.
Input
The first line of the input contains one integer n (1≤n≤2⋅105) — the number of segments.The next n lines contain segments. The i-th line contains a pair of integers li,ri (0≤li≤ri≤1018) — the endpoints of the i-th segment.
Output
Print n space separated integers cnt1,cnt2,…,cntn, where cnti is equal to the number of points such that the number of segments that cover these points equals to i.Examples
Input
3
0 3
1 3
3 8
Output
6 2 1
Input
3
1 3
2 4
5 7
Output
5 2 0
Note
The picture describing the first example:Points with coordinates [0,4,5,6,7,8] are covered by one segment, points [1,2] are covered by two segments and point [3] is covered by three segments.
The picture describing the second example:
Points [1,4,5,6,7] are covered by one segment, points [2,3] are covered by two segments and there are no points covered by three segments.
/*-------------E - Covered Points Count---------------*/
#include<iostream>
#include<map>
typedef long long ll;
using namespace std;
ll sic[200050];
map<ll, int>mp;
int main() {
int n;
ll a, b;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a >> b;
mp[a+1]++;
mp[b + 2]--;
}
ll r = mp[0];
int ans = 0;
for (auto i = mp.begin(); i != mp.end(); i++){
sic[ans] += i->first - r;//上次结束位置到本次位置每个覆盖一个线段
r = i->first;//更新结束位置
ans += i->second;//覆盖线段数量
}
for (int i = 1; i <= n; i++) {
cout << sic[i];
if (i != n)
cout << ' ';
}
return 0;
}
京公网安备 11010502036488号