【Week5 作业】A - 最大矩形、B - TT's Magic Cat、C - 平衡字符串、D - 滑动窗口

A - 最大矩形

题意：

给一个直方图，求直方图中的最大矩形的面积。例如，下面这个图片中直方图的高度从左到右分别是2, 1, 4, 5, 1, 3, 3, 他们的宽都是1，其中最大的矩形是阴影部分。

Input

输入包含多组数据。每组数据用一个整数n来表示直方图中小矩形的个数，你可以假定1 <= n <= 100000. 然后接下来n个整数h1, …, hn, 满足 0 <= hi <= 1000000000. 这些数字表示直方图中从左到右每个小矩形的高度，每个小矩形的宽度为1。 测试数据以0结尾。

Output

对于每组测试数据输出一行一个整数表示答案。

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8
4000

思路做法：

为求最大矩形面积，可以对于每个直方图，确定它的可以到达的最左的左端点和最右的右端点，循环更新$ans$ans值。
用单调栈确定端点。首先定义结构体$R$R，包含索引$index$index，左端点$l$l初始为0，右端点$r$r初始为$n-1$n−1，和高$h$h。
维护一个数组$stack$stack作为栈，把数组$a$a中所有的元素尝试放栈中，当栈空或栈顶元素的高$h$h低于等于当前$a[i].h$a[i].h时入栈，当栈顶元素的高$h$h高于当前$a[i].h$a[i].h时，说明栈顶元素的右端点出现了，更新右端点的值并出栈，若最后也没有出栈则右端点即为初始值$n-1$n−1。
同理，清空栈后（栈顶指针$top=0$top=0）反着放一边即可确定每个左端点。循环计算矩形面积$(h*(r-l+1))$(h∗(r−l+1))并更新ans值。

总结:

单调栈的思路要清晰，知道要算的是什么。WA的原因是初始定义都是int类型，但面积可能超，所以改为long long类型就可以了。

代码:

#include <stdio.h>

const int N = 100100;
struct R{
	int index, l, r;
	long long h;
}a[N], stack[N];

int main(){
	int n;
	while(scanf("%d", &n)){
		if(n == 0) break;
		int top = 0;
		long long ans = 0;
		for(int i = 0; i < n; ++i){
			scanf("%lld", &a[i].h);
			a[i].l = 0;
			a[i].r = n-1;
			a[i].index = i;
		}
		for(int i = 0; i < n; ++i){
			while(top > 0 && stack[top].h > a[i].h){
				a[stack[top--].index].r = i-1;
			}
			stack[++top] = a[i];
		}
		top = 0;
		for(int i = n-1; i >= 0; --i){
			while(top > 0 && stack[top].h > a[i].h){
				a[stack[top--].index].l = i+1;
			}
			stack[++top] = a[i];
		}
		for(int i = 0; i < n; ++i){
//			printf("%d %d\n", a[i].l, a[i].r);
			long long v = a[i].h*(a[i].r-a[i].l+1);
			if(v > ans) ans = v;
		}
		printf("%lld\n", ans);
	}
	return 0;
} 

B - TT’s Magic Cat

题意：

Thanks to everyone’s help last week, TT finally got a cute cat. But what TT didn’t expect is that this is a magic cat.

One day, the magic cat decided to investigate TT’s ability by giving a problem to him. That is select n cities from the world map, and $a[i]$a[i] represents the asset value owned by the $i$i-th city.

Then the magic cat will perform several operations. Each turn is to choose the city in the interval $[l,r]$[l,r] and increase their asset value by $c$c. And finally, it is required to give the asset value of each city after $q$q operations.

Could you help TT find the answer?

Input

The first line contains two integers n,q ($1≤n,q≤2⋅10^5$1≤n,q≤2⋅105) — the number of cities and operations.

The second line contains elements of the sequence a: integer numbers $a1,a2,...,an (−10^6≤ai≤10^6)$a1,a2,...,an(−106≤ai≤106).

Then q lines follow, each line represents an operation. The $i$i-th line contains three integers $l,r$l,r and $c (1≤l≤r≤n,−10^5≤c≤10^5)$c(1≤l≤r≤n,−105≤c≤105) for the $i$i-th operation.

Output

Print $n$n integers $a1,a2,…,an$a1,a2,…,an one per line, and ai should be equal to the final asset value of the $i$i-th city.

Sample Input

4 2
-3 6 8 4
4 4 -2
3 3 1

2 1
5 -2
1 2 4

1 2
0
1 1 -8
1 1 -6

