#6029. 「雅礼集训 2017 Day1」市场 [线段树]

考虑到每次除法，然后加法，差距会变小，于是维护加法lazytag即可
#include <cstdio>

#include <cmath>

#define int long long

int read() {

  int x = 0;

  bool f = 0;

  char c = getchar();

  while (c < 48) f ^= (c == '-'), c = getchar();

  while (c > 47) x = x * 10 + (c - 48), c = getchar();

  return f ? -x : x;

}

int n, m;

const int maxn = 1e5 + 51;

int a[maxn];

int mn[maxn << 2], mx[maxn << 2];

int del[maxn << 2], sum[maxn << 2];

int min(int x, int y) { return x < y ? x : y; }

int max(int x, int y) { return x > y ? x : y; }

void pushup(int rt) {

  mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);

  mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);

  sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];

}

void build(int l, int r, int rt) {

  if (l == r) {

    sum[rt] = mn[rt] = mx[rt] = a[l];

    return;

  }

  int mid = l + r >> 1;

  build(l, mid, rt << 1);

  build(mid + 1, r, rt << 1 | 1);

  pushup(rt);

}

void pushtag(int l, int r, int rt, int x) {

  del[rt] += x, mn[rt] += x, mx[rt] += x;

  sum[rt] += x * (r - l + 1);

}

void pushd(int l, int r, int rt) {

  if (!del[rt]) return;

  int mid = l + r >> 1;

  pushtag(l, mid, rt << 1, del[rt]);

  pushtag(mid + 1, r, rt << 1 | 1, del[rt]);

  del[rt] = 0;

}

void modify(int a, int b, int l, int r, int rt, int v) {

  if (a <= l && r <= b) {

    pushtag(l, r, rt, v);

    return;

  }

  pushd(l, r, rt);

  int mid = l + r >> 1;

  if (a <= mid) modify(a, b, l, mid, rt << 1, v);

  if (b > mid) modify(a, b, mid + 1, r, rt << 1 | 1, v);

  pushup(rt);

}

void div(int a, int b, int l, int r, int rt, int v) {

  if (a <= l && r <= b) {

    int tx = floor((double)mx[rt] / v);

    int ty = floor((double)mn[rt] / v);

    if (tx - mx[rt] == ty - mn[rt]) {

      pushtag(l, r, rt, tx - mx[rt]);

      return;

    }

    pushd(l, r, rt);

    int mid = l + r >> 1;

    div(a, b, l, mid, rt << 1, v), div(a, b, mid + 1, r, rt << 1 | 1, v);

    pushup(rt);

    return;

  }

  pushd(l, r, rt);

  int mid = l + r >> 1;

  if (a <= mid) div(a, b, l, mid, rt << 1, v);

  if (b > mid) div(a, b, mid + 1, r, rt << 1 | 1, v);

  pushup(rt);

}

int qry(int a, int b, int l, int r, int rt) {

  if (a <= l && r <= b) return sum[rt];

  pushd(l, r, rt);

  int mid = l + r >> 1;

  int ans = 0;

  if (a <= mid) ans = qry(a, b, l, mid, rt << 1);

  if (b > mid) ans += qry(a, b, mid + 1, r, rt << 1 | 1);

  return ans;

}

int qrymin(int a, int b, int l, int r, int rt) {

  if (a <= l && r <= b) return mn[rt];

  pushd(l, r, rt);

  int mid = l + r >> 1;

  int ans = 1e18;

  if (a <= mid) ans = min(ans, qrymin(a, b, l, mid, rt << 1));

  if (b > mid) ans = min(ans, qrymin(a, b, mid + 1, r, rt << 1 | 1));

  return ans;

}

signed main() {

  n = read(), m = read();

  for (int i = 1; i <= n; i++) a[i] = read();

  build(1, n, 1);

  while (m--) {

    int op;

    op = read();

    if (op == 1) {

      int l, r, x;

      l = read(), r = read(), x = read();

      ++l, ++r;

      modify(l, r, 1, n, 1, x);

    }

    if (op == 2) {

      int l, r, x;

      l = read(), r = read(), x = read();

      ++l, ++r;

      div(l, r, 1, n, 1, x);

    }

    if (op == 3) {

      int l, r;

      l = read(), r = read();

      ++l, ++r;

      printf("%lld\n", qrymin(l, r, 1, n, 1));

    }

    if (op == 4) {

      int l, r;

      l = read(), r = read();

      ++l, ++r;

      printf("%lld\n", qry(l, r, 1, n, 1));

    }

  }

  return 0;

}
巴特西

#6029. 「雅礼集训 2017 Day1」市场 [线段树]

最新文章

热门文章
