bzoj1798
题目描述：给定n个数的序列，有三种操作。 1、将一段区间乘上c 2、将一段区间加上c 3、求一段区间的和
输入格式：第一行两个整数第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作1：“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c(1≤t≤g≤N,0≤c≤1000000000)。 操作2：“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3：“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
输出格式：对每个操作3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。
输入样例： 7 43 1 2 3 4 5 6 7 5 1 2 5 5 3 2 4 2 3 7 9 3 1 3 3 4 7
输出样例： 2 35 8
解析：线段树的模板题。关键在于如何处理线段树的乘和加。 可以将每一个数变为\(a \times b + c\) 的形式，在每一次乘的修改时，直接将和乘c，并将加和乘的标记都乘c即可。而加的修改则只需要将加的标记加上c即可。 在标记下传时，将该点子树的乘标记乘上该点的乘标记；将子树的加标记先乘上该点的乘标记，再加上该点的加标记即可。
代码如下：
#include<cstdio> #define lc o << 1 #define rc o << 1 | 1 using namespace std; const int maxn = 1e5 + 5; int n, m, p, a[maxn], sum[maxn << 2], bj1[maxn << 2], bj2[maxn << 2]; //bj1:乘标记，bj2:加标记 int read(void) { char c; while (c = getchar(), c < '0' || c >'9'); int x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x; } void build(int o, int l, int r) { //建树 bj1[o] = 1; //乘标记的初始值为1 if (l == r) { sum[o] = a[l] % p; return; } int mid = l + r >> 1; build(lc, l, mid); build(rc, mid + 1, r); sum[o] = (sum[lc] + sum[rc]) % p; } void pushdown(int o, int l, int r) { //标记下传 int mid = l + r >> 1; sum[lc] = 1ll * sum[lc] * bj1[o] % p; sum[lc] += 1ll * bj2[o] * (mid - l + 1) % p; sum[lc] %= p; sum[rc] = 1ll * sum[rc] * bj1[o] % p; sum[rc] += 1ll * bj2[o] * (r - mid) % p; sum[rc] %= p; bj1[lc] = 1ll * bj1[lc] * bj1[o] % p; bj1[rc] = 1ll * bj1[rc] * bj1[o] % p; bj2[lc] = 1ll * bj2[lc] * bj1[o] % p; bj2[lc] = (bj2[lc] + bj2[o]) % p; bj2[rc] = 1ll * bj2[rc] * bj1[o] % p; bj2[rc] = (bj2[rc] + bj2[o]) % p; bj1[o] = 1; bj2[o] = 0; } void modify1(int o, int l, int r, int ql, int qr,int c) { if (ql <= l && qr >= r) { //两个标记都要乘上c sum[o] = 1ll * sum[o] * c % p; bj1[o] = 1ll * bj1[o] * c % p; bj2[o] = 1ll * bj2[o] * c % p; return; } int mid = l + r >> 1; if (bj1[o] != 1 || bj2[o]) pushdown(o, l, r); if (ql <= mid) modify1(lc, l, mid, ql, qr, c); if (qr > mid) modify1(rc, mid + 1, r, ql, qr, c); sum[o] = (sum[lc] + sum[rc]) % p; } void modify2(int o, int l, int r, int ql, int qr, int c) { if (ql <= l && qr >= r) { //加标记直接加上c sum[o] += 1ll * c * (r - l + 1) % p; sum[o] %= p; bj2[o] = (bj2[o] + c) % p; return; } int mid = l + r >> 1; if (bj1[o] != 1 || bj2[o]) pushdown(o, l, r); if (ql <= mid) modify2(lc, l, mid, ql, qr, c); if (qr > mid) modify2(rc, mid + 1, r, ql, qr, c); sum[o] = (sum[lc] + sum[rc]) % p; } int query(int o, int l, int r, int ql, int qr) { if (ql <= l && qr >= r) return sum[o]; int mid = l + r >> 1, ans = 0; if (bj1[o] != 1 || bj2[o]) pushdown(o, l, r); if (ql <= mid) ans += query(lc, l, mid, ql, qr); ans %= p; if (qr > mid) ans += query(rc, mid + 1, r, ql, qr); ans %= p; return ans; } int main() { n = read(); p = read(); for (int i = 1; i <= n; ++ i) a[i] = read(); build(1, 1, n); m = read(); while (m --) { int opt = read(); if (opt == 1) { int x = read(), y = read(), c = read(); modify1(1, 1, n, x, y, c); } else if (opt == 2) { int x = read(), y = read(), c = read(); modify2(1, 1, n, x, y, c); } else { int x = read(), y = read(); printf("%d\n", query(1, 1, n, x, y)); } } return 0; }转载于:https://www.cnblogs.com/Gaxc/p/9979278.html
相关资源：JAVA上百实例源码以及开源项目