Visit Counter
AmazingCounters.com

1、感谢popoqqq大神犇
2、题目大意:就是线段树修改,双标记,一个是区间×,一个是区间+,询问区间和
3、分析:之前一直不会做双标记的线段树,长姿势了
其实双标记只需要记住一条,父亲的优先级比儿子的小,所以标记先传合并的时候,以儿子为开始
然后这道题就变的略水了一点(可是我还是不会啊),然后就是下传自己推一下什么的,
双标记就是两个lazy,但是这两种lazy就需要自己定一个优先级(就是先进行那个操作),这道题,
显然是×定为优先级最高的更好
于是我们推一推下传就出来了,主要还是那个儿子和父亲的优先级的问题(听popoqqq神犇讲完,
顿时感觉自己啥也不会了,自己太弱了)
4、这样的话,代码就非常好实现了
代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
struct segment_tree{
    LL N, P;
    LL sum[1000000];
    LL clazy[1000000];
    LL jlazy[1000000];
    LL value[1000000];
    LL x, y, z;
    void build(LL l, LL r, LL o){
        if(l == r){
            clazy[o] = 1;
            jlazy[o] = 0;
            sum[o] = value[l];
            return;
        }
        int mid = (l + r) / 2;
        build(l, mid, 2 * o);
        build(mid + 1, r, 2 * o + 1);
        sum[o] = sum[2 * o] + sum[2 * o + 1]; sum[o] %= P;
        clazy[o] = 1;
        jlazy[o] = 0;
        return;
    }
    void updata(LL l, LL r, LL o){
        clazy[2 * o] *= clazy[o]; clazy[2 * o] %= P;
        jlazy[2 * o] *= clazy[o]; jlazy[2 * o] %= P;
        jlazy[2 * o] += jlazy[o]; jlazy[2 * o] %= P;
        clazy[2 * o + 1] *= clazy[o]; clazy[2 * o + 1] %= P;
        jlazy[2 * o + 1] *= clazy[o]; jlazy[2 * o + 1] %= P;
        jlazy[2 * o + 1] += jlazy[o]; jlazy[2 * o + 1] %= P;
        sum[o] = sum[o] * clazy[o] + jlazy[o] * (r - l + 1); sum[o] %= P;
        clazy[o] = 1;
        jlazy[o] = 0;
        return;
    }
    void add_c(LL l, LL r, LL o){
        updata(l, r, o);
        if(x > r || y < l) return;
        if(x <= l && r <= y){
            clazy[o] = z;
            updata(l, r, o);
            return;
        }
        LL mid = (l + r) / 2;
        add_c(l, mid, 2 * o);
        add_c(mid + 1, r, 2 * o + 1);
        sum[o] = sum[2 * o] + sum[2 * o + 1]; sum[o] %= P;
        return;
    }
    void add_j(LL l, LL r, LL o){
        updata(l, r, o);
        if(x > r || y < l) return;
        if(x <= l && r <= y){
            jlazy[o] = z;
            updata(l, r, o);
            return;
        }
        LL mid = (l + r) / 2;
        add_j(l, mid, 2 * o);
        add_j(mid + 1, r, 2 * o + 1);
        sum[o] = sum[2 * o] + sum[2 * o + 1]; sum[o] %= P;
        return;
    }
    LL query(LL l, LL r, LL o){
        updata(l, r, o);
        if(x > r || y < l) return 0;
        if(x <= l && r <= y) return sum[o];
        LL mid = (l + r) / 2;
        LL ret = 0;
        ret += query(l, mid, 2 * o); ret %= P;
        ret += query(mid + 1, r, 2 * o + 1); ret %= P;
        sum[o] = sum[2 * o] + sum[2 * o + 1]; sum[o] %= P;
        return ret;
    }
} wt;
int main(){
    scanf("%lld%lld", &wt.N, &wt.P);
    for(LL i = 1; i <= wt.N; i ++){
        scanf("%lld", &wt.value[i]);
    }
    wt.build(1, wt.N, 1);
    LL q;
    scanf("%lld", &q);
    while(q --){
        LL a;
        scanf("%lld", &a);
        if(a == 1){
            scanf("%lld%lld%lld", &wt.x, &wt.y, &wt.z);
            wt.add_c(1, wt.N, 1);
        }
        else if(a == 2){
            scanf("%lld%lld%lld", &wt.x, &wt.y, &wt.z);
            wt.add_j(1, wt.N, 1);
        }
        else if(a == 3){
            scanf("%lld%lld", &wt.x, &wt.y);
            printf("%lld\n", wt.query(1, wt.N, 1));
        }
    }
    return 0;
}