线段树板子4

 

题目描述

现在给你一串数字，a1,a2,a3…an，你需要进行m次如下几种操作：

1 l r v，区间a[l]到a[r]的所有数字全部加v。

2 l r v，区间a[l]到a[r]的所有数字全部乘v。

3 l r，求区间a[l]到a[r]之间两两之间数字的乘积和(例如：2，3，4，5两两之间乘积和为 2*3+2*4+2*5+3*4+3*5+4*5)

现在给出你操作的顺序，按照要求操作或者输出。

输入描述:

第一行,一个数字T，表示有T组数据。

每组数据，第一行三个数值，n，m，p，表示有n个数字，有m个操作，p为模数，所有算术操作均要取模。

第二行，n个数字，表示初始序列

接下来m行，每行第一个数为操作方法opt，

若opt=1或者2，则后面跟着三个数l，r，v，若opt=3，则后面跟着两个数字l，r其含义如题所示

1≤T≤10,1≤n≤100000,1≤m≤200000,2≤p≤INT_MAX

保证所有输入均在int范围内，所有数字均为整数，其中p为素数，保证数据合法。

输出描述:

对于每次操作3，输出一行一个数字ans（mod p），表示答案。

示例1

输入

1
5 6 1000000007
0 0 0 0 0
1 1 5 1
3 1 5
2 2 4 2
2 3 3 2
3 1 3
3 1 1

输出

10
14
0

备注:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
long long mod;
long long A[MAXN];
struct tnode
{
    long long sum[2], lazy[2];
    int l, r;
};
tnode operator + (const tnode &A, const tnode &B)
{
    tnode C;
    C.l = A.l;
    C.r = B.r;
    C.lazy[0] = 1;
    C.lazy[1] = 0;
    C.sum[0] = A.sum[0] + B.sum[0];
    if (C.sum[0] >= mod)C.sum[0] -= mod;
    C.sum[1] = A.sum[1] + B.sum[1];
    if (C.sum[1] >= mod)C.sum[1] -= mod;
    C.sum[1] += A.sum[0] * B.sum[0] % mod;
    if (C.sum[1] >= mod)C.sum[1] -= mod;
    return C;
}
struct Segment_Tree
{
    tnode t[4 * MAXN];
    void init_lazy(int root)
    {
        t[root].lazy[0] = 1;
        t[root].lazy[1] = 0;
    }
    void union_lazy(int fa, int ch)
    {
        long long temp[2];
        temp[0] = t[fa].lazy[0] * t[ch].lazy[0] % mod;
        temp[1] = ((t[fa].lazy[0] * t[ch].lazy[1] % mod) + t[fa].lazy[1]) % mod;
        t[ch].lazy[0] = temp[0];
        t[ch].lazy[1] = temp[1];
    }
    void cal_lazy(int root)
    {
        long long len = (t[root].r - t[root].l + 1) % mod;
        t[root].sum[1] = (len * (len - 1) / 2 % mod * t[root].lazy[1] % mod * t[root].lazy[1] % mod +
                          t[root].lazy[0] * t[root].lazy[0] % mod * t[root].sum[1] % mod +
                          t[root].lazy[0] * t[root].lazy[1] % mod * (len - 1) % mod * t[root].sum[0] % mod) % mod;
        t[root].sum[0] = (len * t[root].lazy[1] % mod +
                          t[root].lazy[0] * t[root].sum[0] % mod) % mod;
        return;
    }
    void push_down(int root)
    {
        if (t[root].lazy[0] != 1 || t[root].lazy[1] != 0)
        {
            cal_lazy(root);
            if (t[root].l != t[root].r)
            {
                int ch = root << 1;
                union_lazy(root, ch);
                union_lazy(root, ch + 1);
            }
            init_lazy(root);
        }
    }
    void update (int root)
    {
        int ch = root << 1;
        push_down(ch);
        push_down(ch + 1);
        t[root] = t[ch] + t[ch + 1];
    }
    void build(int root, int l, int r)
    {
        t[root].l = l;
        t[root].r = r;
        init_lazy(root);
        if (l != r)
        {
            int mid = (l + r) >> 1;
            int ch = root << 1;
            build(ch, l, mid);
            build(ch + 1, mid + 1, r);
            update(root);
        }
        else
        {
            t[root].sum[0] = A[l] % mod;
            t[root].sum[1] = 0;
        }
    }
    void change(int root, int l, int r, long long delta, int op)
    {
        push_down(root);
        if (l == t[root].l && r == t[root].r)
        {
            t[root].lazy[op] = delta % mod;
            return;
        }
        int mid = (t[root].l + t[root].r) >> 1;
        int ch = root << 1;
        if (r <= mid)change(ch, l, r, delta, op);
        else if (l > mid)change(ch + 1, l, r, delta, op);
        else {change(ch, l, mid, delta, op); change(ch + 1, mid + 1, r, delta, op);}
        update(root);
    }
    tnode sum(int root, int l, int r)
    {
        push_down(root);
        if (t[root].l == l && t[root].r == r)
        {
            return t[root];
        }
        int mid = (t[root].l + t[root].r) >> 1;
        int ch = root << 1;
        if (r <= mid)return sum(ch, l, r);
        else if (l > mid)return sum(ch + 1, l, r);
        else return sum(ch, l, mid) + sum(ch + 1, mid + 1, r);
    }
};
Segment_Tree ST;
int n, m, op, l, r, T;
long long x;
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d %d %lld", &n, &m , &mod);
        for (int i = 1; i <= n; ++i)
        {
            scanf("%lld", &A[i]);
        }
        ST.build(1, 1, n);
        for (int _ = 1; _ <= m; ++_)
        {
            scanf("%d %d %d", &op, &l, &r);
            if (op <= 2)
            {
                scanf("%lld", &x);
                ST.change(1, l, r, x, 2 - op);
            }
            else
            {
                printf("%lld\n", ST.sum(1, l, r).sum[1]);
            }
        }
    }
    return 0;
}