标签归档:洛谷

洛谷 P4777 【模板】扩展中国剩余定理(EXCRT)

照着教程想了一下午,终于A了。。。
参考文章:
https://www.luogu.org/blog/niiick/solution-p4777
https://www.luogu.org/problemnew/solution/P4777
https://blog.csdn.net/xiaobian_/article/details/87949337

扩展欧几里得算法与中国剩余定理


https://www.cnblogs.com/yangsongyi/p/9867057.html
(快速乘规避溢出)
https://www.cnblogs.com/jt2001/p/6129914.html
https://blog.csdn.net/qq_39599067/article/details/81118467

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;
ll b[100005], a[100005]; //b是余数,a是模数
ll quickmultiply(ll a, ll b,ll mod) {
    if (b == 0)return 0;
    ll result = quickmultiply(a, b / 2, mod) % mod;
    result = 2*result%mod;
    if (b & 1)result = (result+a)%mod;
    return result;
}
ll ngcd(ll a, ll b) {
    return b == 0 ? a : ngcd(b, a % b);
}
ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
ll excrt() {
    ll lcm = a[1], ans = b[1];
    for (int i = 2; i <= n; i++) {
        ll k1, k2, K, mod = lcm;
        ll gcd = exgcd(lcm, a[i], k1, k2);
        ll minus = ((b[i] - ans) % a[i] + a[i]) % a[i];
        if ((minus % ngcd(lcm, a[i]) != 0))return -1;
        K = (quickmultiply(k1,(minus / gcd),(a[i] / gcd)) + a[i] / gcd) % (a[i] / gcd);
        lcm *= a[i] / gcd, ans = (K * mod + ans) % lcm;
    }
    return (ans % lcm + lcm) % lcm;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    cout<<excrt();
}

洛谷 P3381 【模板】最小费用最大流

参考链接:https://www.cnblogs.com/widerg/p/9394929.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int eN = 100005;
const int vN = 10005;
const int INF = 0x7f7f7f7f;
int n, m, s, t;
int ePtr = -1; //e的实际存储只能从偶数号顶点开始,奇数号顶点存储反向边
int to[eN << 1], nxt[eN << 1], value[eN << 1], cost[eN << 1];
int head[vN], dis[vN], minV[vN];
int preID[eN << 1], preNode[eN << 1];
bool inqueue[vN];
inline void createEdge(int u, int v, int w, int c) {
    to[++ePtr] = v;
    value[ePtr] = w;
    cost[ePtr] = c;
    nxt[ePtr] = head[u];
    head[u] = ePtr;
}
bool SPFA(int s, int t) {
    queue<int> q;
    memset(dis, 0x7f, sizeof(dis));
    memset(inqueue, false, sizeof(inqueue));
    memset(preID, -1, sizeof(preID));
    memset(preNode, -1, sizeof(preNode));
    memset(minV, 0x7f, sizeof(minV));
    dis[s] = 0;
    inqueue[s] = true;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        inqueue[x] = false;
        for (int i = head[x]; ~i; i = nxt[i]) {
            int dest = to[i];
            if (dis[dest] > dis[x] + cost[i] && value[i]) {
                dis[dest] = dis[x] + cost[i];
                minV[dest] = min(minV[x], value[i]);
                preID[dest] = i;
                preNode[dest] = x;
                if (!inqueue[dest]) {
                    inqueue[dest] = true;
                    q.push(dest);
                }
            }
        }
    }
    return dis[t] != INF;
}
void MinCostMaxFlow(int s, int t, int& maxflow, int& mincost) {
    while (SPFA(s, t)) {
        for (int i = t; i != s; i = preNode[i]) {
            value[preID[i]] -= minV[t];
            value[preID[i] ^ 1] += minV[t];
        }
        maxflow += minV[t];
        mincost += minV[t] * dis[t];
    }
}
int main() {
    memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, w, f;
        scanf("%d%d%d%d", &u, &v, &w, &f);
        createEdge(u, v, w, f);
        createEdge(v, u, 0, -f);//第0号边被占用,这条语句为反向边留下空间
    }
    int maxflow = 0, mincost = 0;
    MinCostMaxFlow(s, t, maxflow, mincost);
    printf("%d %d\n", maxflow, mincost);
}

洛谷 P3376 【模板】网络最大流

