The use of simple monotonic stack
Niuke’s one-stop solution is the best barrier
Question: There are n mountains with a height of ai. The soldiers on the mountain can supervise each other if and only if max(ai + 1…aj-1)
Calculate optimal barrier placement and maximum defensive force reduction
n≤50000
Idea: The placement of the barrier will divide the large interval into two independent intervals on the left and right, and know the value of the large interval
At the point where the enumeration barrier is placed, the key is to have two independent intervals on the left and right with preprocessing
Use the stack to process the left and right intervals, which are divided into two types: looking from back to front and looking from front to back.
Processing, adding a number, the logarithm can be generated by a monotonically decreasing interval smaller than the previous one
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define endl '\
'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ms(x,y) memset(x,y,sizeof x);
#define YES cout<<"YES"<<'\
';
#define NO cout<<"NO"<<'\
';
#define fr(i,z,n) for(int i = z;i <= n; i + + )
#define ufr(i,n,z) for(int i = n;i >= z; i--)
typedef long long ll;
const ll maxn=2e5 + 10,inf = 1e18;
const ll mod = 1e9 + 7;
using namespace std;
int a[maxn];
int v1[maxn]; //Record from back to front
int v2[maxn]; //Look from front to back
stack<int>s;
signed main()
{
int t;
scanf("%d", & amp;t);
for (int Case = 1; Case <= t; Case + + ) {
memset(v1, 0, sizeof(v1));
memset(v2, 0, sizeof(v2));
while (!s.empty()) {
s.pop();
}
int n;
scanf("%d", & amp;n);
fr(i, 1, n) {
scanf("%d", & amp;a[i]);
}
for (int i = 1; i <= n; i + + ) { //Looking from back to front
v1[i] = v1[i - 1];
int t = 0;
while (!s.empty() & amp; & amp; s.top() < a[i]) {
s.pop();
t + + ;
}
if (!s.empty()) v1[i] + = t + 1;
else v1[i] + = t;
s.push(a[i]);
}
while (!s.empty()) {
s.pop();
}
for (int i = n; i >= 1; i--) { //Look from front to back
v2[i] = v2[i + 1];
int t = 0;
while (!s.empty() & amp; & amp; s.top() < a[i]) {
s.pop();
t + + ;
}
if (!s.empty()) v2[i] + = t + 1;
else v2[i] + = t;
s.push(a[i]);
}
int ans = 0, id = 0;
fr(i, 1, n) {
int x = v1[n] - (v1[i] + v2[i + 1]);
if (x > ans) {
ans = x;
id = i;
}
}
id + = 1;
//Case #1: 2 2
cout << "Case #" << Case << ": " << id << ' ' << ans << '\
';
}
}
Suspension method—maximum submatrix
HISTOGRA – Largest Rectangle in a Histogram
There are n rectangles with width 1 on a horizontal line. Find the area of the largest subrectangle contained in these rectangles.
Time complexity O(n)
#include <algorithm>
#include <cstdio>
using std::max;
const int N = 100010;
int n, a[N];
int l[N], r[N]; //l[i] represents the position where a[i] can expand to the left, r[i] represents the position where a[i] can expand to the right
long long ans;
int main() {
while (scanf("%d", & amp;n) != EOF & amp; & amp; n) {
ans = 0;
for (int i = 1; i <= n; i + + ) scanf("%d", & amp;a[i]), l[i] = r[i] = i;
for (int i = 1; i <= n; i + + )
while (l[i] > 1 & amp; & amp; a[i] <= a[l[i] - 1]) l[i] = l[l[i] - 1];
for (int i = n; i >= 1; i--)
while (r[i] < n & amp; & amp; a[i] <= a[r[i] + 1]) r[i] = r[r[i] + 1];
for (int i = 1; i <= n; i + + )
ans = max(ans, (long long)(r[i] - l[i] + 1) * a[i]);
printf("%lld\
", ans);
}
return 0;
}
P4147 Jade Toad Palace
Given a n*m matrix, each cell is F or R, find the largest rectangular land full of F, and output the area*3
n<=m<=1000
Idea: Same as HISTOGRA – Largest Rectangle in a Histogram, expand the position of each row upward as the length of the suspension line
Time complexity O(n*m)
#include <algorithm>
#include <cstdio>
#include<iostream>
using namespace std;
int m, n, a[1010], l[1010], r[1010], ans;
int main() {
cin >> n >> m;
int ans = 0;
for (int i = 1; i <= n; i + + ) {
for (int j = 1; j <= m; j + + ) {
l[j] = r[j] = j;
}
char s;
for (int j = 1; j <= m; j + + ) {
cin >> s;
if (s == 'F') {
a[j] + + ;
}
else {
a[j] = 0;
}
}
for (int j = 1; j <= m; j + + ) {
while (l[j] > 1 & amp; & amp; a[j] <= a[l[j] - 1])l[j] = l[l[j] - 1];
}
for (int j = m; j >=1; j--) {
while (r[j] < m & amp; & amp; a[j] <= a[r[j] + 1]) r[j] = r[r[j] + 1];
}
for (int j = 1; j <= m; j + + ) {
ans = max(ans, a[j] * (r[j] - l[j] + 1));
}
}
cout << 3*ans << '\
';
}
Luogu
Feel Good Feel Good
Given a positive integer n and a sequence a of length n, we are required to find a subinterval [l, r],
Maximize the sum of numbers in this subrange multiplied by the smallest value in the subrange. Output the maximum value and the two endpoints of the interval
Minimize the interval length if the answers are equal, and minimize the left endpoint number if the length is minimized.
Idea: Find the left and right expansion of each node, and use the prefix sum to find the answer
#include <cstdio>
#include <cstring>
const int N = 100010;
int n, a[N], l[N], r[N];
long long sum[N];
long long ans;
int ansl, ansr;
bool fir = 1;
int main() {
while (scanf("%d", & amp;n) != EOF) {
memset(a, -1, sizeof(a));
if (!fir)
printf("\
");
else
fir = 0;
ans = 0;
ansl = ansr = 1;
for (int i = 1; i <= n; i + + ) {
scanf("%d", & amp;a[i]);
sum[i] = sum[i - 1] + a[i];
l[i] = r[i] = i;
}
for (int i = 1; i <= n; i + + )
while (a[l[i] - 1] >= a[i]) l[i] = l[l[i] - 1];
for (int i = n; i >= 1; i--)
while (a[r[i] + 1] >= a[i]) r[i] = r[r[i] + 1];
for (int i = 1; i <= n; i + + ) {
long long x = a[i] * (sum[r[i]] - sum[l[i] - 1]);
if (ans < x || (ans == x & amp; & amp; ansr - ansl > r[i] - l[i]))
ans = x, ansl = l[i], ansr = r[i];
}
printf("%lld\
%d %d\
", ans, ansl, ansr);
}
return 0;
}
Divisible chunks (regular + chunk boundaries)
1.f(n)=sum of n/i (1<=i<=n)
Taking l as the left boundary, k=n/l, and the right boundary r as the maximum subscript i of k, find the largest i that satisfies i<=n/k
Bring in k,r=n/(n/l)
#include<iostream>
using namespace std;
int main()
{
int ans = 0;
int n;
cin >> n;
for (int l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
cout << l << ' ' << r << '\
';
ans + = (n / l) * (r - l + 1);
}
cout << ans << '\
';
return 0;
}
P1403 [AHOI2005] Research on divisors
f(n) represents the number of divisors of n
Find the sum of f(i) (1<=i<=n)
Idea: The properties of divisors satisfy that the number of occurrences of each positive divisor i in 1~n is n/i
Directly apply the integer division board
#include<iostream>
using namespace std;
int main()
{
int ans = 0;
int n;
cin >> n;
for (int l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
//cout << l << ' ' << r << '\
';
ans + = (n / l) * (r - l + 1);
}
cout << ans << '\
';
return 0;
}
P2424 Sum of divisors
f(x) represents the sum of all divisors of x, find f(x) + f(x + 1)… + f(y)
Idea: The properties of divisors satisfy that the number of occurrences of each positive divisor i in 1~n is n/i, so the contribution of the divisors to the sum is i*n/i
In the interval [l, r], if n/i is a constant, find the arithmetic sequence
ans=cal(y)-cla(x-1)
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
int a[1000];
int cal(int n) {
int res = 0;
for (int l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
//res + = (n / l) * (r - l + 1) / 2;
res + = (n / l) * (l + r) * (r - l + 1) / 2;
}
return res;
}
signed main()
{
int x, y;
cin >> x >> y;
cout << cal(y) - cal(x - 1) << '\
';
return 0;
}
P2261 [CQOI2007] Sum of remainders
Given n,k, calculate the sum of k%i and find (1<=i<=n)
n,k<=1e9
Idea: for a%b -> a-b*(a/b)
k%i ->k-i*(k/i)
sum of ans=k-i*(k/i) (1<=i<=n)
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
signed main()
{
int n, k;
cin >> n >> k;
int ans = n*k;
for (int l = 1, r; l <= n; l = r + 1) {
if (k / l != 0) //Prevent re
r = min(k / (k / l), n);
else
r = n;
ans -= (k / l) * (l + r) * (r - l + 1) / 2;
}
cout << ans << '\
';
return 0;
}