min(max, max) = max + max - max

Little_corn · 2025-11-05 15:21:42 · 个人记录

P10764 [BalticOI 2024] Wall

无脑做法。

下文称一个位置的水位为水的高度 + 柱子的高度。

令最后的序列为 h=(h_1, h_2, ..., h_n)，则一个位置的水位 ht_i = \min(\max_{j = 1}^i h_i, \max_{j = i}^n h_i)。\min 套 \max 不好做，直接换成 \max_{j = 1}^i h_i + \max_{j = i}^n h_i - \max_{i = 1}^n h_i，然后拆贡献，后面部分的贡献是容易算的，考虑前面的两个问题。前缀 \max 和后缀 \max 的问题是对称的。

现在的问题变成如何计算所有序列的前缀 \max 的和。直接 dp，设 f_{i, j} 为考虑前 i 个位置，此时的前缀 \max = j 的方案数，不妨设 a_i < b_i，则转移相当于：

• f_{i - 1, [0, a_i - 1]} \to f_{i, a_i}
• \forall a_i \le j < b_i, f_{i - 1, j} \to f_{i, j}

使用线段树即可 1log。

:::info[code]

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pir pair<ll, ll> 
#define mkpir make_pair
#define umap unordered_map
#define pb emplace_back
#define fi first
#define se second
#define db double
using namespace std;

const int N = 1e6 + 10, M = 2e5 + 10;
const ll INF = 1e18, mod = 1e9 + 7;
const db eps = 1e-9;

/*
struct edge{
  int v, next;
}edges[M << 1];
int head[N], idx;

il void add_edge(int u, int v){
  edges[++idx] = {v, head[u]};
  head[u] = idx;
}
*/

il void chkmax(ll& x, ll y){if(x < y) x = y;}
il void chkmin(ll& x, ll y){if(x > y) x = y;}
il void chkmax(int& x, int y){if(x < y) x = y;}
il void chkmin(int& x, int y){if(x > y) x = y;}
il void ADD(ll& x, ll y){x += y; ((x >= mod) ? x -= mod : 0ll);}
il void MUL(ll& x, ll y){x = x * y % mod;}

il ll qpow(ll x, int y){
  ll ret = 1;
  for(; y; y >>= 1, MUL(x, x)) if(y & 1) MUL(ret, x);
  return ret;
}
//#define int long long

int n, a[N], b[N], rk[N], V;
ll pw2[N];

struct Segtree{
  #define ls (o << 1)
  #define rs (o << 1 | 1)
  #define mid ((l + r) >> 1)
  ll sum[N << 2], ad[N << 2], mul[N << 2], val[N << 2], ANS[N << 2];
  void pushup(int o){
    sum[o] = (sum[ls] + sum[rs]) % mod;
    val[o] = (val[ls] + val[rs]) % mod;
    ANS[o] = (ANS[ls] + ANS[rs]) % mod;
  }
  void addtagA(int o, int l, int r, ll v){ADD(ad[o], v); ADD(sum[o], (r - l + 1) * v % mod); ADD(ANS[o], (r - l + 1) * v % mod * val[o] % mod);}
  void addtagM(int o, ll v){MUL(ad[o], v); MUL(mul[o], v); MUL(sum[o], v); MUL(ANS[o], v);}
  void pushdown(int o, int l, int r){
    if(mul[o] != 1) addtagM(ls, mul[o]), addtagM(rs, mul[o]), mul[o] = 1;
    if(ad[o]) addtagA(ls, l, mid, ad[o]), addtagA(rs, mid + 1, r, ad[o]), ad[o] = 0;
  }
  void build(int o, int l, int r){
    mul[o] = 1; ad[o] = ANS[o] = 0;
    if(l == r) return sum[o] = (!l), val[o] = rk[l], void();
    build(ls, l, mid); build(rs, mid + 1, r);
    pushup(o);
  }
  void Segadd(int o, int l, int r, int s, int t, ll v){
    if(s > t) return;
    if(s <= l && r <= t) return addtagA(o, l, r, v);
    pushdown(o, l, r);
    if(s <= mid) Segadd(ls, l, mid, s, t, v);
    if(mid < t) Segadd(rs, mid + 1, r, s, t, v);
    pushup(o);
  }
  void Segmul(int o, int l, int r, int s, int t, ll v){
    if(s > t) return;
    if(s <= l && r <= t) return addtagM(o, v);
    pushdown(o, l, r);
    if(s <= mid) Segmul(ls, l, mid, s, t, v);
    if(mid < t) Segmul(rs, mid + 1, r, s, t, v);
    pushup(o);
  }
  ll getsum(int o, int l, int r, int s, int t){
    if(s > t) return 0ll;
    if(s <= l && r <= t) return sum[o];
    pushdown(o, l, r); ll ret = 0;
    if(s <= mid) ADD(ret, getsum(ls, l, mid, s, t));
    if(mid < t) ADD(ret, getsum(rs, mid + 1, r, s, t));
    return ret;
  }
}tr;

ll solve(){
  tr.build(1, 0, V); ll ret = 0;
  for(int i = 1; i <= n; i++){
    ll sa = tr.getsum(1, 0, V, 0, a[i] - 1), sb = tr.getsum(1, 0, V, 0, b[i] - 1);
    tr.Segmul(1, 0, V, 0, a[i] - 1, 0ll); tr.Segmul(1, 0, V, b[i], V, 2ll);
    tr.Segadd(1, 0, V, a[i], a[i], sa); tr.Segadd(1, 0, V, b[i], b[i], sb);
    ADD(ret, pw2[n - i] * tr.ANS[1] % mod); 
  } return ret;
}

void clr(){

}

int cnt0[N], cnt1[N];

signed main(){
  //freopen("wall.in", "r", stdin);
  //freopen("wall.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  cin >> n; pw2[0] = 1;
  for(int i = 1; i <= n; i++) pw2[i] = pw2[i - 1] * 2ll % mod;
  for(int i = 1; i <= n; i++) cin >> a[i], rk[i] = a[i];
  for(int i = 1; i <= n; i++) cin >> b[i], rk[i + n] = b[i];
  sort(rk + 1, rk + 2 * n + 1); V = unique(rk + 1, rk + 2 * n + 1) - (rk + 1);
  for(int i = 1; i <= n; i++) a[i] = lower_bound(rk + 1, rk + V + 1, a[i]) - rk, b[i] = lower_bound(rk + 1, rk + V + 1, b[i]) - rk;
  for(int i = 1; i <= n; i++) if(a[i] > b[i]) swap(a[i], b[i]);
  for(int i = 1; i <= n; i++) cnt0[a[i]]++, cnt1[b[i]]++;
  ll ans = 0, res = 1, lst = 0;
  for(int i = 1; i <= n; i++) ADD(ans, pw2[n - 1] * (rk[a[i]] + rk[b[i]]) % mod);
  int cnt = 0;
  for(int i = 1; i <= V; i++){
    cnt += cnt0[i]; MUL(res, pw2[cnt1[i]]); 
    ll rel = res * (cnt == n); 
    ADD(ans, (rel - lst + mod) * rk[i] % mod * n % mod); lst = rel; 
  }
  ans = mod - ans; 
  ADD(ans, solve()); reverse(a + 1, a + n + 1); reverse(b + 1, b + n + 1);
  ADD(ans, solve()); cout << ans;

  return 0;
}