P3373求调（麻风优良，分块)）

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[100005], plu[100005], sum[100005], mul[100005];
int n, q, f, s, m;
int belong(int x)
{
    return (x + s - 1) / s;
}
int sm(int x, int y)
{
    int bx = belong(x), by = belong(y), ans = 0;
    if(bx == by)
    {
        for(int i = x; i <= y; i++)
            ans += a[i] * mul[i] + plu[bx], ans %= m;
    }
    else
    {
        for(int i = x; i <= bx * s; i++)
            ans += a[i] * mul[bx] + plu[bx], ans %= m;
        for(int i = (by - 1) * s + 1; i <= y; i++)
            ans += a[i] * mul[by] + plu[by], ans %= m;
        for(int i = bx + 1; i <= by - 1; i++)
            ans += sum[i] % m, ans %= m;
    }
    return ans % m;
}
void pl(int x, int y, int k)
{
    int bx = belong(x), by = belong(y);
    if(bx == by)
    {
        sum[bx] -= sm(x, y);
        for(int i = x; i <= y; i++)
            a[i] += k * mul[bx], a[i] %= m;
        sum[bx] += sm(x, y);
        sum[bx] %= m;
    }
    else
    {
        sum[bx] -= sm(x, bx * s);
        for(int i = x; i <= bx * s; i++)
            a[i] += k * mul[bx], a[i] %= m;
        sum[bx] += sm(x, bx * s);
        sum[bx] %= m;
        sum[by] -= sm((by - 1) * s + 1, y);
        for(int i = (by - 1) * s + 1; i <= y; i++)
            a[i] += k * mul[by], a[i] %= m;
        sum[by] += sm((by - 1) * s + 1, y);
        sum[by] %= m;
        for(int i = bx + 1; i <= by - 1; i++)
        {
            plu[i] += k * mul[i];
            sum[i] += s * k * mul[i];
            sum[i] %= m;
            plu[i] %= m;
        }
    }
}
void ml(int x, int y, int k)
{
    int bx = belong(x), by = belong(y);
    if(bx == by)
    {
        sum[bx] -= sm(x, y);
        for(int i = x; i <= y; i++)
            a[i] *= k, a[i] %= m;
        sum[bx] += sm(x, y);
    }
    else
    {
        sum[bx] -= sm(x, bx * s);
        for(int i = x; i <= bx * s; i++)
            a[i] *= k, a[i] %= m;
        sum[bx] += sm(x, bx * s);
        sum[by] -= sm((by - 1) * s + 1, y);
        for(int i = (by - 1) * s + 1; i <= y; i++)
            a[i] *= k, a[i] %= m;
        sum[by] += sm((by - 1) * s + 1, y);
        for(int i = bx + 1; i <= by - 1; i++)
        {
            mul[i] *= k;
            plu[i] *= k;
            sum[i] = sum[i] * mul[i] + plu[i];
            sum[i] %= m;
            plu[i] %= m;
            mul[i] %= m;
        }
    }
}
signed main()
{
    cin >> n >> q >> m;
    f = sqrt(n), s = n / f;
    for(int i = 1; i <= n; i++)
        cin >> a[i], sum[belong(i)] += a[i], sum[belong(i)] %= m, mul[i] = 1;
    while(q--)
    {
        int opt, x, y;
        cin >> opt >> x >> y;
        if(opt == 2)
        {
            int k;
            cin >> k;
            pl(x, y, k);
        }
        else if(opt == 1)
        {
            int k;
            cin >> k;
            ml(x, y, k);
        }
        else 
            cout << sm(x, y) << '\n';
    }
}