Transformation

区间维护加法，乘法，赋值，求三次方的和

思路

an very old problem

#include <bits/stdc++.h>

using namespace std;

#define dbg(x...) do { cout << #x << " -> "; err(x); } while (0)

void err() { cout << endl; }

template<class T, class... Ts>
void err(const T &arg, const Ts &... args) {
    cout << arg << ' ';
    err(args...);
}

#define endl "\n"
using pii = pair<int, int>;
using ll = long long;
using db = double;

const int N = 1e5 + 10;
const int p = 10007;

int n, q;

struct SEG {
    struct node {
        int l, r;
        int sum[3], lazy[3];//+ * =
        node() {
            sum[0] = sum[1] = sum[2] = 0;
            lazy[0] = lazy[2] = 0;
            lazy[1] = 1;
        }

        node(int _l, int _r) {
            l = _l;
            r = _r;
            sum[0] = sum[1] = sum[2] = 0;
            lazy[0] = lazy[2] = 0;
            lazy[1] = 1;
        }
    } t[N << 2];
    
    void add(int id, int v) {
        int len = t[id].r - t[id].l + 1;
        t[id].sum[2] = (t[id].sum[2] + (len * v % p * v % p * v % p) + (3 * v % p * v % p * t[id].sum[0] % p) +
                        (3 * v % p * t[id].sum[1] % p)) % p;
        t[id].sum[1] = (t[id].sum[1] + (2 * v % p * t[id].sum[0] % p) + (len * v % p * v % p)) % p;
        t[id].sum[0] = (t[id].sum[0] + len * v % p) % p;
        t[id].lazy[0] = (t[id].lazy[0] + v) % p;
    }
    
    void mul(int id, int v) {
        t[id].sum[0] = (t[id].sum[0] * v) % p;
        t[id].sum[1] = (t[id].sum[1] * v % p * v) % p;
        t[id].sum[2] = (t[id].sum[2] * v % p * v % p * v) % p;
        t[id].lazy[0] = t[id].lazy[0] * v % p;
        t[id].lazy[1] = t[id].lazy[1] * v % p;
    }
    
    void equ(int id, int v) {
        int len = t[id].r - t[id].l + 1;
        t[id].sum[0] = len * v % p;
        t[id].sum[1] = t[id].sum[0] * v % p;
        t[id].sum[2] = t[id].sum[1] * v % p;
        t[id].lazy[0] = 0;
        t[id].lazy[1] = 1;
        t[id].lazy[2] = v;
    }
    
    void build(int id, int l, int r) {
        t[id] = node(l, r);
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
    
    void down(int id) {
        if (t[id].l >= t[id].r) return;
        if (t[id].lazy[2]) {
            equ(id << 1, t[id].lazy[2]);
            equ(id << 1 | 1, t[id].lazy[2]);
            t[id].lazy[2] = 0;
        }
        if (t[id].lazy[1] != 1) {
            mul(id << 1, t[id].lazy[1]);
            mul(id << 1 | 1, t[id].lazy[1]);
            t[id].lazy[1] = 1;
        }
        if (t[id].lazy[0]) {
            add(id << 1, t[id].lazy[0]);
            add(id << 1 | 1, t[id].lazy[0]);
            t[id].lazy[0] = 0;
        }
    }
    
    void up(int id) {
        int lson = id << 1;
        int rson = id << 1 | 1;
        t[id].sum[0] = (t[lson].sum[0] + t[rson].sum[0]) % p;
        t[id].sum[1] = (t[lson].sum[1] + t[rson].sum[1]) % p;
        t[id].sum[2] = (t[lson].sum[2] + t[rson].sum[2]) % p;
    }
    
    void update(int id, int ql, int qr, int op, int v) {
        if (t[id].l >= ql && t[id].r <= qr) {
            if (op == 0) {
                add(id, v);
            } else if (op == 1) {
                mul(id, v);
            } else if (op == 2) {
                equ(id, v);
            }
            return;
        }
        down(id);
        int mid = (t[id].l + t[id].r) >> 1;
        if (ql <= mid) update(id << 1, ql, qr, op, v);
        if (qr > mid) update(id << 1 | 1, ql, qr, op, v);
        up(id);
    }
    
    int query(int id, int ql, int qr, int idx) {
        if (t[id].l >= ql && t[id].r <= qr) {
            return t[id].sum[idx];
        }
        down(id);
        int mid = (t[id].l + t[id].r) >> 1;
        int res = 0;
        if (ql <= mid) res = (res + query(id << 1, ql, qr, idx)) % p;
        if (qr > mid) res = (res + query(id << 1 | 1, ql, qr, idx)) % p;
        return res;
    }
} seg;

void RUN() {
    while (scanf("%d %d", &n, &q) != EOF) {
        if (n == 0 && q == 0) break;
        seg.build(1, 1, n);
        while (q--) {
            int op, a, b, c;
            scanf("%d %d %d %d", &op, &a, &b, &c);
            if (op <= 3) {
                seg.update(1, a, b, op - 1, c);
            } else {
                printf("%d\n", seg.query(1, a, b, c - 1));
            }
        }
    }
}

int main() {
#ifdef LOCAL_JUDGE
    freopen("input.txt", "r", stdin);
#endif

//    ios::sync_with_stdio(false);
//    cin.tie(nullptr), cout.tie(nullptr);

    RUN();

#ifdef LOCAL_JUDGE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

Copy