线段树-HDU4578 Transformation

Xhyukhalt · 2021-10-17 16:26:17 · 个人记录

出自：2013ACM-ICPC杭州赛区全国邀请赛 ~~好久没水博客了~~ 断断续续写了一周，由于太复杂，加上自己总会在里面写一些不该出现的错误，导致调试时间拉得很长。现在终于过掉了，于是兴高采烈地水一篇。 ### 题意给定一段序列，现给定四种操作如下： $1\ x\ y\ z$：使这段序列$[x,y]$区间内的每一个数字$+z$。 $2\ x\ y\ z$：使这段序列$[x,y]$区间内的每一个数字$×z$。 $3\ x\ y\ z$：使这段序列$[x,y]$区间内的每一个数字$=z$。 $4\ x\ y\ p$：查询这段序列$[x,y]$区间内的每一个数字的$p$次方的和，其中保证$1≤z≤3$。 ### 做法题目本身不难，难受在于这道题很复杂。由于本题数据较为简单，所以暴力更新懒标记的方法可行。但是由于我们要维护一段序列的和、平方和、立方和，加上我们有加法操作、乘法操作、更改操作和查询操作，所以本题用这种办法实现十分的麻烦。首先我们设懒标记： $Inc:

这段区间所有数要加的值。

Mul:

这段区间所有数要乘的值。

Fix:

这段区间所有数要变成的值。

s_1,s_2,s_3:

这段区间所有数的和、平方和、立方和。

首先我们要规定+和×的运算顺序。维护一段区间的时候，利用其懒标记算出它最终的值的时候，我们采用先乘后加的顺序。所以当我们更新加标记的时候，可以直接加上去，但是如果更新乘标记的时候，需要先把加标记处理掉（即下传），然后再更新乘标记。

现在考虑pushdown函数。

现设一个区间的长度为$l$，重新赋的值为$c$，原始和标记为$s_1,s_2,s_3$，更改后的为$s_1',s_2',s_3'$。先从最简单的操作$3$开始。这个操作对区间每一个数重新赋值，所以$s_1,s_2,s_3$非常好求： $$s_1'=cl$$ $$s_2'=c^2l$$ $$s_3'=c^3l$$ 然后是乘法操作，对每一个数翻倍，那么对所有数所更改的倍数是固定的，那么和的变化也是固定的： $$s_1'=cs_1$$ $$s_2'=c^2s_2$$ $$s_3'=c^3s_3$$ 最复杂的是加法操作，对每一个数进行加法，由于先加后方会带来一些多余项，我们在计算加的$c$的时候也要算上运算过程中所产生的其他项。假设区间下标为$1,2,\cdots,l$，考虑到： $$s_1=x_1+x_2+\cdots+x_l$$ $$s_1'=(x_1+c)+(x_2+c)+\cdots+(x_l+c)=s_1+cl $$ $$s_2=x_1^2+x_2^2+\cdots+x_l^2$$ $$s_2'=(x_1^2+2cx_1+c^2)+(x_2^2+2cx_2+c^2)+\cdots+(x_l^2+2cx_l+c^2)$$ $$s_2'=s_2+2cs_1+c^2l$$ 同理得 $$s_3'=s_3+3cs_2+3c^2s_1+c^3l$$ 发现高幂标记需要用低幂标记来更新，所以我们先从立方和开始更新，然后更新平方和，最后更新和。用这样的思路，于是就可以写出超长$pushdown$函数。（可能是我代码臭）每次更新在直接修改区间的时候，对这个区间的和标记也是这样更新。 $AcceptCode:

#include<bits/stdc++.h>
#include<ctime>
using namespace std;
typedef long long LL;
const LL p = 1e4 + 7;

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

struct tree
{
    LL l, r, Inc, Mul, Fix;
    LL s[5];
}t[400050];

void build_tree(LL ni, LL l, LL r)
{
    t[ni].l = l; t[ni].r = r;
    t[ni].s[1] = t[ni].s[2] = t[ni].s[3] = t[ni].Inc = 0;
    t[ni].Fix = -1;
    t[ni].Mul = 1;
    if (l == r) return;
    LL mid = (l + r) >> 1;
    build_tree(ni << 1, l, mid);
    build_tree((ni << 1) + 1, mid + 1, r);
}

