LOJ10129. 「一本通 4.3 练习 3」维护序列

题意描述

source: https://loj.ac/p/10129

维护一个 $\bmod M$ 意义下的序列，支持三种操作：

• 区间乘 $x$
• 区间加 $x$
• 求区间和

序列的初始值和 $x$ 都在 $[0,10^9]$ 内，$1\le M\le 10^9+7$，$1\le n,m\le 10^5$。

思路

将两种操作合并为一种操作“乘 $k$ 再加 $b$”，这样对于一个长为 $\rm len$、和为 $S$ 的序列，每个数乘 $k$ 再加 $b$ 后新的和 $S’$ 就是 $kS+b\cdot\rm len$。详见代码。

代码

https://loj.ac/s/1055841

#define FILE_IO

#include <cstdio>

namespace hermione {

int scan();
template <typename Type, typename... Args> int read(Type&, Args&...);
int token(char*);
template <typename Type> int lread(Type*, const int&);
template <typename Type, typename... Args> void print(const Type&, const Args&...);
template <typename Type> void lprint(Type* arr, const int& length);
#define debug(var) (print(#var, " = ", var, '\n'))
#define lineno() (print("line ", __LINE__, '\n'))

constexpr int MAXN = 100005;
int MOD;

struct oper {
  long long k, b;
  oper(int k_ = 1, int b_ = 0) : k(k_), b(b_) {}
};
oper compose(oper x, oper y) {
  oper res;
  auto [k1, b1] = x;
  auto [k2, b2] = y;
  res.k = k1 * k2 % MOD;
  res.b = b1 * k2 % MOD + b2 % MOD;
  res.b %= MOD;
  return res;
}

struct node {
  int l, r;
  long long sum;
  oper lazy;
} tree[MAXN * 4];
int a[MAXN];

void build(int root, int l, int r) {
  tree[root] = {l, r};
  if (l == r) {
    tree[root].sum = a[l];
    return;
  }
  int mid = (l + r) / 2;
  build(root * 2, l, mid);
  build(root * 2 + 1, mid + 1, r);
  tree[root].sum = (tree[root * 2].sum + tree[root * 2 + 1].sum) % MOD;
}

void pushdown(int root) {
  if (tree[root].lazy.k != 1 || tree[root].lazy.b != 0) {
    int l = tree[root].l, r = tree[root].r;
    int mid = (l + r) / 2;
    tree[root * 2].sum = tree[root * 2].sum * tree[root].lazy.k % MOD + tree[root].lazy.b * (mid - l + 1);
    tree[root * 2].sum %= MOD;
    tree[root * 2 + 1].sum = tree[root * 2 + 1].sum * tree[root].lazy.k % MOD + tree[root].lazy.b * (r - mid);
    tree[root * 2 + 1].sum %= MOD;
    tree[root * 2].lazy = compose(tree[root * 2].lazy, tree[root].lazy);
    tree[root * 2 + 1].lazy = compose(tree[root * 2 + 1].lazy, tree[root].lazy);
    tree[root].lazy = {1, 0};
  }
}

void modify(int root, int ql, int qr, oper delta) {
  int l = tree[root].l, r = tree[root].r;
  if (qr < l || r < ql) { return; }
  if (ql <= l && r <= qr) {
    tree[root].sum = tree[root].sum * delta.k % MOD + delta.b * (r - l + 1) % MOD;
    tree[root].sum %= MOD;
    tree[root].lazy = compose(tree[root].lazy, delta);
    return;
  }
  pushdown(root);
  modify(root * 2, ql, qr, delta);
  modify(root * 2 + 1, ql, qr, delta);
  tree[root].sum = (tree[root * 2].sum + tree[root * 2 + 1].sum) % MOD;
}

long long query(int root, int ql, int qr) {
  int l = tree[root].l, r = tree[root].r;
  if (qr < l || r < ql) { return 0; }
  if (ql <= l && r <= qr) {
    return tree[root].sum;
  }
  pushdown(root);
  return (query(root * 2, ql, qr) + query(root * 2 + 1, ql, qr)) % MOD;
}

int main(int argc, char** argv) {
  int n;
  read(n, MOD);
  lread(a + 1, n);
  build(1, 1, n);
  int m = scan();
  for (int i = 0; i < m; ++i) {
    int op, l, r;
    read(op, l, r);
    if (op == 1) {
      int c = scan();
      modify(1, l, r, {c, 0});
    } else if (op == 2) {
      int c = scan();
      modify(1, l, r, {1, c});
    } else {
      print(query(1, l, r), '\n');
    }
  }
  return 0;
}

#ifndef TYPE_LESS_IO_
#define TYPE_LESS_IO_

#define mread(format) return std::scanf("%" format, &x)

int read(char& x) {
  return std::scanf(" %c", &x);
}
int read(unsigned char& x) {
  mread("hhu");
}
int read(short& x) {
  mread("hd");
}
int read(unsigned short& x) {
  mread("hu");
}
int read(int& x) {
  mread("d");
}
int read(unsigned int& x) {
  mread("u");
}
int read(long& x) {
  mread("ld");
}
int read(unsigned long& x) {
  mread("lu");
}
int read(long long& x) {
  mread("lld");
}
int read(unsigned long long& x) {
  mread("llu");
}
int read(float& x) {
  mread("f");
}
int read(double& x) {
  mread("lf");
}
int read(long double& x) {
  mread("Lf");
}
int read(void*& x) {
  mread("p");
}
int read(char* x) {
  return std::scanf(" %s", x);
}
int read() {
  return 0;
}

template <typename Type>
void read(const Type& x) {
  throw "read type error";
}

template <typename Type, typename... Args>
int read(Type& x, Args&... args) {
  return read(x) != EOF ? read(args...) : EOF;
}

int token(char* x) {
  return std::scanf("%s", x);
}

template <typename Type>
int lread(Type* arr, const int& length) {
  int ret = 0;
  for (int i = 0; i < length; ++i) {
    ret = read(arr[i]);
  }
  return ret;
}

int scan() {
  int x;
  read(x);
  return x;
}

#define mprint(format) std::printf("%" format, x)

void print(const char& x) {
  mprint("c");
}
void print(char* x) {
  mprint("s");
}
void print(const char* x) {
  mprint("s");
}
void print(const unsigned char& x) {
  mprint("hhu");
}
void print(const short& x) {
  mprint("hd");
}
void print(const unsigned short& x) {
  mprint("hu");
}
void print(const int& x) {
  mprint("d");
}
void print(const unsigned int& x) {
  mprint("u");
}
void print(const long& x) {
  mprint("ld");
}
void print(const unsigned long& x) {
  mprint("lu");
}
void print(const long long& x) {
  mprint("lld");
}
void print(const unsigned long long& x) {
  mprint("llu");
}
void print(const double& x) {
  mprint("le");
}
void print(const long double& x) {
  mprint("Le");
}
void print(void* x) {
  mprint("p");
}
void print() {}

template <typename Type>
void print(const Type& x) {
  throw "print type error";
}

template <typename Type, typename... Args>
void print(const Type& x, const Args&... args) {
  print(x);
  print(args...);
}

template <typename Type>
void lprint(Type* arr, const int& length) {
  for (int i = 0; i < length; ++i) {
    print(arr[i]);
    print(i == length - 1 ? '\n' : ' ');
  }
}
void lprint(char* arr, const int& length) {
  for (int i = 0; i < length; ++i) {
    print(arr[i]);
  }
  print('\n');
}

class typeof_print_LF_before_EOF {
public:
  ~typeof_print_LF_before_EOF() {
    print('\n');
  }
} print_LF_before_EOF;

#endif // ifndef TYPE_LESS_IO_

} // namespace hermione

int main(int argc, char** argv) {
  #if defined(DEBUG) && defined(FILE_IO)
  (std::freopen("test.in", "r", stdin));
  (std::freopen("test.out", "w", stdout));
  #endif
  int ret = hermione::main(argc, argv);
  #if defined(DEBUG) && defined(FILE_IO)
  (std::fclose(stdin));
  (std::fclose(stdout));
  #endif
  return ret;
}