参考链接:https://www.cnblogs.com/widerg/p/9387909.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int eN = 100005;
const int vN = 10005;
const int INF = 0x7f7f7f7f;
int n, m, s, t;
int ePtr = -1; //e的实际存储只能从偶数号顶点开始,奇数号顶点存储反向边
int to[eN<<1], nxt[eN<<1], value[eN<<1];
int head[vN], dis[vN];
inline void createEdge(int u, int v, int w) {
    to[++ePtr] = v;
    value[ePtr] = w;
    nxt[ePtr] = head[u];
    head[u] = ePtr;
}
bool bfs(int s, int t) {
    queue<int> q;
    memset(dis, 0x7f, sizeof(dis));
    dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; ~i; i = nxt[i]) {
            int dest = to[i];
            if (dis[dest] == INF && value[i] != 0) {
                dis[dest] = dis[x] + 1;
                q.push(dest);
            }
        }
    }
    return dis[t] != INF;
}
int dfs(int x, int t, int maxflow) {
    if (x == t)return maxflow;
    int ans = 0;
    for (int i = head[x]; ~i; i = nxt[i]) {
        int dest = to[i];
        if (dis[dest] != dis[x] + 1 || value[i] == 0 || ans >= maxflow)continue;
        int f = dfs(dest, t, min(value[i], maxflow - ans));
        value[i] -= f;
        value[i ^ 1] += f;
        ans += f;
    }
    return ans;
}
int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t))ans += dfs(s, t, INF);
    return ans;
}
int main() {
    memset(head, -1, sizeof(head));
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        createEdge(u, v, w);
        createEdge(v, u, 0);//第0号边被占用,这条语句为下一个边留下空间
    }
    printf("%d", dinic(s, t));
}

洛谷 P3386 【模板】二分图匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<list>
#include<cmath>
#include<queue>
#include<unordered_set>
#include<unordered_map>
using namespace std;
int n, m, e;
vector<int> edges[2005];
bool visited[2005];
int match[2005];
bool biFind(int node) {
    if (visited[node])return false;
    visited[node] = true;
    for (int i = 0; i < edges[node].size(); i++) {
        if (!match[edges[node][i]] || biFind(match[edges[node][i]])) {
            match[node] = edges[node][i];
            match[edges[node][i]] = node;
            return true;
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> e;
    for (int i = 1; i <= e; i++) {
        int u, v;
        cin >> u >> v;
        if (u > n || v > m)continue;
        edges[u].push_back(v + n);
        edges[v + n].push_back(u);
    }
    int cnter = 0;
    for (int i = 1; i <= n; i++) {
        memset(visited, false, sizeof(visited));
        if (biFind(i))cnter++;
    }
    cout << cnter;
}

洛谷 P3379 【模板】最近公共祖先(LCA)重写

朴素算法:洛谷70分,O2 80分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<vector>
using namespace std;
int n, m, s;
vector<int> edges[500005];
int father[500005],depth[500005];
void dfs(int node, int fath) {
    father[node] = fath;
    depth[node] = depth[fath] + 1;
    for (int i = 0; i < edges[node].size(); i++) {
        if (edges[node][i] == fath)continue;
        dfs(edges[node][i], node);
    }
}
int query(int a, int b) {
    while (a != b) {
        if (depth[a] >= depth[b])a = father[a];
        else b = father[b];
    }
    return a;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    dfs(s, s);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        cout << query(a, b) << "\n";
    }
}

倍增:洛谷80分,O2 100分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<vector>
#include<algorithm>
#define MAXLOG 20
using namespace std;
int n, m, s;
vector<int> edges[500005];
int depth[500005];
int ancestor[500005][MAXLOG+2];
void dfs(int node, int fath) {
    ancestor[node][0] = fath;
    depth[node] = depth[fath] + 1;
    for (int i = 1; i <= MAXLOG; i++)ancestor[node][i] = ancestor[ancestor[node][i - 1]][i - 1];
    for (int i = 0; i < edges[node].size(); i++) {
        if (edges[node][i] == fath)continue;
        dfs(edges[node][i], node);
    }
}
int query(int a, int b) {
    if (depth[b] > depth[a])swap(a, b);
    for (int i = MAXLOG; ~i; i--)if (depth[ancestor[a][i]] >= depth[b])a = ancestor[a][i];
    if (a == b)return a;
    for (int i = MAXLOG; ~i; i--) if(ancestor[a][i]!=ancestor[b][i]){
        a = ancestor[a][i];
        b = ancestor[b][i];
    }
    return ancestor[a][0];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    dfs(s, s);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        cout << query(a, b) << "\n";
    }
}

