洛谷P1083 二分答案+差分

算法关键词：二分答案、差分

题目描述

数据范围：(1leq n,mleq10^6)
题目意思：给定长度为(n)的数组，和(m)次询问，每次询问把数组([l,r])减去(d)，问第几次询问能够使得数组能够存在小于0的数。

朴素

朴素做法:对当前(1..n)对每个询问区间做修改(闭区间([l,r])同时减去(d))，同时扫描当前区间长度([1,n])是否出现(a[i]leq0)。
不难分析时间复杂度是(O(nm)),而((10^6)^2>>10^7)必然超时。观察数据(1e6)的数据考虑(nlgn)做法。

二分答案和差分思想

时间复杂度(O( ext{log}(m)*(n+m)))

具有二段性

本题关键是如果第(k)个答案是不符合要求的，那么后面的都肯定不符合要求（后面减去上一些数，肯定也是小于0的）。即答案具有二段性。我们需要找到一个临界点，在这个临界点区间某个点下一次会被减到负数，而该点后面都是不满足的情况。
因此，我们需要实现一个函数check(m)，使得询问当前这个点(m)是符合的（如果区间每一个数都是小于原来数组的那么是符合的），并且通过二分找到这个符合点的最右端点(k)。

差分思想优化区间修改的过程

再次发现，每一次再修改一个区间都是同时加上或者减去某个数，最后会询问当前这个答案m下，是否是符合的，属于离线修改区间，可以考虑使用差分思想。
方法是对于 ([l,r]) 加上(d)实质上是对于差分数组(p)做(p[l]+d),(p[r+1]-d)。
即为：

  for (int i = l; i <= r; i++) {
    q[s[i]] += d[i];
    q[t[i] + 1] -= d[i];//做差分
  }

最后对差分数组q求前缀和：

for (int i = 1; i <= n; i++) q[i] = q[i] + q[i - 1];

这样即可在(O(n+m))的时间复杂度内得到修改后的数组。
而暴力是需要(O(m*n))的时间复杂度。

二分答案过程使用差分思想优化后的时间复杂度

因为总共有(m)次询问，二分([1,m])区间总共是(O( ext{log}(m)))次
而每一次是使用差分优化，差分时间复杂度是(O(n+m))，因此时间复杂度是(O( ext{log}(m)*(n+m)))，
综上比暴力(O(nm))快得多。

代码

//https://www.luogu.com.cn/problem/P1083
// Author: oceanlvr
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static int faster_iostream = []() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(NULL);
  return 0;
}();
int n, m;
const int maxn = 1e6 + 10;
ll a[maxn];
ll q[maxn];
ll d[maxn], s[maxn], t[maxn];

bool check(int idx) {
  memset(q, 0, sizeof q);
  int l = 1, r = idx;
  for (int i = l; i <= r; i++) {
    q[s[i]] += d[i];
    q[t[i] + 1] -= d[i];//做差分
  }
  //对差分做前缀和 得到最后m次修改之后的数组
  for (int i = 1; i <= n; i++) q[i] = q[i] + q[i - 1];
  for (int i = 1; i <= n; i++) {
    if (q[i] > a[i]) {
      return false;
    }
  }
  return true;  //满足分配条件
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= m; i++) cin >> d[i] >> s[i] >> t[i];
  //时间复杂度O(lg(m)*(m+n))
  int l = 1, r = m;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (check(mid)) {  //满足分配
      l = mid;         //试图找不满足
    } else {
      r = mid - 1;
    }
  }
  if (r == m) {
    cout << 0 << endl;
  } else if (check(r)) {
    cout << -1 << endl << r + 1 << endl;
  } else {
    //一个都不满足 此时r=1
    cout << -1 << endl << r << endl;
  }
  return 0;
}