Sample Output

-3 6 9 2

9 2

-14

思路做法：

直接便历是$O(nq)$O(nq)的复杂度，可能超时，因此用差分构造方式，每次区间修改只需2个值修改。
令$b[i] = a[i] - a[i-1]$b[i]=a[i]−a[i−1]，那么$a[i] = a[i-1] + b[i]$a[i]=a[i−1]+b[i]，那么$a[L, R]$a[L,R]的整个区间都$+c$+c时，只需$b[L]+c， b[R+1]-c$b[L]+c，b[R+1]−c。这样，在小于$L$L的范围内$a[i]$a[i]不变，在$[L, R]$[L,R]的范围内，由于$a[i]$a[i]都加了$b[L]$b[L]，于是相应的都$+c$+c，而在大于$R$R的范围内，由于$b[R+1]-c$b[R+1]−c，两者抵消，$a[i]$a[i]恢复了没$+c$+c的状态，最后通过更新完的b数组还原出a数组打印出来即可。

总结:

单看每个数的范围和每次更改的范围及更改次数都是int类型，但数据大了后可能超出，因此a数组和b数组都必须是long long类型

代码:

#include <stdio.h>

const int N = 200000+100;
long long a[N], b[N];

int main(){
	int n, q;
	scanf("%d %d", &n, &q);
	scanf("%lld", &a[1]); b[1] = a[1];
	for(int i = 2; i <= n; ++i){  //从1到 n 
		scanf("%lld", &a[i]);
		b[i] = a[i] - a[i-1];  //差分 
	}
	for(int i = 0; i < q; ++i){  //q次操作 
		int l, r, c;
		scanf("%d %d %d", &l, &r, &c);
		b[l] += c;
		b[r+1] -= c;
	}
	a[1] = b[1]; printf("%lld ", a[1]);
	for(int i = 2; i <= n; ++i){
		a[i] = a[i-1] + b[i];
		printf("%lld ", a[i]);
	}
	printf("\n");
	return 0;
}

C - 平衡字符串

题意：

一个长度为 n 的字符串 s，其中仅包含 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符。

如果四种字符在字符串中出现次数均为 n/4，则其为一个平衡字符串。

现可以将 s 中连续的一段子串替换成相同长度的只包含那四个字符的任意字符串，使其变为一个平衡字符串，问替换子串的最小长度?

如果 s 已经平衡则输出0。

Input

一行字符表示给定的字符串s

Output

一个整数表示答案

Sample Input

QWER
QQWE
QQQW
QQQQ

Sample Output

0
1
2
3

Note

$1<=n<=10^5$1<=n<=105

n是4的倍数

字符串中仅包含字符 ‘Q’, ‘W’, ‘E’ 和 ‘R’.

思路做法：

题目要求替换子串的最小长度，可以用尺取法，也可以二分。
为了检测在给定替换子串的情况下s是否平衡，用字符到数值的映射cnt记录替换子串外的每个字符的个数，当$[L, R]$[L,R]改变时，同时维护cnt。
取出cnt中4个字符数量的最大值M，其他字符数量必须向它看齐，所需的空间大小为$((M-cnt['Q'])+(M-cnt['W'])+(M-cnt['E'])+(M-cnt['R']))$((M−cnt[′Q′])+(M−cnt[′W′])+(M−cnt[′E′])+(M−cnt[′R′]))，替换子串的大小为$T = R - L + 1$T=R−L+1，用掉上边的那些空间后，还剩$F$F大小的空间，若$F$F合法即$F>=0$F>=0，并且$F\%4==0$F%4==0即剩余空间可以被数量相等的4个字符继续填充满，那么这个替换子串就可以使$s$s合法.
对于给定的一个替换子串$s[L, R]$s[L,R]，如果替换掉它可以使$s$s平衡，我们就可以尝试一个更小的区间，让$L++$L++，否则$R++$R++，让子串更长一些，更容易使$s$s平衡。直到$R==s.length()$R==s.length()这样可以把$s$s全部便历一遍，找出最短的区间长度。

总结:

初始L，R都为0， 直到R超过数组s的长度，说明之前的替换子串不能使s平衡，但是向右没有更新的空间了，循环结束。若更新后L>R，说明一开始字符串就是平衡的，因此先判断cnt中的4个数字是否相等，不等再用尺取法。

代码:

#include <iostream>
#include <string>
#include <map>
using namespace std;

const int N = 100000+100;
string s;
map<char, int> cnt;

