Title Link:

https://loj.ac/problem/6280

Title:

Give you a sequence of n integers, let you do two operations;

• Add a value xxx to the number between [l,r][l,r][l,r]
• Ask the number between [l,r][l,r][l,r] and modmodmod mod (x+1)(x+1)(x+1)

Analysis:

Block is used here;
If you want to solve this problem directly, you need to preprocess the element sum of each block and maintain it; when you modify, you need to violence the incomplete block of the interval, if it is a complete block, add it to the tag; for query, you need to violence the sum of the incomplete block, multiply the tag by the length of the interval and add the element sum of the block;

Code:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define inf 0x7f7f7f7f
#define maxn 50050
#define N 100100
#define P 2

typedef long long ll;
typedef struct {
    int u, v, next, w;
} Edge;
Edge e[2];
int cnt, head[1];

inline void add(int u, int v, int w) {
    e[cnt].u = u;
    e[cnt].v = v;
    e[cnt].w = w;
    // e[cnt].f=f;
    e[cnt].next = head[u];
    head[u] = cnt++;
    e[cnt].u = v;
    e[cnt].v = u;
    e[cnt].w = w;
    //    e[cnt].f=-f;
    e[cnt].next = head[v];
    head[v] = cnt++;
}

inline void write(int x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

int opt, l, r, c, sz, n, pos[maxn];
ll mark[maxn], a[maxn], sum[maxn];
vector<ll> vec[250];
void update(int l, int r, int val) {
    int pl = pos[l], pr = pos[r];
    for (int i = l; i <= min((pl + 1) * sz, r); i++) {
        a[i] += val;
        sum[pl] += val;
    }
    if (pl != pr) {
        for (int i = pr * sz + 1; i <= r; i++) {
            a[i] += val;
            sum[pr] += val;
        }
    }
    for (int i = pl + 1; i < pr; i++) {
        mark[i] += val;
        sum[i] += 1ll * sz * val;
    }
}
ll query(int l, int r, int val) {
    ll res = 0;
    int pl = pos[l], pr = pos[r];
    for (int i = l; i <= min((pl + 1) * sz, r); i++) {
        res += (mark[pl] + a[i]);
    }
    if (pl != pr) {
        for (int i = pr * sz + 1; i <= r; i++) {
            res += (mark[pr] + a[i]);
        }
    }
    for (int i = pl + 1; i < pr; i++) res += sum[i];
    return res % (val + 1);
}
int main() {
    cin >> n;
    sz = sqrt(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pos[i] = (i - 1) / sz;
        vec[pos[i]].push_back(a[i]);
        sum[pos[i]] += a[i];
    }
    for (int i = 1; i <= n; i++) {
        opt = read(), l = read(), r = read(), c = read();
        if (opt) {
            printf("%d\n", query(l, r, c));
        } else {
            update(l, r, c);
        }
    }
    return 0;
}

We insist on one thing not because it will work, but because we firmly believe that it is right to do so.
——Javier