Java P3373 【模板】线段树 2

Java P3373 【模板】线段树 2

题目链接
多敲几遍，打发时间

// czl
import java.util.*;
import java.io.*;
public class Main 
{
	static class Node {
		int l, r;
		long sum;
		long mul, add; // 懒标记
	}
	static int N = 100010, MOD;	
	
	static Node tr[] = new Node[4 * N];
	static int a[] = new int[N];
	static int n, m;
	
	static void pushup(int u) {
		tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
		tr[u].sum %= MOD;
	}
	
	static void pushdown(int u) {
		eval(tr[u << 1], tr[u].mul, tr[u].add);
		eval(tr[u << 1 | 1], tr[u].mul, tr[u].add);
		tr[u].mul = 1;
		tr[u].add = 0;
	}	
	
	static void eval(Node u ,long mul, long add) {
		u.sum = u.sum * mul + (u.r - u.l + 1) * add;
		u.sum %= MOD;
		u.mul = u.mul * mul % MOD;
		u.add = u.add * mul + add;
		u.add %= MOD;
	}
	
	static void build(int u, int l, int r) {
		tr[u] = new Node();
		tr[u].l = l; tr[u].r = r; tr[u].mul = 1;
		if(l == r) {
			tr[u].sum = a[l];
			return;
		}
		int mid = l + r >> 1;
		build(u << 1, l, mid);
		build(u << 1 | 1, mid + 1, r);
		pushup(u);
	}
	
	static void modify(int u, int l, int r, long mul, long add) {
		if(tr[u].l >= l && tr[u].r <= r) {
			eval(tr[u], mul, add);
			return;
		}
		pushdown(u);
		int mid = tr[u].l + tr[u].r >> 1;
		if(l <= mid) modify(u << 1, l, r, mul, add);
		if(r > mid) modify(u << 1 | 1, l, r, mul, add);
		pushup(u);
	}
	
	static long query(int u, int l, int r) {
		if(tr[u].l >= l && tr[u].r <= r) {
			return tr[u].sum % MOD;
		}
		pushdown(u);
		int mid = tr[u].l + tr[u].r >> 1;
		long res = 0;
		if(l <= mid) res += query(u << 1, l, r);
		if(r > mid) res += query(u << 1 | 1, l, r);
		return res % MOD;
	}
	
    public static void main(String[] args) {
        InputReader sc = new InputReader(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        MOD = sc.nextInt();
        
        for(int i = 1; i <= n; i ++ )
        	a[i] = sc.nextInt();
        
        build(1, 1, n);
        
        while(m -- > 0) {
        	int p = sc.nextInt();
        	int l = sc.nextInt();
        	int r = sc.nextInt();
        	if(p == 1) {
        		int k = sc.nextInt();
        		modify(1, l, r, k, 0);
        	}
        	else if(p == 2) {
        		int k = sc.nextInt();
        		modify(1, l, r, 1, k);
        	}
        	else if(p == 3)
        		System.out.println(query(1, l, r));
        }
    }
    
    // 快读板子
    static class InputReader {
        public BufferedReader br;
        public StringTokenizer st;

        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream), 32768);
            st = null;
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        
        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}