欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

(待改)HDU 4578 Transformation (线段树+成段更新+多种操作)

程序员文章站 2022-05-11 18:22:11
...

题意:给你一个数组,初始值为零,有四种操作
(1)“1 x y c”,代表 把区间 [x,y] 上的值全部加c
(2)“2 x y c”,代表 把区间 [x,y] 上的值全部乘以c
(3)“3 x y c” 代表 把区间 [x,y]上的值全部赋值为c
(4)“4 x y p” 代表 求区间 [x,y] 上值的p次方和1<=p<=3

题解:线段树+成段更新+多种操作

wa了一天,实在找不到哪里有问题,1次方答案是对的,但往上就错了。
等刷完成段更新的其他题再看看吧。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
//成段更新
const int mod = 10007;
const int MAXN = 1e5 + 5;
int sum[MAXN << 2][4], add[MAXN << 2], mult[MAXN << 2], cover[MAXN << 2];
struct Node {
    int l, r;
    int mid() { return (l + r) >> 1; }
} tree[MAXN << 2];
void fadd(int rt, int c, int m) {
    add[rt] = (add[rt] + c) % mod;
    sum[rt][3] = (sum[rt][3] + (3 * c * sum[rt][2]) % mod + (3 * ((c * c) % mod) * sum[rt][1]) % mod + (((((c * c) % mod) * c) % mod) * m) % mod) % mod;
    sum[rt][2] = (sum[rt][2] + (2 * c * sum[rt][1]) % mod + (((c * c) % mod) * m) % mod) % mod;
    sum[rt][1] = (sum[rt][1] + (c * m) % mod) % mod;
    //int sum1 = sum[rt][1], sum2 = sum[rt][2], sum3 = sum[rt][3];

    //sum[rt][1] += (c * m) % mod;
    //sum[rt][1] %= mod;

    //int tmp2 = (c * c) % mod;
    //sum[rt][2] += (2 * sum1 * c) % mod + (tmp2 * m) % mod;
    //sum[rt][2] %= mod;

    //int tmp3 = (tmp2 * c) % mod;
    //sum[rt][3] += (3 * tmp2 * sum1) % mod + (3 * c * sum2) % mod + (tmp3 * m) % mod;
    //sum[rt][3] %= mod;
}
void fmult(int rt, int c, int m) {
    if (mult[rt]) mult[rt] = (mult[rt] * c) % mod;
    else mult[rt] = c;
    add[rt] = (add[rt] * c) % mod;
    sum[rt][1] = (c * sum[rt][1]) % mod;
    sum[rt][2] = (((c * c) % mod) * sum[rt][2]) % mod;
    sum[rt][3] = (((((c * c) % mod) * c) % mod) * sum[rt][3]) % mod;
    //add[rt] = (add[rt] * c) % mod;

    //int sum1 = sum[rt][1], sum2 = sum[rt][2], sum3 = sum[rt][3];

    //sum[rt][1] = (sum1 * c) % mod;

    //int tmp2 = (c * c) % mod;
    //sum[rt][2] = (sum2 * tmp2) % mod;

    //int tmp3 = (tmp2 * c) % mod;
    //sum[rt][3] = (sum3 * tmp3) % mod;
}
void fcover(int rt, int c, int m) {
    cover[rt] = c;
    add[rt] = mult[rt] = 0;
    sum[rt][1] = (c * m) % mod;
    sum[rt][2] = (c * sum[rt][1]) % mod;
    sum[rt][3] = (c * sum[rt][2]) % mod;
}
void PushDown(int rt, int m) {
    if (cover[rt]) {
        fcover(rt << 1, cover[rt], m - (m >> 1));
        fcover(rt << 1 | 1, cover[rt], m >> 1);
        cover[rt] = 0;
    }
    if (mult[rt]) {
        fmult(rt << 1, mult[rt], m - (m >> 1));
        fmult(rt << 1 | 1, mult[rt], m >> 1);
        mult[rt] = 0;
    }
    if (add[rt]) {
        fadd(rt << 1, add[rt], m - (m >> 1));
        fadd(rt << 1 | 1, add[rt], m >> 1);
        add[rt] = 0;
    }
}
void PushUp(int rt) {
    sum[rt][1] = (sum[rt << 1][1] + sum[rt << 1 | 1][1]) % mod;
    sum[rt][2] = (sum[rt << 1][2] + sum[rt << 1 | 1][2]) % mod;
    sum[rt][3] = (sum[rt << 1][3] + sum[rt << 1 | 1][3]) % mod;
}
void build(int l, int r, int rt) {
    tree[rt].l = l;
    tree[rt].r = r;
    sum[rt][1] = sum[rt][2] = sum[rt][3] = add[rt] = mult[rt] = cover[rt] = 0;
    if (l == r) {
        sum[rt][1] = sum[rt][2] = sum[rt][3] = 0;
        return;
    }
    int m = tree[rt].mid();
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    //PushUp(rt);
}
void update(int c, int l, int r, int rt, int id) {
    if (tree[rt].l == l && r == tree[rt].r) {
        if (id == 1) fadd(rt, c, r - l + 1);
        else if (id == 2) fmult(rt, c, r - l + 1);
        else fcover(rt, c, r - l + 1);
        return;
    }
    if (tree[rt].l == tree[rt].r) return;
    PushDown(rt, tree[rt].r - tree[rt].l + 1);
    int m = tree[rt].mid();
    if (r <= m) update(c, l, r, rt << 1, id);
    else if (l > m) update(c, l, r, rt << 1 | 1, id);
    else {
        update(c, l, m, rt << 1, id);
        update(c, m + 1, r, rt << 1 | 1, id);
    }
    PushUp(rt);
}
int query(int l, int r, int rt, int p) {
    if (l == tree[rt].l && r == tree[rt].r) {
        return sum[rt][p];
    }
    PushDown(rt, tree[rt].r - tree[rt].l + 1);
    int m = tree[rt].mid();
    int res = 0;
    if (r <= m) res += query(l, r, rt << 1, p), res %= mod;
    else if (l > m) res += query(l, r, rt << 1 | 1, p), res %= mod;
    else {
        res += query(l, m, rt << 1, p), res %= mod;
        res += query(m + 1, r, rt << 1 | 1, p), res %= mod;
    }
    return res;
}
int n, m, id, x, y, c;
int main() {
    freopen("in.txt", "r", stdin);
    while (~scanf("%d%d", &n, &m) && n) {
        build(1, n, 1);
        for (int i = 1; i <= m; i++) {
            scanf("%d%d%d%d", &id, &x, &y, &c);
            if (id <= 3) update(c, x, y, 1, id);
            else printf("%d\n", query(x, y, 1, c));
        }
    }
	return 0;
}