[ABC282Ex] Min + Sum 题解

题面传送门。

题目要求有多少对 \((l, r)\) 满足 \(1 \le l \le r \le n\) 且 \(\sum_{i=l}^{r}{b_i} + \min_{i=l}^{r}{a_i} \le S\)。

考虑 CDQ 分治，那么我们需要不断寻找有多少对 \((l,r)\) 满足 \(L \le l \le M < r \le R\) 且 \(\sum_{i=l}^{r}{b_i} + \min_{i=l}^{r}{a_i} \le S\)。因为第一条限制，所以第二条限制可以转化为 \(\sum_{i=M+1}^{r}{b_i} + \sum_{i=l}^{M}{b_i} + \min(\min_{i=l}^{M}{a_i}, \min_{i=M+1}^{r}{a_i}) \le S\)。

这显然需要先进行前后缀和。我们无法做到枚举 \(l\) 又枚举 \(r\)。所以考虑枚举 \(r\)。容易发现 \(\min_{i=x}^{M}{a_i} \le \min_{i=x + 1}^{M}{a_i}\)，于是我们双指针，找到一个 \(x\)，对于当前枚举到的 \(r\) 满足 \(\min_{i=x}^{M}{a_i} < \min_{i=M+1}^{r}{a_i} \le \min_{i=x + 1}^{M}{a_i}\)。

那么现在，\([L,x]\) 中的点 \(l\) 需要满足 \(\min_{i=l}^{M}{a_i} + \sum_{i=l}^{M}{b_i} + \sum_{i=M+1}^{r}{b_i} \le S\)。

\((x,M]\) 中的点 \(l\) 需要满足 \(\sum_{i=l}^{M}{b_i} + \min_{i=M+1}^{r}{a_i} + \sum_{i=M+1}^{r}{b_i} \le S\)。

由于我们已知右端点 \(r\)，所以可以分类讨论左端点 \(l\) 的情况。对不等式移项，求出其限制，最后发现这是一个插入删除后，求多少个插入后保留数满足小于某个数，这显然可以用 01 - trie 来解决。

最后时间复杂度 \(O(n \log n \log S)\)。

AC Code

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int MAXN = 2e5 + 3;

int n;
LL S, ans = 0, a[MAXN], b[MAXN]; 
LL smi[MAXN], ssum[MAXN];

int top[2] = {1, 1}, eg[2][MAXN * 50][2], cnt[2][MAXN * 50];

inline void Insert(int op, LL x){ // 01 - trie 插入 
  int p = 1;
  for(int i = 49; i >= 0; i--){ int col = (x >> i) & 1;
    if(!eg[op][p][col]) eg[op][p][col] = ++top[op];
    p = eg[op][p][col], cnt[op][p]++;
  }
}
inline void Erase(int op, LL x){ // 01 - trie 删除 
  int p = 1;
  for(int i = 49; i >= 0; i--){ int col = (x >> i) & 1;
    p = eg[op][p][col], cnt[op][p]--;
  }
}
inline int query(int op, LL x){ // 01 - trie 求小于 x 的个数 
  if(x <= 0) return 0;
  int p = 1, ret = 0;
  for(int i = 49; i >= 0; i--){ int col = (x >> i) & 1;
    if(col == 1 && eg[op][p][0]) ret += cnt[op][eg[op][p][0]];
    if(!eg[op][p][col]) eg[op][p][col] = ++top[op];
    p = eg[op][p][col];
  }
  return ret;
}
void Clear(){ // 清空 01 - trie 
  for(int op = 0; op <= 1; op++){
    for(int i = 1; i <= top[op]; i++) cnt[op][i] = eg[op][i][0] = eg[op][i][1] = 0;
    top[op] = 1;
  }
}

void Solve(int l, int r){ // CDQ 分治 
  if(l == r){
    ans += (a[l] + b[l] <= S); // 统计 l = r 的区间 
    return;
  } 
  int mid = (l + r) >> 1;
  smi[mid] = a[mid], ssum[mid] = b[mid], Insert(0, ssum[mid] + smi[mid]); // 预处理 [l,mid] 区间 
  for(int i = mid - 1; i >= l; i--) smi[i] = min(smi[i + 1], a[i]), ssum[i] = ssum[i + 1] + b[i], Insert(0, ssum[i] + smi[i]);
  
  LL mi = 1e17, sum = 0;
  for(int i = mid + 1, j = mid + 1; i <= r; i++){ // 在 (mid,r] 中枚举答案右端点 
    mi = min(mi, a[i]), sum += b[i];
    while(j > l && smi[j - 1] >= mi) j--, Insert(1, ssum[j]), Erase(0, ssum[j] + smi[j]); // 01 - trie 处理 
    ans += query(1, S - sum - mi + 1) + query(0, S - sum + 1); // 通过 01 - trie 找到合法的在 [l,mid] 中的答案左端点，统计答案 
  }
  Clear(), Solve(l, mid), Solve(mid + 1, r); // 清空 01 - trie 后继续递归处理 
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> S;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= n; i++) cin >> b[i];
  Solve(1, n); 
  cout << ans;  
  return 0;
}