Tarjan:洛谷70分,O2 100分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m, s;
vector<int> edges[500005],askPair[500005];
bool visited[500005];
int father[500005];
inline int _find(int node) {
    if (father[node]==-1)return node;
    return father[node] = _find(father[node]);
}
inline void _union(int x, int y) {
    if(_find(x)!=_find(y))father[_find(x)] = y;
}
struct ask {
    int u, v;
    int ans;
}asks[500005];
inline int checkV(int id,int node) {
    if (asks[id].u != node)return asks[id].u;
    return asks[id].v;
}
void dfs(int node,int fath) {
    for (int i = 0; i < edges[node].size(); i++) {
        if (edges[node][i] == fath)continue;
        dfs(edges[node][i],node);
        _union(edges[node][i], node);
    }
    visited[node] = true;
    for (int i = 0; i < askPair[node].size(); i++) {
        int v = checkV(askPair[node][i], node);
        if (visited[v])asks[askPair[node][i]].ans = _find(v);
    }
}
int main() {
    memset(father, -1, sizeof(father));
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        cin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    for (int i = 1; i <= m; i++) {
        cin >> asks[i].u >> asks[i].v;
        askPair[asks[i].u].push_back(i);
        askPair[asks[i].v].push_back(i);
    }
    dfs(s,s);
    for (int i = 1; i <= m; i++)cout << asks[i].ans << "\n";
}

洛谷 P1022 计算器的改良

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int ratio = 0, constant = 0;
#define IfLetter if (ch <= 'Z'&&ch >= 'A' || ch <= 'z'&&ch >= 'a')
#define IfNumber if (ch >= '0'&&ch <= '9' || ch=='+' || ch=='-')
int main() {
    char letter;
    char ch;
    int num = 0;
    bool flag = true;
    while ((ch = getchar()) != '\n') {
        IfNumber{ // number(maybe with variable)
            ungetc(ch, stdin);
            int re = scanf("%d", &num); //specially prepared for the testcase form like "-a"
            if (re == 0) {
                getchar();
                ratio -= (flag ? 1 : -1);
            }
            ch = getchar();
            IfLetter{
                ratio += num * (flag ? 1 : -1);
                letter = ch;
            }
            else {
                constant += num * (flag ? 1 : -1);
                ungetc(ch, stdin);
            }
            num = 0;
        }
        else IfLetter{ //pure variable without ratio
            letter = ch;
            ratio+=(flag ? 1 : -1);
        }
        else if (ch == '=') {
            flag = false;
        }
    }
    printf("%c=%.3lf", letter, -1.0*constant / ratio);
}

洛谷 P2114 [NOI2014]起床困难综合症

