LYDSY 1798

题目大意

暂无

题目解法

暂无

RTFC

#include <cctype>
#include <cstdio>
template <typename T>
inline void read(T &x)
{
    int ch = 0, flag = 1;
    x = 0;
    while (!isdigit(ch = getchar()))
        if (ch == '-') flag = -1;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    x *= flag;
}
const int N = 100010;
typedef long long i64;
i64 sum[N << 2], add[N << 2], mul[N << 2], a[N], ha;
#define avg(x, y) (x + ((y - x) >> 1))
#define L(x) ((x) << 1)
#define R(x) ((x) << 1 | 1)
inline void update(int x)
{
    sum[x] = (sum[L(x)] + sum[R(x)]) % ha;
}
void build(int k, int l, int r)
{
    mul[k] = 1;
    if (l == r - 1) return sum[k] = a[l], void();
    int m = avg(l, r);
    build(L(k), l, m);
    build(R(k), m, r);
    update(k);
}
inline void push_down(int k, int l, int r)
{
    if (l == r - 1) return;
    if (mul[k] != 1)
    {
        add[L(k)] = add[L(k)] * mul[k] % ha;
        add[R(k)] = add[R(k)] * mul[k] % ha;
        mul[L(k)] = mul[L(k)] * mul[k] % ha;
        mul[R(k)] = mul[R(k)] * mul[k] % ha;
        sum[L(k)] = sum[L(k)] * mul[k] % ha;
        sum[R(k)] = sum[R(k)] * mul[k] % ha;
        mul[k] = 1;
    }
    if (add[k] != 0)
    {
        int m = avg(l, r);
        sum[L(k)] = (sum[L(k)] + add[k] * (m - l)) % ha;
        sum[R(k)] = (sum[R(k)] + add[k] * (r - m)) % ha;
        add[L(k)] = (add[L(k)] + add[k]) % ha;
        add[R(k)] = (add[R(k)] + add[k]) % ha;
        add[k] = 0;
    }
}
void update_add(int k, int l, int r, int x, int y, int v)
{
    if (x <= l && r <= y)
    {
        add[k] = (add[k] + v) % ha;
        sum[k] = (sum[k] + v * (r - l)) % ha;
    }
    else
    {
        push_down(k, l, r);
        int m = avg(l, r);
        if (x < m) update_add(L(k), l, m, x, y, v);
        if (y > m) update_add(R(k), m, r, x, y, v);
        update(k);
    }
}
void update_mul(int k, int l, int r, int x, int y, int v)
{
    if (x <= l && r <= y)
    {
        mul[k] = (mul[k] * v) % ha;
        add[k] = (add[k] * v) % ha;
        sum[k] = (sum[k] * v) % ha;
    }
    else
    {
        push_down(k, l, r);
        int m = avg(l, r);
        if (x < m) update_mul(L(k), l, m, x, y, v);
        if (y > m) update_mul(R(k), m, r, x, y, v);
        update(k);
    }
}
i64 query(int k, int l, int r, int x, int y)
{
    push_down(k, l, r);
    if (x <= l && r <= y)
        return sum[k] % ha;
    else
    {
        int m = avg(l, r);
        i64 ret = 0;
        if (x < m) ret += query(L(k), l, m, x, y);
        if (y > m) ret += query(R(k), m, r, x, y);
        return ret % ha;
    }
}
int main()
{
    int n, q;
    read(n), read(ha);
    for (int i = 0; i < n; i++) read(a[i]);
    build(1, 0, n);
    read(q);
    while (q--)
    {
        int op, t, g, c;
        read(op), read(t), read(g), t--;
        if (op == 1)
            read(c), update_mul(1, 0, n, t, g, c);
        if (op == 2)
            read(c), update_add(1, 0, n, t, g, c);
        if (op == 3)
            printf("%lld\n", query(1, 0, n, t, g));
    }
    return 0;
}