void pd(LL ni)
{
    LL ls = (ni << 1), rs = ((ni << 1) + 1); 
    LL lc = (t[ls].r - t[ls].l + 1), rc = (t[rs].r - t[rs].l + 1);
    if (t[ni].Fix != -1)
    {
        t[ls].Fix = t[rs].Fix = t[ni].Fix;
        t[ls].Inc = t[rs].Inc = 0;
        t[ls].Mul = t[rs].Mul = 1;
        t[ls].s[1] = (t[ls].Fix * lc) % p;
        t[ls].s[2] = (t[ls].s[1] * t[ls].Fix) % p;
        t[ls].s[3] = (t[ls].s[2] * t[ls].Fix) % p;
        t[rs].s[1] = (t[rs].Fix * rc) % p;
        t[rs].s[2] = (t[rs].s[1] * t[rs].Fix) % p;
        t[rs].s[3] = (t[rs].s[2] * t[rs].Fix) % p;
    }
    if (t[ni].Mul > 1)
    {
        LL c1 = t[ni].Mul; LL c2 = (c1 * c1) % p, c3 = (c1 * c1 * c1) % p;
        t[ls].Mul = (t[ls].Mul * t[ni].Mul) % p;
        t[rs].Mul = (t[rs].Mul * t[ni].Mul) % p;
        t[ls].Inc = (t[ls].Inc * t[ni].Mul) % p;
        t[rs].Inc = (t[rs].Inc * t[ni].Mul) % p;
        LL M = t[ni].Mul; t[ni].Mul = 1;
        t[ls].s[1] = (t[ls].s[1] * c1) % p;
        t[rs].s[1] = (t[rs].s[1] * c1) % p;
        t[ls].s[2] = (t[ls].s[2] * c2) % p;
        t[rs].s[2] = (t[rs].s[2] * c2) % p;
        t[ls].s[3] = (t[ls].s[3] * c3) % p;
        t[rs].s[3] = (t[rs].s[3] * c3) % p;
    }
    if (t[ni].Inc > 0)
    {
        t[ls].Inc += t[ni].Inc; t[rs].Inc += t[ni].Inc;
        LL c = t[ni].Inc;
        t[ls].s[3] = t[ls].s[3] + lc * c * c * c + 3 * t[ls].s[2] * c + 3 * t[ls].s[1] * c * c;
        t[ls].s[3] %= p;
        t[rs].s[3] = t[rs].s[3] + rc * c * c * c + 3 * t[rs].s[2] * c + 3 * t[rs].s[1] * c * c;
        t[rs].s[3] %= p;
        t[ls].s[2] = t[ls].s[2] + t[ls].s[1] * c * 2 + lc * c * c;
        t[ls].s[2] %= p;
        t[rs].s[2] = t[rs].s[2] + t[rs].s[1] * c * 2 + rc * c * c;
        t[rs].s[2] %= p;
        t[ls].s[1] = (t[ls].s[1] + lc * c) % p;
        t[rs].s[1] = (t[rs].s[1] + rc * c) % p;
        t[ni].Inc = 0;
    }
    t[ni].Inc = 0; t[ni].Fix = -1; t[ni].Mul = 1;
}

void pu(LL ni)
{
    t[ni].s[1] = (t[ni << 1].s[1] + t[(ni << 1) + 1].s[1]) % p;
    t[ni].s[2] = (t[ni << 1].s[2] + t[(ni << 1) + 1].s[2]) % p;
    t[ni].s[3] = (t[ni << 1].s[3] + t[(ni << 1) + 1].s[3]) % p;
}

void add(LL ni, LL l, LL r, LL c)
{ 
    if (l <= t[ni].l && t[ni].r <= r)
    {
        t[ni].Inc = (t[ni].Inc + c) % p;
        LL len = t[ni].r - t[ni].l + 1;
        t[ni].s[3] = (t[ni].s[3] + 3 * c * t[ni].s[2] + 3 * c * c * t[ni].s[1] + c * c * c * len) % p;
        t[ni].s[2] = (t[ni].s[2] + 2 * c * t[ni].s[1] + len * c * c) % p;
        t[ni].s[1] = (t[ni].s[1] + c * len) % p;
        return;
    }
    pd(ni);
    LL mid = (t[ni].l + t[ni].r) >> 1;
    if (l <= mid) add(ni << 1, l, r, c);
    if (mid < r) add((ni << 1) + 1, l, r, c);
    pu(ni);
}

void mul(LL ni, LL l, LL r, LL c)
{
    if (l <= t[ni].l && t[ni].r <= r)
    {
        t[ni].Inc = (t[ni].Inc * c) % p;
        t[ni].Mul = (t[ni].Mul * c) % p;
        t[ni].s[3] = (t[ni].s[3] * c * c * c) % p;
        t[ni].s[2] = (t[ni].s[2] * c * c) % p;
        t[ni].s[1] = (t[ni].s[1] * c) % p; 
        return;
    }
    pd(ni);
    LL mid = (t[ni].l + t[ni].r) >> 1;
    if (l <= mid) mul(ni << 1, l, r, c);
    if (mid < r) mul((ni << 1) + 1, l, r, c);
    pu(ni);
}

void fix(LL ni, LL l, LL r, LL c)
{
    if (l <= t[ni].l && t[ni].r <= r)
    {
        t[ni].Fix = c;
        t[ni].Inc = 0; t[ni].Mul = 1;
        LL len = (t[ni].r - t[ni].l + 1);
        t[ni].s[1] = (c * len) % p;
        t[ni].s[2] = (c * c * len) % p;
        t[ni].s[3] = (c * c * c * len) % p;
        return;
    }
    pd(ni);
    LL mid = (t[ni].l + t[ni].r) >> 1;
    if (l <= mid) fix(ni << 1, l, r, c);
    if (mid < r) fix((ni << 1) + 1, l, r, c);
    pu(ni);
}

LL que(LL ni, LL l, LL r, LL c)
{
    if (l <= t[ni].l && t[ni].r <= r)
    {
        return t[ni].s[c];
    }
    pd(ni);
    LL mid = (t[ni].l + t[ni].r) >> 1;
    LL lr = 0, rr = 0;
    if (l <= mid) lr = que(ni << 1, l, r, c);
    if (mid < r) rr = que((ni << 1) + 1, l, r, c);
    pu(ni);
    return (lr + rr) % p;
}

LL n, m;

void main2()
{
    build_tree(1, 1, n);
    for (LL i = 1; i <= m; ++i)
    {
        LL o, x, y, z;
        o = read(); x = read(); y = read(); z = read();
        if (o == 1)
        {
            add(1, x, y, z);
        }
        else if (o == 2)
        {
            mul(1, x, y, z); 
        }
        else if (o == 3)
        {
            fix(1, x, y, z);
        }
        else
        {
            printf("%lld\n", que(1, x, y, z));
        }
    }
}
LL T;
int main()
{
    while (1)
    {
        n = read(); m = read();
        if (!n && !m) break;
        main2();
    }
    return 0;
}