LOJ #6283. 數列分塊入門 7

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
const int mod = 10007;
int n, m, bl[A], add[A], multi[A], sq[A], f[A], opt, a, b, c;
void reset(int x) {
  for (int i = (x - 1) * m + 1; i <= min(x * m, n); i++) sq[i] = (sq[i] * multi[x] % mod + add[x]) % mod;
  add[x] = 0; multi[x] = 1;
}
void addd(int a, int b, int c) {
  reset(bl[a]);
  for (int i = a; i <= min(b, bl[a] * m); i++) sq[i] += c, sq[i] %= mod;
  if (bl[a] != bl[b]) {
    reset(bl[b]);
    for (int i = min(b, (bl[b] - 1) * m + 1); i <= b; i++) sq[i] += c, sq[i] %= mod;
  }
  for (int i = bl[a] + 1; i <= bl[b] - 1; i++) add[i] += c, add[i] %= mod;
}
void multii(int a, int b, int c) {
  reset(bl[a]);
  for (int i = a; i <= min(b, bl[a] * m); i++) sq[i] *= c, sq[i] %= mod;
  if (bl[a] != bl[b]) {
    reset(bl[b]);
    for (int i = min(b, (bl[b] - 1) * m + 1); i <= b; i++) sq[i] *= c, sq[i] %= mod;
  }
  for (int i = bl[a] + 1; i <= bl[b] - 1; i++) add[i] *= c, add[i] %= mod, multi[i] *= c, multi[i] %= mod;
}

int main(int argc, char const *argv[]) {
  scanf("%d", &n); m = sqrt(n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &sq[i]);
    bl[i] = (i - 1) / m + 1;
  }
  for (int i = 1; i <= bl[n]; i++) multi[i] = 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d%d", &opt, &a, &b, &c);
    if (opt == 2) printf("%d\n", (sq[b] * multi[bl[b]] % mod + add[bl[b]]) % mod);
    else if (opt == 1) multii(a, b, c);
    else addd(a, b, c);
  }
  return 0;
}