11546: 【原1546】ecneuqes

题目描述

author: AHOI 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1546

Description

有长为\(N\)的数列\(a_1,a_2,\cdots,a_N\), 有如下三种操作形式: 1. 把数列中的一段数全部乘一个值. 2. 把数列中的一段数全部加一个值. 3. 询问数列中的一段数的和. 由于答案可能很大，你只需输出这个数模\(P\)的值.

Input Format

第一行两个整数\(N\)和\(P\).

第二行含有\(N\)个非负整数,从左到右依次为\(a_1,a_2,\cdots,a_N \).

第三行有一个整数\(M\), 表示操作总数.

从第四行开始每行描述一个操作, 输入的操作有以下三种形式: 操作1：1 t g c.表示把所有满足\(t\leq i \leq g\)的\(a_i\)改为\(a_i\times c\). 操作2：2 t g c.表示把所有满足\(t\leq i \leq g\)的\(a_i\)改为\(a_i+ c\). 操作3：3 t g.询问所有满足\(t\leq i \leq g\)的\(a_i\)的和模\(P\)的值\(t\leq i \leq g\). 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格.

Output Format

共一行，包含一个整数表示答案。

Sample Input 1

5 19260817
976 997 1022 237 252
5
2 1 3 1000
3 3 3
1 3 5 8
3 4 5
3 1 4

Sample Output 1

2022
3912
22045

Sample Input 2

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

Sample Output 2

2
35
8

Limits

对于\(100\%\)的数据, \(n\leq 100000, q\leq 10^9, a_i\leq 10^9\).

\(20\%\)的数据满足, \(n \leq 1000\).

\(20\%\)的数据满足只有加法操作.

\(20\%\)的数据满足: 单点修改, 区间查询.

yyong119's solution

#include <cstdio>
#include <iostream>
using namespace std;
inline const int getint() {
    int r = 0, k = 1;
    char c = getchar();
    for (; c<'0' || c>'9'; c = getchar()) if (c == ' - ') k = -1;
    for (; c >= '0'&&c <= '9'; c = getchar()) r = r * 10 + c - '0';
    return k*r;
}

const int N = 100010;
int n, MD;

struct node {
    int sum, add, mul;
    void upd(int a, int m, int len) {
        add = ((long long)add*m + a) % MD;
        mul = ((long long)mul*m) % MD;
        sum = ((long long)sum*m + (long long)a*len) % MD;
    }
}t[N << 2];

void pushdown(int x, int len) {
    if (t[x].add != 0 || t[x].mul != 1)
        t[x << 1].upd(t[x].add, t[x].mul, (len - (len >> 1))),
        t[x << 1 | 1].upd(t[x].add, t[x].mul, len >> 1),
        t[x].add = 0, t[x].mul = 1;
}

void pushup(int x) {
    t[x].sum = (t[x << 1].sum + t[x << 1 | 1].sum) % MD; 
}
void build(int l, int r, int x) {
    t[x].add = 0;
    t[x].mul = 1;
    if (l == r) { t[x].sum = getint(); return; }
    int mid = (l + r) >> 1;
    build(l, mid, x << 1); build(mid + 1, r, x << 1 | 1);
    pushup(x);
}

void update(int l, int r, int x, int L, int R, int add, int mul) {
    if (L <= l && r <= R) { t[x].upd(add, mul, r - l + 1); return; }
    pushdown(x, r - l + 1);
    int mid = (l + r) >> 1;
    if (L <= mid) update(l, mid, x << 1, L, R, add, mul);
    if (mid<R) update(mid + 1, r, x << 1 | 1, L, R, add, mul);
    pushup(x);
}

int query(int l, int r, int x, int L, int R) {
    if (L <= l && r <= R) return t[x].sum;
    pushdown(x, r - l + 1);
    int mid = (l + r) >> 1, ret = 0;
    if (L <= mid) ret += query(l, mid, x << 1, L, R);
    if (mid<R) ret += query(mid + 1, r, x << 1 | 1, L, R);
    ret %= MD;
    return ret;
}

int main() {
    scanf("%d%d", &n, &MD);
    build(1, n, 1);
    int m;
    scanf("%d", &m);
    while (m--) {
        int c;
        scanf("%d", &c);
        int l, r, x;
        switch (c) {
            case 1:
                scanf("%d%d%d", &l, &r, &x);
                update(1, n, 1, l, r, 0, x);
                break;
            case 2:
                scanf("%d%d%d", &l, &r, &x);
                update(1, n, 1, l, r, x, 1);
                break;
            case 3:
                scanf("%d%d", &l, &r);
                printf("%d\n", query(1, n, 1, l, r));
                break;
        }
    }
    return 0;
}