题目

WA #2 #9 #10

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;

int w[N];
struct Tree { 
	int l, r;
	LL sum, add, mu; 
}tr[N * 4];
int n, m;
LL p;

int M (int l, int r) {return l + ((r - l) >> 1);}

void pushup (int u) {
	tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}

void pushdown (int u) {
	if (tr[u].add || (tr[u].mu >> 1)) {
		Tree &root = tr[u], &left = tr[u<<1], &right = tr[u<<1|1];
		left.add = (left.add * root.mu + root.add) % p;
		left.mu = (left.mu * root.mu) % p;
		left.sum = (left.sum * root.mu % p + (LL)(left.r - left.l + 1) * root.add % p)%p;
		
		right.add = (right.add * root.mu + root.add) % p;
		right.mu = (right.mu * root.mu) % p;
		right.sum = (right.sum * root.mu % p + (LL)(right.r - right.l + 1) * root.add % p)%p;
	
		root.add = 0; root.mu = 1;
	} 
}

void build (int u, int l, int r) {
	if (l == r) {
		tr[u] = (Tree){l, r, w[l], 0, 1};
		return;
	}
	tr[u] = (Tree){l, r, 0, 0, 1}; 
	int mid = M (l, r);
	build (u << 1, l, mid);
	build (u << 1 | 1, mid + 1, r);
	pushup (u);
}

void modify1 (int u, int l, int r, int k) {
	if (l <= tr[u].l && tr[u].r <= r) {
		tr[u].add = (tr[u].add * k) % p;
		tr[u].mu = (tr[u].mu * k) % p;
		tr[u].sum = (tr[u].sum * k) % p;
		return;
	}
	pushdown (u);
	int mid = M (tr[u].l, tr[u].r);
	if (l <= mid) modify1 (u << 1, l, r, k);
	if (r > mid) modify1 (u << 1 | 1, l, r, k);
	pushup (u);
}

void modify2 (int u, int l, int r, int k) {
	if (l <= tr[u].l && tr[u].r <= r) {
		tr[u].add = (tr[u].add + k) % p;
		tr[u].sum = (tr[u].sum + (LL)(tr[u].r - tr[u].l + 1) * k % p) % p;
		return;
	}
	pushdown (u);
	int mid = M (tr[u].l, tr[u].r);
	if (l <= mid) modify2 (u << 1, l, r, k);
	if (r > mid) modify2 (u << 1 | 1, l, r, k);
	pushup (u);
}

LL query (int u, int l, int r) {
	if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
	pushdown (u);
	int mid = M (tr[u].l, tr[u].r);
	LL v = 0;
	if (l <= mid) v = query (u << 1, l, r) % p;
	if (r > mid) v = (v + query (u << 1 | 1, l, r)) % p;
	return v;
}


int main(){
	scanf ("%d%d%lld", &n, &m, &p);
	for (int i = 1; i <= n; i ++ ) 
		scanf ("%d", &w[i]);
	build (1, 1, n);
	
	int q, x, y, k;
	for (int i = 1; i <= m; i ++ ) {
		scanf ("%d%d%d", &q, &x, &y);
		if (q == 1) {
			scanf ("%d", &k);
			modify1 (1, x, y, k);
		}
		else if (q == 2) {
			scanf ("%d", &k);
			modify2 (1, x, y, k);
		}
		else printf ("%lld\n", query (1, x, y));
	} 
    return 0;
}