洛谷P3373_template

开O2才可以进1s

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
int P;

using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(i64 x) : x(norm(x % P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

template < typename T, auto op, auto e, typename F, auto mapping, auto composition,
           auto e1 >
class segtree
{
    int n;
    vector< T > v;
    vector< F > lazy;
    void build(int now, int l, int r, T a[])
    {
        if(l == r)
        {
            v[now] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(now * 2, l, mid, a);
        build(now * 2 + 1, mid + 1, r, a);
        v[now] = op(v[now * 2], v[now * 2 + 1]);
    }
    void pushup(int k) { v[k] = op(v[k * 2], v[k * 2 + 1]); }
    void pushdown(int k, int l, int r)
    {
        v[k] = mapping(v[k], lazy[k], l, r);
        if (l != r) {
            lazy[k * 2] = composition(lazy[k * 2], lazy[k]);
            lazy[k * 2 + 1] = composition(lazy[k * 2 + 1], lazy[k]);
        }
        lazy[k] = e1();
    }

    void modify(int now, int ql, int qr, int l, int r, F x)
    {
        pushdown(now, l, r);
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            lazy[now] = x;
            pushdown(now, l, r);
            return;
        }
        modify(now * 2, ql, qr, l, (l + r) / 2, x);
        modify(now * 2 + 1, ql, qr, (l + r) / 2 + 1, r, x);
        pushup(now);
    }
    T query(int now, int ql, int qr, int l, int r)
    {
        pushdown(now, l, r);
        if (l > qr || r < ql) return e();
        if (l >= ql && r <= qr) return v[now];
        return op(query(now * 2, ql, qr, l, (l + r) / 2),
                  query(now * 2 + 1, ql, qr, (l + r) / 2 + 1, r));
    }

public:
    segtree(T a[], int n) : segtree(n)
    {
        build(1, 1, n, a);
    }
    segtree(int n)
    {
        this->n = n;
        v = vector< T >(n << 2, e());
        lazy = vector< F >(n << 2, e1());
    }

    void modify(int l, int r, F x) { modify(1, l, r, 1, n, x); }
    T query(int l, int r) { return query(1, l, r, 1, n); }
};

template<typename T>
T MAX(T x, T y) {if(x > y) return x; else return y;}
template<typename T>
T MIN(T x, T y) {if(x < y) return x; else return y;}
template<typename T>
T PLUS(T x, T y) {return x + y;}
template<typename T,typename D>
T LAZY(T x,T lazy,D l,D r){return x + (r - l + 1) * lazy;}

/*  Note:
    typename T, auto op, T e, 
    typename F, auto mapping, auto composition,
    F e1
*/
using segtree_add=segtree< ll, PLUS<ll>, [](){return 0ll;}, ll,[](ll x, ll lazy, int l, int r) { return x + (r - l + 1) * lazy; }, PLUS<ll>, [](){return 0ll;} >;
//using segtree_min=segtree< ll, MIN<ll>, (ll)1e9, ll,[](ll x, ll lazy, int l, int r) { return x+lazy; },PLUS<ll>, 0 >;
//using segtree_add=segtree< ll, PLUS<ll>, 0, ll,LAZY<ll,int>, PLUS<ll>, 0 >;
struct F{
    Z mul;    
    Z add;
};
using segtree_add_mul=segtree< Z, [](Z x, Z y) { return x + y; }, [](){return Z(0);}, 
     F, [](Z x, F t, int l, int r) { return x * t.mul + (r - l + 1) * t.add; },
     [](F t1, F t2)->F { return {(t1.mul * t2.mul), (t1.add * t2.mul + t2.add)}; }, 
     []()->F{return {1, 0};} >;
ll n,m;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>P;
    segtree_add_mul s(n);
    for(int i=1,x;i<=n;++i)cin>>x,s.modify(i,i,F{0,x});
    for(int i=1,op,x,y,z;i<=m;++i){
        cin>>op>>x>>y;
        if(op==1){
            cin>>z;
            s.modify(x,y,F{z,0});
        }else if(op==2){
            cin>>z;
            s.modify(x,y,F{1ll,z});
        }else {
            cout<<s.query(x,y)<<"\n";
        }
    }
}