简单单调栈的运用，悬线法

单调栈的运用，悬线法"/>

简单单调栈的运用，悬线法

简单单调栈的运用

牛客一站到底 最优屏障
题意：有n座山，高度位ai,山上的士兵能相互监督当且仅当max(ai+1...aj-1)<min(ai,aj)
M国的防守能力大小为相互监视的哨兵对数,H国家可以放一块巨大屏障在某山前，以便最大消弱M方式能力
计算最优的屏障放置位置和最大的防守力减少量
 n≤50000
思路：屏障的放置将大区间分为左右两个独立区间，知道大区间的的值
在枚举屏障放置点，关键在与预处理左右两个独立区间
用栈处理左右区间，分为从后往前看，从前往后看两种
处理，添加一个数进来，能产生对数的是前面比之小的单调递减区间
 

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<math.h>
#include<map>
#include<vector>
#include<stack>
#define endl '\n'
#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"<<'\n';
#define NO  cout<<"NO"<<'\n';
#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];             //记录从后往前看
int v2[maxn];                     //从前往后看
stack<int>s;signed main()
{int t;scanf("%d", &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", &n);fr(i, 1, n) {scanf("%d", &a[i]);}for (int i = 1; i <= n; i++) {                 //从后往前看v1[i] = v1[i - 1];int t = 0;while (!s.empty() && 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--) {              //从前往后看v2[i] = v2[i + 1];int t = 0;while (!s.empty() && 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 2cout << "Case #" << Case << ": " << id << ' ' << ans << '\n';}
}

悬线法---最大子矩阵

HISTOGRA - Largest Rectangle in a Histogram
在一条水平线上有 n 个宽为1 的矩形，求包含于这些矩形的最大子矩形面积、
时间复杂度O(n)

#include <algorithm>
#include <cstdio>
using std::max;
const int N = 100010;
int n, a[N];
int l[N], r[N];         //l[i]表示a[i]向左能扩展到的位置，r[i]表示向右能扩展到的位置
long long ans;int main() {while (scanf("%d", &n) != EOF && n) {ans = 0;for (int i = 1; i <= n; i++) scanf("%d", &a[i]), l[i] = r[i] = i;for (int i = 1; i <= n; i++)while (l[i] > 1 && a[i] <= a[l[i] - 1]) l[i] = l[l[i] - 1];for (int i = n; i >= 1; i--)while (r[i] < n && 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\n", ans);}return 0;
}

P4147 玉蟾宫
给定n*m的矩阵，每一格为F或R,找到最大的全为F的矩形土地，输出面积*3
n<=m<=1000
思路:同HISTOGRA - Largest Rectangle in a Histogram，将每一行的位置向上扩展作为悬线长度
时间复杂度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 && a[j] <= a[l[j] - 1])l[j] = l[l[j] - 1];}for (int j = m; j >=1; j--) {while (r[j] < m && 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 << '\n';
}

洛谷
感觉不错 Feel Good
给出正整数n 和一个长度为n 的数列a，要求找出一个子区间[l, r]，
使这个子区间的数字和乘上子区间中的最小值最大。输出这个最大值与区间的两个端点
在答案相等的情况下最小化区间长度，最小化长度的情况下最小化左端点序号。
思路：寻找每一个结点的左右扩展，利用前缀和求出答案

#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", &n) != EOF) {memset(a, -1, sizeof(a));if (!fir)printf("\n");elsefir = 0;ans = 0;ansl = ansr = 1;for (int i = 1; i <= n; i++) {scanf("%d", &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 && ansr - ansl > r[i] - l[i]))ans = x, ansl = l[i], ansr = r[i];}printf("%lld\n%d %d\n", ans, ansl, ansr);}return 0;
}

整除分块（规律+分块边界）

1.f(n)=n/i的和 (1<=i<=n) 
以l为左边界，k=n/l, 右边界r为k的最大下标i,找到最大的i满足i<=n/k
带入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 << '\n';ans += (n / l) * (r - l + 1);}cout << ans << '\n';return 0;
}

P1403 [AHOI2005] 约数研究
f(n)表示n的约数的个数
求f(i)的和  (1<=i<=n)
思路：约数的性质满足每个正约数i在1~n中出现的个为n/i
直接套用整除分块板子

#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 << '\n';ans += (n / l) * (r - l + 1);}cout << ans << '\n';return 0;
}

P2424 约数和
f(x)表示x的所有约数和，求f(x)+f(x+1)...+f(y)
思路：约数的性质满足每个正约数i在1~n中出现的个为n/i,于是约数对总和的贡献为i*n/i
在区间[l,r]满足n/i为常数，等差数列求出
 

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) << '\n';return 0;
}
P2261 [CQOI2007] 余数求和
给定n,k，计算k%i的和，求(1<=i<=n)
n,k<=1e9
思路：对于a%b  -> a-b*(a/b)
k%i ->k-i*(k/i)
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)                        //防止rer = min(k / (k / l), n);elser = n;ans -= (k / l) * (l + r) * (r - l + 1) / 2;}cout << ans << '\n';return 0;
}