参看题解:
https://www.luogu.org/blog/user17941/solution-p2114
https://www.luogu.org/blog/user25845/solution-p2114

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int n, m, t[100005];
string s[100005];
int zero = 0, one = 0x7fffffff;
int ans = 0;
void process(int & x) {
    for (int i = 1; i <= n; i++) {
        switch (s[i][0]) {
        case 'A':
            x &= t[i];
            break;
        case 'O':
            x |= t[i];
            break;
        case 'X':
            x ^= t[i];
            break;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> s[i] >> t[i];
    process(zero);
    process(one);
    for (int i = 31; i >= 0; i--) {
        if (ans + (1 << i) > m)continue;
        if (!(zero&(1<<i))&&(one&(1 << i)))ans |= (1 << i);
    }
    process(ans);
    cout << ans;
}

洛谷 P1972 [SDOI2009]HH的项链

参考题解:https://www.luogu.org/blog/skylee/solution-p1972

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int arr[500005];
int c[500000];
int last[1000001];
int flag=0;
struct question{
    int id,l,r,ans;
    bool operator < (const question& q2) const{
        if(flag==0)return r<q2.r;
        else return id<q2.id;
    }
}qs[200005];
inline int lowbit(int i){
    return i&(-i);
}
int query(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
void update(int i,int v){
    while(i<=n){
        c[i]+=v;
        i+=lowbit(i);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>qs[i].l>>qs[i].r;
        qs[i].id=i;
    }
    sort(qs+1,qs+m+1);
    int ptr=1;
    for(int i=1;i<=m;i++){
        for(;ptr<=qs[i].r;ptr++){
            if(last[arr[ptr]]!=0)update(last[arr[ptr]],-1);
            update(last[arr[ptr]]=ptr,1);
        }
        qs[i].ans=query(qs[i].r)-query(qs[i].l-1);
    }
    flag=1;
    sort(qs+1,qs+m+1);
    for(int i=1;i<=m;i++){
        cout<<qs[i].ans<<endl;
    }
}

洛谷 P2023 [AHOI2009]维护序列

没啥说的,和上一道题一模一样。。只是把输入改掉就可以了。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
using namespace std;
struct segmentTree{
    typedef long long ll;
    const static int MAX=100000;
    ll MOD;
    ll v[4*MAX],aTg[4*MAX],mTg[4*MAX];
    inline static ll lson(ll r){return r*2;}
    inline static ll rson(ll r){return r*2+1;}
    void build(ll r,ll* a,ll s,ll e){
        aTg[r]=0;mTg[r]=1;
        if(s==e){v[r]=a[s]%MOD;return;}
        ll m=(s+e)>>1;
        build(lson(r),a,s,m);
        build(rson(r),a,m+1,e);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
    void pushDown(ll r,ll s,ll e){
        if(aTg[r]==0&&mTg[r]==1)return;
        ll m=(s+e)>>1;
        v[lson(r)]=(v[lson(r)]*mTg[r]%MOD+aTg[r]*(m-s+1)%MOD)%MOD;
        v[rson(r)]=(v[rson(r)]*mTg[r]%MOD+aTg[r]*(e-m)%MOD)%MOD;
        aTg[lson(r)]=(aTg[lson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        aTg[rson(r)]=(aTg[rson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        mTg[lson(r)]=(mTg[lson(r)]*mTg[r])%MOD;
        mTg[rson(r)]=(mTg[rson(r)]*mTg[r])%MOD;
        aTg[r]=0;mTg[r]=1;
    }
    ll query(ll r,ll cs,ll ce,ll qs,ll qe){
        if(qe<cs||ce<qs)return 0;
        if(qs<=cs&&ce<=qe)return v[r]%MOD;
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        return (query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe))%MOD;
    }
    void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv=0,ll mulv=1){
        if(ue<cs||ce<us)return;
        if(us<=cs&&ce<=ue){
            v[r]=(v[r]*mulv%MOD+addv*(ce-cs+1))%MOD;
            aTg[r]=(aTg[r]*mulv%MOD+addv)%MOD;
            mTg[r]=(mTg[r]*mulv)%MOD;
            return;
        }
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        update(lson(r),cs,cmd,us,ue,addv,mulv);
        update(rson(r),cmd+1,ce,us,ue,addv,mulv);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
}ST;
typedef long long ll;
ll n,m,p;
ll a[100005];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;
    ST.MOD=p;
    ST.build(1,a,1,n);
    for(int i=1;i<=m;i++){
        ll op,x,y,k;
        cin>>op;
        if(op==1||op==2){
            cin>>x>>y>>k;
            if(op==1)ST.update(1,1,n,x,y,0,k);
            else ST.update(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<ST.query(1,1,n,x,y)%p<<endl;
        }
    }
}

洛谷 P3373 【模板】线段树 2

总算写出来了。。。线段树同时维护乘法和加法,欢迎体验!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
using namespace std;
struct segmentTree{
    typedef long long ll;
    const static int MAX=100000;
    ll MOD;
    ll v[4*MAX],aTg[4*MAX],mTg[4*MAX];
    inline static ll lson(ll r){return r*2;}
    inline static ll rson(ll r){return r*2+1;}
    void build(ll r,ll* a,ll s,ll e){
        aTg[r]=0;mTg[r]=1;
        if(s==e){v[r]=a[s]%MOD;return;}
        ll m=(s+e)>>1;
        build(lson(r),a,s,m);
        build(rson(r),a,m+1,e);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
    void pushDown(ll r,ll s,ll e){
        if(aTg[r]==0&&mTg[r]==1)return;
        ll m=(s+e)>>1;
        v[lson(r)]=(v[lson(r)]*mTg[r]%MOD+aTg[r]*(m-s+1)%MOD)%MOD;
        v[rson(r)]=(v[rson(r)]*mTg[r]%MOD+aTg[r]*(e-m)%MOD)%MOD;
        aTg[lson(r)]=(aTg[lson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        aTg[rson(r)]=(aTg[rson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        mTg[lson(r)]=(mTg[lson(r)]*mTg[r])%MOD;
        mTg[rson(r)]=(mTg[rson(r)]*mTg[r])%MOD;
        aTg[r]=0;mTg[r]=1;
    }
    ll query(ll r,ll cs,ll ce,ll qs,ll qe){
        if(qe<cs||ce<qs)return 0;
        if(qs<=cs&&ce<=qe)return v[r]%MOD;
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        return (query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe))%MOD;
    }
    void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv=0,ll mulv=1){
        if(ue<cs||ce<us)return;
        if(us<=cs&&ce<=ue){
            v[r]=(v[r]*mulv%MOD+addv*(ce-cs+1))%MOD;
            aTg[r]=(aTg[r]*mulv%MOD+addv)%MOD;
            mTg[r]=(mTg[r]*mulv)%MOD;
            return;
        }
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        update(lson(r),cs,cmd,us,ue,addv,mulv);
        update(rson(r),cmd+1,ce,us,ue,addv,mulv);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
}ST;
typedef long long ll;
ll n,m,p;
ll a[100005];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    ST.MOD=p;
    ST.build(1,a,1,n);
    for(int i=1;i<=m;i++){
        ll op,x,y,k;
        cin>>op;
        if(op==1||op==2){
            cin>>x>>y>>k;
            if(op==1)ST.update(1,1,n,x,y,0,k);
            else ST.update(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<ST.query(1,1,n,x,y)%p<<endl;
        }
    }
}