int main(){
	cin >> s;
	int n = s.length(), L = 0, R = 0, ans = n;
	for(int i = 0; i < n; ++i) cnt[s[i]]++;  //计算个数 
	if(!(cnt['Q']==cnt['W']&&cnt['Q']==cnt['E']&&cnt['Q']==cnt['R'])){
		cnt[s[0]]--;
		while(R < n){
//			cout<<cnt['Q']<<' '<<cnt['W']<<' '<<cnt['E']<<' '<<cnt['R']<<endl;
			int M = max(max(cnt['Q'], cnt['W']), max(cnt['E'], cnt['R']));
			int T = R - L + 1;
			int F = T - ((M-cnt['Q'])+(M-cnt['W'])+(M-cnt['E'])+(M-cnt['R']));
//			cout<<"M = "<<M<<" T = "<<T<<" F = "<<F<<endl;
			if(F >= 0 && F % 4 == 0){  //满足条件 
				if(R-L+1 < ans) ans = R-L+1;  //更新 ans
				cnt[s[L++]]++;  //缩短区间 更新 cnt 
			}else cnt[s[++R]]--;  //会不会越界？？ 不会 
		}
	}else ans = 0;
	cout << ans << endl;
	return 0;
}

D - 滑动窗口

题意：

ZJM 有一个长度为 n 的数列和一个大小为 k 的窗口, 窗口可以在数列上来回移动. 现在 ZJM 想知道在窗口从左往右滑的时候，每次窗口内数的最大值和最小值分别是多少. 例如：
数列是 [1 3 -1 -3 5 3 6 7], 其中 k 等于 3.

Input

输入有两行。第一行两个整数n和k分别表示数列的长度和滑动窗口的大小，$1<=k<=n<=1000000$1<=k<=n<=1000000。第二行有$n$n个整数表示ZJM的数列。

Output

输出有两行。第一行输出滑动窗口在从左到右的每个位置时，滑动窗口中的最小值。第二行是最大值。

Sample Input

8 3
1 3 -1 -3 5 3 6 7

Sample Output

-1 -3 -3 -3 3 3
3 3 5 5 6 7

思路做法：

若是暴力求解可能超时，用单调队列求解。
因为数组中的数可能脱离窗口，因此定义结构体$Num$Num，包含索引$index$index和数$num$num，用数组自定义一个$Num$Num类型的单调队列$queue$queue。
首先找区间内的最小值，当数组$a$a中的元素放入队列时先判断队列是否为空，非空然后判断队列的head指针指向的元素的索引是否脱离当前区间，是的话就要$head++$head++，使其出队列，直到没有脱离区间的元素在队列中。同时看$tail$tail指针指向的元素的$num$num值是否大于当前$a[i].num$a[i].num值，因为求最小值，所以大于的话就要$tail--$tail−−，比当前$num$num值都大的元素都出队列后，只剩下小于等于当前$num$num的元素在队列中，$head$head指向的元素即为最小值。
求最大值同理，只是大于改为了小于，$head$head指向的元素自然为最大值。
将每个区间的最小值与最大值记录并打印。

总结:

注意$k$k不同时很多变量都要相应改变，不能面向一组数据编程。另外代码中最值的记录和打印可以同时进行，进而$min$min和$max$max数组就不需要了

代码:

#include <stdio.h>

const int N = 1000000+100;
struct Num{
	int index, num;
}a[N], queue[N]; 
int min[N], max[N], head = 0, tail = -1;

int main(){
	int k, n;
	scanf("%d %d", &n, &k);  //注意k不同时后面的代码改动 
	for(int i = 0; i < n; ++i){
		scanf("%d", &a[i].num);
		a[i].index = i;
	}
	for(int i = 0; i < n; ++i){
		while(head <= tail && i - queue[head].index > k-1) head++;
		while(head <= tail && queue[tail].num > a[i].num) tail--;
		queue[++tail] = a[i];
		if(i >= k-1) min[i-k+1] = queue[head].num;
	}
	head = 0;
	tail = -1;
	for(int i = 0; i < n; ++i){
		while(head <= tail && i - queue[head].index > k-1) head++;
		while(head <= tail && queue[tail].num < a[i].num) tail--;
		queue[++tail] = a[i];
		if(i >= k-1) max[i-k+1] = queue[head].num;
	}
	for(int i = 0; i < n-k+1; ++i) printf("%d ", min[i]);
	printf("\n");
	for(int i = 0; i < n-k+1; ++i) printf("%d ", max[i]);
	printf("\n");
	return 0;
}