P6503 [COCI2010-2011#3] DIFERENCIJA

moonbowqwq · 2023-07-29 12:04:14 · 题解

题目链接

题意简述

给出一个长度为 n 的序列 a = \{a_1, a_2, \ldots, a_n\}，求其所有子序列的最大值和最小值的差的和。

数据范围与约定：2 \leq n \leq 3 \times 10^5, 1 \leq a_i \leq 10^{18}。

解题思路

显然我们可以把最大值和最小值分别统计，最后把和相减即可，这里我用的是 ST 表。

具体地，假设我们当前所在的区间为 [l, r]，该区间内的最值所在位置为 k (k \in [l, r])，那么所有左端点在 [l, k] 之中且右端点在 [k, r] 之中的子序列其最值都为 a_k，所以 a_k 对答案的贡献就为 (-1)^{[\forall i \in [l, r], a_k \leq a_i]} \times a_k \times (r - k + 1) \times (k - l + 1)，然后我们再递归处理子区间 [l, k - 1] 和 [k + 1, r] 即可，累和后的结果就是答案。

代码实现

#include<bits/stdc++.h>

using namespace std;

int N,A[300005];

class Sparse_Table_Max{
private:
  int max_id[300005][20];
  int log2(int num){
    int res = -1;
    while(num > 0)
      ++res,num >>= 1;
    return res;
  }
  int Max(int a,int b){
    if(A[a] > A[b])
      return a;
    return b;
  }
public:
  void Init(){
    for(int i = 1;i <= N;++i)
      max_id[i][0] = i;
    for(int k = 1;k < 20;++k)
      for(int i = N - (1 << k) + 1;i > 0;--i)
    max_id[i][k] = Max(max_id[i][k - 1],max_id[i + (1 << k - 1)][k - 1]);
    return;
  }
  int Query(int l,int r){
    int k = log2(r - l + 1);
    return Max(max_id[l][k],max_id[r - (1 << k) + 1][k]);
  }
}STX;

class Sparse_Table_Min{
private:
  int min_id[300005][20];
  int log2(int num){
    int res = -1;
    while(num > 0)
      ++res,num >>= 1;
    return res;
  }
  int Min(int a,int b){
    if(A[a] < A[b])
      return a;
    return b;
  }
public:
  void Init(){
    for(int i = 1;i <= N;++i)
      min_id[i][0] = i;
    for(int k = 1;k < 20;++k)
      for(int i = N - (1 << k) + 1;i > 0;--i)
    min_id[i][k] = Min(min_id[i][k - 1],min_id[i + (1 << k - 1)][k - 1]);
    return;
  }
  int Query(int l,int r){
    int k = log2(r - l + 1);
    return Min(min_id[l][k],min_id[r - (1 << k) + 1][k]);
  }
}STN;

__int128 DFS1(int l,int r);
__int128 DFS2(int l,int r);

int main(){
  scanf("%d",&N);
  for(int i = 1;i <= N;++i)
    scanf("%d",&A[i]);
  STN.Init(),STX.Init();
  printf("%lld",(long long)(DFS1(1,N) - DFS2(1,N)));
  return 0;
}

__int128 DFS1(int l,int r){
  if(l > r)
    return 0;
  if(l == r)
    return A[l];
  int mid = STX.Query(l,r);
  return (__int128)(mid - l + 1) * (r - mid + 1) * A[mid] + DFS1(l,mid - 1) + DFS1(mid + 1,r);
}//get max

__int128 DFS2(int l,int r){
  if(l > r)
    return 0;
  if(l == r)
    return A[l];
  int mid = STN.Query(l,r);
  return (__int128)(mid - l + 1) * (r - mid + 1) * A[mid] + DFS2(l,mid - 1) + DFS2(mid + 1,r);
}//get min