Warning！！！！Waring
本期马蜂怪异，请空腹观看
强者从不抱怨环境（bushi
A. 最大的和
时间：1s 空间：256M
题目描述：
输入长度为 n 的数组 A ，求数组 A 中所有长度为 m 的区间里，区间和最大的那个区间的区间和。(数组中可能出现负数)
输入格式：
第一行两个整数 n 和 m
第二行给出 n 个整数，第i个整数代表Ai
1<=n<= 10^5 ，1<=m<=n，-10000<=Ai <=10000
输出格式：
输出一行答案，最大的区间长度为 m 的区间和
样例输入1：
5 3
2 5 -4 10 3
样例输出1：
11
基础题
for(int j=1;j<=m;j++){
ans+=a[j];
}
maxn=max(maxn,ans);
for(int i=2;i<=n;i++){
if(i+m-1<=n){
ans-=a[i-1];
ans+=a[i+m-1];
maxn=max(maxn,ans);
}
}
B. 玉米地
题目描述：
小 Q 买下了一片农场，并在其中种下了 n 行 m 列玉米。
每株玉米的产量各不相同，减掉成本之后有盈有亏。具体而言，第 i 行第 j 列的玉米的收益为 ai,j，若 ai,j<0 则意味着这株玉米亏本了。
现在小 Q 想知道玉米地的收益如何。
小 Q 给了你 q 组询问，每组询问都给出四个数 x1, y1, x2, y2，需要你求出行从 x1 到 x2、列从 y1 到 y2 这个矩形区域内玉米的收益之和。
输入格式：
第一行输入三个正整数 n,m,q。
接下来 n 行，每行 m 个整数，分别表示每一株玉米的收益。
接下来 q 行，每行 4 个整数 x1, y1, x2, y2，含义如上。
输出格式：
输出 q 行，每行一个数，表示所询问的矩形区域内的玉米收益之和。
样例输入：
3 4 2
1 2 3 4
-5 6 -7 8
9 0 -1 -2
1 1 2 3
2 3 3 4
样例输出：
0
-2
数据规模：
对于 100% 的数据，1≤n,m≤3×103，1≤q≤105，-1000≤ai,j≤1000。
差分基础题
for(int i=1;i<=n;i++){
7
for(int j=1;j<=m;j++){
8
scanf("%d",&a);
9
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a;
10
}
11
}
12
while(q--){
13
int x1,y1,x2,y2;
14
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
15
printf("%d\n",sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]);
16
}
C. 街区建设
Problem ID: 8524
Contest ID: 5874
必做题
Accepted
100 分
题目描述：
开发商小 Q 买下了一条街，他想在这条街的一边盖房子。
街道可以抽象为一条数轴，而小 Q 只会在坐标在 1~n 的范围内盖房子。
首先，小 Q 将街上坐标在 1~n 范围内的物体全部铲平。也就是说，在正式动工盖房子之前，1~n 范围内是没有东西的。
小 Q 的盖房子技术出奇的烂，他每次只会在坐标从 l 到 r 的一段区间上砌一堵高为 h 厘米的墙。如果某个位置已经有墙了，那么他会将墙加高 h 厘米。
好吧小 Q 不得不承认自己不会盖房子只会砌墙。
小 Q 已经砌了 m 次墙了，整条街已经乱七八糟的了。
你知道有多乱吗？
输入格式：
第一行输入两个正整数 n,m，分别表示坐标最大范围、操作总数。
接下来 m 行每行输入三个正整数 li, ri, hi，表示小 Q 在坐标从 li 到 ri 这一段区间上砌了一堵高为 hi 厘米的墙。
输出格式：
输出一行 n 个数，分别表示 m 次操作之后街道上坐标从 1 到 n 的位置上墙的高度（单位为厘米）。
样例输入：
5 3 1 3 2 2 3 1 4 4 9
样例输出：
2 3 3 9 0
数据规模：
对于 10% 的数据，m=0；
对于 100% 的数据，1≤n,m≤5×10^5，1≤h≤1000。
d[l]+=h;
d[r+1]-=h;
D. 大哈贴广告
Problem ID: 9891
Contest ID: 5874
必做题
Accepted
100 分
时间：1s 空间：256M
题目描述：
大哈有一面 n * n 的广告墙，他往墙上贴 m 张广告，广告之间有些部分会相互重叠，问墙上的每个点上覆盖了几张广告
输入格式：
第一行两个整数 n 和 m
接下来 m 行 ，每行给出 x1 ，y1 , x2 , y2 ，代表这张广告的左上角是(x1,y1)和右下角是(x2,y2)
1≤n,m≤3000，
1≤x1≤x2≤n，
1≤y1≤y2≤n
输出格式：
输出 n 行，每行 n 个正整数，
第 i 行 第 j 个 表示 (i , j) 这个点被几张广告覆盖
样例输入1：
5 3 2 2 3 3 3 3 5 5 1 2 1 4
样例输出1：
0 1 1 1 0 0 1 1 0 0 0 1 2 1 1 0 0 1 1 1 0 0 1 1 1``
d[x1][yy]++;
9
d[x2+1][y2+1]++;
10
d[x2+1][yy]--;
11
d[x1][y2+1]--;
E. 连续子区间的和
Problem ID: 15648
Contest ID: 5874
必做题
Accepted
100 分
时间：1s 空间：512M
题目描述：
有一个长度为n的不递减数组，给定一个数m，求出其中有多少连续的子区间的和等于m。
题目输入；
输入第一行，一个整数n,一个整数m
第二行，输入n个整数A[1]~A[n];
题目输出：
输出一个整数
样例输入：
5 5 1 2 3 5 6
样例输出：
2
数据范围：
n<=100000
0<= m <= 1e9
0<= A[i] <= 100000;
while (right < n)
17
{
18
sum += a[right];
19
while (sum > m) sum -= a[left ++ ];
20
if (sum == m) res ++ ;
21
right ++ ;
22
}
G. 长度最小的子数组
Problem ID: 8091
Contest ID: 5874
必做题
Accepted
100 分
时间：1s 空间：256M
题目描述：
给定一个含有 n 个整数的数组和一个整数 s ，找出该数组中满足其和 ≥s 的长度最小的连续子数组。
如果不存在符合条件的连续子数组，输出 0。
输入格式：
第一行包含一个整数 T，表示测试数据组数。
对于每组测试数据，
第一行包含两个整数 n, s。
接下来包含 n 个整数 ai
输出格式：
对于每组测试数据，输出一个整数表示答案。
样例1输入：
3 8 7 2 3 1 2 0 4 3 0 8 100 2 3 1 2 0 4 3 0 3 0 1 1 1
样例1输出：
2 0 1
约定与提示：
对于100%的数据，
1≤T≤3⋅105，
1≤n≤3⋅105，
0≤s≤1018，
0≤ai≤109
保证 ∑n≤3⋅105
对于样例1的第一组测试数据：子数组下标是[6,7]，所以答案为 2。
while(sum<s&&j<=n){
13
sum+=a[j];
14
j++;
15
}
16
if(sum>=s) minn=min(minn,j-i);
17
sum-=a[i];
18
}
H. 激光炸弹
Problem ID: 7557
Contest ID: 5874
必做题
Accepted
100 分
时间：1s 空间：256M
题目描述
一种新型的激光炸弹，可以摧毁一个边长为R的正方形内的所有的目标。现在地图上有n(N<=10000)个目标，用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置，每个目标都有一个价值vi。
激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为R的正方形的边必须和x，y轴平行。若目标位于爆破正方形的边上，该目标将不会被摧毁。
输入格式
第一行为正整数n和正整数R，接下来的n行每行有3个正整数，分别表示xi,yi,vi
输出格式
输出文件仅有一个正整数，表示一颗炸弹最多能炸掉地图上总价值为多少的目标（结果不会超过32767）。
样例输入
2 1 0 0 1 1 1 1
样例输出
1
约定
提示
for(int i=1;i<=n;i++)
11
{
12
int x,y,w;
13
cin>>x>>y>>w;
14
x++;
15
y++;
16
sum[x][y]+=w;
17
nx=max(nx,x);
18
ny=max(ny,y);
19
}
20
for(int i=1;i<=nx;i++)
21
for(int j=1;j<=ny;j++)
22
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
23
24
int s=0;
25
for(int i=r;i<=nx;i++)
26
for(int j=r;j<=ny;j++)
27
s=max(s,sum[i][j]-sum[i-r][j]-sum[i][j-r]+sum[i-r][j-r]);
28
cout<<s;
I. 矩阵翻转
Problem ID: 8167
Contest ID: 5874
必做题
Accepted
100 分
题目描述：
读入一个n*m的01矩阵，q次操作，每次将一个子矩阵内的01翻转，求最终的矩阵
输入格式：
第一行三个整数n，m，q
之后n行每行m个整数0或1
之后q行，每行四个整数x1,y1,x2,y2，表示要翻转矩阵的左上角和右下角
输出格式：
输出一个矩阵表示答案
样例输入 1 ：
5 4 1
1 1 0 0
1 0 0 0
0 0 1 1
1 1 1 1
1 0 1 0
2 2 5 3
样例输出 1 ：
1 1 0 0
1 1 1 0
0 1 0 1
1 0 0 1
1 1 0 0
约定：
1 ≤ n,m ≤ 500， q ≤ 1000000
提示：
for(int i=1;i<=n;i++){
19
for(int j=1;j<=m;j++){
20
if(i>1)d[i][j]+=d[i-1][j];
21
if(j>1)d[i][j]+=d[i][j-1];
22
if(i>1&&j>1)d[i][j]-=d[i-1][j-1];
23
a[i][j]^=(d[i][j]&1);
24
printf("%d ",a[i][j]);
25
}
26
printf("\n");
27
}
J. 小李的遗迹之旅
Problem ID: 8526
Contest ID: 5874
选做题
Accepted
100 分
题目描述：
小李是一名探险家，这天，他到了一个古代遗迹当中，但是这个遗迹的大门无法打开，但是这个古代遗迹非常的神奇，在大门上不断的闪过一些古代文字，小李的探险经验非常丰富，找到了一块石碑，石碑上记载了破解大门打开的方法
破解规则如下：
石碑上给出了一些古代文字，那些古代文字其实包含了n个古代词语。大门闪烁的古代文字其实是一篇文章，文章由m个段落构成，每个段落都是1个古代词语。你需要做的是记录这篇文章，在文章中找出连续的一些段落，其中包含最多的出现的石碑上的古代词语（重复的只算一个）。并且在石碑上出现的古代词语数量尽量多的情况下，还要使选出的文章段落尽量短，最终得到两个数字输出石碑，即可打开大门。
输入格式：
第 1 行一个数 n，接下来 n 行每行是一个长度不超过 10 的字符串，表示一个石碑上出现的古代词语。
接着是一个数 m，然后是 m 行长度不超过 10 的字符串，每个表示文章中的一个段落。
输出格式：
输出文件共 2 行。第 1 行为文章中最多包含的石碑上的古代词语，第 2 行表示在文章中包含最多石碑上出现的最短的连续段的长度。
样例1输入：
3 wink cat art 5 wink cat cat art wink
样例1输出：
3 3
样例2输入：
5 aa bb cc dd aa 6 aa z cc cc bb cc
样例2输出：
3 5
数据规模：
对于 100% 的数据，n≤1000，m≤10^5。
样例2解释：
aa,bb,cc都在文章中出现过，所以第一问答案是3
最短的区间是[1,4]，也就是aa,cc,cc,bb，包含aa,bb,cc，所以长度是4-1+1=4
unordered_set<string> se;
7
for (int i = 0; i < n; i++) {
8
string s;
9
cin >> s;
10
se.insert(s);
11
}
12
cin >> m;
13
vector<string> article(m);
14
for (int i = 0; i < m; i++) {
15
cin >> article[i];
16
}
17
int left = 0, right = 0, count = 0, minLen = m + 1, maxCount = 0;
18
unordered_map<string, int> window;
19
while (right < m) {
20
string s = article[right];
21
right++;
22
if (se.count(s)) {
23
window[s]++;
24
if (window[s] == 1) count++;
25
}
26
while (count == se.size()) {
27
if (right - left < minLen) {
28
minLen = right - left;
29
maxCount = count;
30
}
31
string s = article[left];
32
left++;
33
if (se.count(s)) {
34
window[s]--;
35
if (window[s] == 0) count--;
36
}
37
}
38
}
39
cout << maxCount << endl << minLen << endl;