单调栈题单¶

练习 #1 [COCI2010-2011#3] DIFERENCIJA¶

题目描述

给出一个长度为 \(n\) 的序列 \(a_i\)，求出下列式子的值：

\(\sum_{i=1}^{n} \sum_{j=i}^{n} (\max_{i\le k\le j} a_k-\min_{i\le k\le j} a_k)\)

即定义一个子序列的权值为序列内最大值与最小值的差。求出所有连续子序列的权值和。

考虑维护f,g分别表示\(1\sim i\)中所有后缀的min之和，max之和。那么每次以i为后缀的答案就是g-f。

g,f可以使用单调栈维护后缀min,max顺便维护。

// Problem: P6503 [COCI2010-2011#3] DIFERENCIJA
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6503
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)


#include<bits/stdc++.h>

using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long 
#define itn int

int read(){
    int x;
    cin>>x;
    return x;
}
const int N=3e5+5;
const ull P=137;

/*

策略

我们考虑当前维护了一段前缀的后缀max和min

*/

int a[N];
int mx[N],topmx;
int mn[N],topmn;
signed main(){
    int n=rd;
    for(int i=1;i<=n;i++){
        a[i]=rd;
    }

    int ans=0;
    int f=0,g=0;//f:1~i的所有后缀的min之和

    for(int i=1;i<=n;i++){
        while(topmx&&a[mx[topmx]]<=a[i]){
            g-=a[mx[topmx]]*(mx[topmx]-mx[topmx-1]);
            topmx--;
        }
        while(topmn&&a[mn[topmn]]>a[i]){
            f-=a[mn[topmn]]*(mn[topmn]-mn[topmn-1]);
            topmn--;
        }

        f+=a[i]*(i-mn[topmn]);
        g+=a[i]*(i-mx[topmx]);
        mn[++topmn]=i;
        mx[++topmx]=i;
        ans+=g-f;
    }
    cout<<ans<<endl;
}

练习 #2 有重数单调栈 [COI2007] Patrik 音乐会的等待¶

题目描述

\(n\) 个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。

队列中任意两个人 \(a\) 和 \(b\)，如果他们是相邻或他们之间没有人比 \(a\) 或 \(b\) 高，那么他们是可以互相看得见的。

写一个程序计算出有多少对人可以互相看见。

输入格式

输入的第一行包含一个整数 \(n\)，表示队伍中共有 \(n\) 个人。

接下来的 \(n\) 行中，每行包含一个整数，表示人的高度，以毫微米(等于 \(10^{-9}\) 米)为单位，这些高度分别表示队伍中人的身高。

输出格式

输出仅有一行，包含一个数 \(s\)，表示队伍中共有 \(s\) 对人可以互相看见。

注意下重复数字的累加，以及边界不要多加了。

// Problem: P1823 [COI2007] Patrik 音乐会的等待
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1823
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
// 
#include<bits/stdc++.h>

using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long 
#define pb push_back
#define itn int
#define ps second 
#define pf first


#define rd read()
int read()
{
  int xx = 0, ff = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9')
  {
    if (ch == '-')
      ff = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    xx = xx * 10 + (ch - '0'), ch = getchar();
  return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
    cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
    for (auto v: a) cerr << v << ' ';
    err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
    cerr << a << ' ';
    err(x...);
}
#else
#define dbg(...)
#endif
const int N=5e5+5;
const ull P=137;
const int INF=1e18+7;
/*

策略


*/  


int a[N],top;
pair<int,int> stk[N];

signed main(){
    int n=rd;
    for(int i=1;i<=n;i++){
        a[i]=rd;
    }


    int ans=0;
    for(int i=1;i<=n;i++){
        //答案记载后面的人头上
        int cnt=0;
        while(top&&a[stk[top].pf]<=a[i]){
            if(a[stk[top].pf]==a[i])cnt+=stk[top].ps;
            ans+=stk[top].ps;
            top--;
        }
        if(top)ans++;// not +stk[top].ps
        stk[++top]={i,cnt+1};
        // cdbg(i,ans,cnt+1);
    }

    cout<<ans<<endl;
}

// 4 2