首页 > 其他分享 >p3373

p3373

时间:2025-01-16 16:05:09浏览次数:3  
标签:int tree mid long 区间 now p3373

Description

如题,已知一个数列,你需要进行下面三种操作:

  • 将某区间每一个数乘上 xx;
  • 将某区间每一个数加上 xx;
  • 求出某区间每一个数的和。

Input

第一行包含三个整数 n,q,mn,q,m,分别表示该数列数字的个数、操作的总个数和模数。

第二行包含 nn 个用空格分隔的整数,其中第 ii 个数字表示数列第 ii 项的初始值。

接下来 qq 行每行包含若干个整数,表示一个操作,具体如下:

操作 11: 格式:1 x y k 含义:将区间 [x,y][x,y] 内每个数乘上 kk

操作 22: 格式:2 x y k 含义:将区间 [x,y][x,y] 内每个数加上 kk

操作 33: 格式:3 x y 含义:输出区间 [x,y][x,y] 内每个数的和对 mm 取模所得的结果

Output

输出包含若干行整数,即为所有操作 33 的结果。

Sample 1

InputcopyOutputcopy
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4
17
2

Hint

【数据范围】

对于 30%30% 的数据:n≤8n≤8,q≤10q≤10。
对于 70%70% 的数据:n≤103n≤103,q≤104q≤104。
对于 100%100% 的数据:1≤n≤1051≤n≤105,1≤q≤1051≤q≤105。

除样例外,m=571373m=571373。

#include <iostream>
using namespace std;

const int MAXN = 4e5 + 5; // 线段树的最大节点数,考虑n最大为10^5,4 * n即可
long long tree[MAXN];     // 存储线段树节点值
long long lazy[MAXN] = {0}; // 加法懒标记
long long lazy2[MAXN];    // 乘法懒标记
long long m;              // 模数

// 下推懒标记到子节点
void push_down(int now, int l, int r) {
    int mid = (l + r) >> 1; // 计算中间位置
    int lroot = now << 1;   // 左子节点索引
    int rroot = lroot | 1;  // 右子节点索引

    if (lazy2[now] != 1) {
        // 更新左右子节点的乘法懒标记和实际值
        lazy2[lroot] = (lazy2[lroot] * lazy2[now]) % m;
        lazy2[rroot] = (lazy2[rroot] * lazy2[now]) % m;
        lazy[lroot] = (lazy[lroot] * lazy2[now]) % m;
        lazy[rroot] = (lazy[rroot] * lazy2[now]) % m;
        tree[lroot] = (tree[lroot] * lazy2[now]) % m;
        tree[rroot] = (tree[rroot] * lazy2[now]) % m;
        lazy2[now] = 1; // 重置当前节点的乘法懒标记
    }
    if (lazy[now]) {
        // 更新左右子节点的加法懒标记和实际值
        lazy[lroot] = (lazy[lroot] + lazy[now]) % m;
        lazy[rroot] = (lazy[rroot] + lazy[now]) % m;
        tree[lroot] = (tree[lroot] + lazy[now] * ((mid - l + 1)) % m) % m;
        tree[rroot] = (tree[rroot] + lazy[now] * (r - mid) % m) % m;
        lazy[now] = 0; // 重置当前节点的加法懒标记
    }
}

// 构建线段树
void build_tree(int now, int l, int r) {
    if (l == r) {
        cin >> tree[now]; // 读取叶子节点的值
        tree[now] %= m;   // 对模数取余
    } else {
        int mid = (l + r) >> 1; // 计算中间位置
        int lroot = now << 1;   // 左子节点索引
        int rroot = lroot | 1;  // 右子节点索引
        build_tree(lroot, l, mid); // 递归构建左子树
        build_tree(rroot, mid + 1, r); // 递归构建右子树
        tree[now] = (tree[lroot] + tree[rroot]) % m; // 合并左右子树的结果
    }
}

// 区间乘法更新
void update_mul(int x, int y, int k, int now, int l, int r) {
    if (y < l || x > r) return; // 如果在所属区间外,直接返回
    if (x <= l && y >= r) { // 区间完全包含在内
        lazy2[now] = (lazy2[now] * k) % m; // 更新乘法懒标记
        lazy[now] = (lazy[now] * k) % m;   // 更新加法懒标记
        tree[now] = (tree[now] * k) % m;   // 更新当前节点的值
        return;
    }

    push_down(now, l, r); // 下推懒标记

    int mid = (l + r) >> 1; // 计算中间位置
    int lroot = now << 1;   // 左子节点索引
    int rroot = lroot | 1;  // 右子节点索引
    if (x <= mid) update_mul(x, y, k, lroot, l, mid); // 更新左子树
    if (y > mid) update_mul(x, y, k, rroot, mid + 1, r); // 更新右子树
    tree[now] = (tree[lroot] + tree[rroot]) % m; // 合并左右子树的结果
}

// 区间加法更新
void update_add(int x, int y, int k, int now, int l, int r) {
    if (y < l || x > r) return; // 如果在所属区间外,直接返回
    if (x <= l && y >= r) { // 区间完全包含在内
        lazy[now] = (lazy[now] + k) % m; // 更新加法懒标记
        tree[now] = (tree[now] + k * (r - l + 1) % m) % m; // 更新当前节点的值
        return;
    }

    push_down(now, l, r); // 下推懒标记

    int mid = (l + r) >> 1; // 计算中间位置
    int lroot = now << 1;   // 左子节点索引
    int rroot = lroot | 1;  // 右子节点索引
    if (x <= mid) update_add(x, y, k, lroot, l, mid); // 更新左子树
    if (y > mid) update_add(x, y, k, rroot, mid + 1, r); // 更新右子树
    tree[now] = (tree[lroot] + tree[rroot]) % m; // 合并左右子树的结果
}

// 区间求和查询
long long query(int x, int y, int now, int l, int r) {
    if (y < l || x > r) return 0; // 如果在所属区间外,返回0
    if (x <= l && y >= r) return tree[now]; // 区间完全包含在内,返回当前节点的值

    push_down(now, l, r); // 下推懒标记

    int mid = (l + r) >> 1; // 计算中间位置
    int lroot = now << 1;   // 左子节点索引
    int rroot = lroot | 1;  // 右子节点索引
    long long sum = 0;
    if (x <= mid) sum = (sum + query(x, y, lroot, l, mid)) % m; // 查询左子树
    if (y > mid) sum = (sum + query(x, y, rroot, mid + 1, r)) % m; // 查询右子树
    return sum;
}

int main() {
    int n, q;
    cin >> n >> q >> m;

    // 初始化 lazy2 数组为 1
    for (int i = 0; i < 4 * n; ++i) {
        lazy2[i] = 1;
    }

    // 初始化线段树(假设输入是1-indexed)
    build_tree(1, 1, n);

    for (int i = 0; i < q; ++i) {
        int Q;
        cin >> Q;
        if (Q == 1) {
            int x, y, k;
            cin >> x >> y >> k;
            update_mul(x, y, k, 1, 1, n); // 执行区间乘法更新
        } else if (Q == 2) {
            int x, y, k;
            cin >> x >> y >> k;
            update_add(x, y, k, 1, 1, n); // 执行区间加法更新
        } else if (Q == 3) {
            int x, y;
            cin >> x >> y;
            cout << query(x, y, 1, 1, n) << endl; // 执行区间求和查询
        }
    }

    return 0;
}



标签:int,tree,mid,long,区间,now,p3373
From: https://blog.csdn.net/2402_86997774/article/details/145184649

相关文章

  • 洛谷题单指南-线段树-P3373 【模板】线段树 2
    原题链接:https://www.luogu.com.cn/problem/P3373题意解读:对于序列a[n],支持三种操作:1.对区间每个数乘上一个数2.对区间每个数加上一个数3.求区间和解题思路:由于支持乘、加两种区间修改操作,是线段树的另一种典型应用:多个懒标记显然,这里需要两个懒标记,mul表示对子节点区间每个......
  • 线段树模板,洛谷原题P3373
    线段树区间乘、加,范围求和,QWQ原题#include<bits/stdc++.h>#definePIIpair<int,int>#defineintlonglong#defineDBdoublenamespaceFastIO{ inlineintread(intMOD,int&ret){ charch=getchar();intngtv=1; if(MOD==0){while(ch<&#......
  • P3373 【模板】线段树 2(区间乘+加操作,先乘后加原则)
    题目来源:https://www.luogu.com.cn/problem/P3373//题意:对区间[l,r]可以乘法,加法操作,查询和操作。//思路:既有乘法又有加法,肯定是要有两个标记。纯加法和纯乘法操作是很简单的,但是既有乘法又有加法涉及到先乘后加和先加后乘的顺序。//////所以现在是如何将先加后成也可以......
  • P3373 【模板】线段树 2
    原题链接code#include<bits/stdc++.h>usingnamespacestd;#definelllonglonglla[100005]={0};lllazyadd[400005]={0};lllazymul[400005]={0};lltree[400005]={0};lln,q,m;voidbuild(llnode,llstart,llend){lazyadd[node]=0;lazymul[no......
  • 【线段树入门】P3373 线段树 2(区间乘加)
    //笔记-自用//#pragmaGCCoptimize("Ofast")//#pragmaGCCoptimize("unroll-loops")#define_CRT_SECURE_NO_WARNINGS#defineAll(a)a.begin(),a.end()#defineINF2147483647#include<bits/stdc++.h>#include<numeric>usingnamespac......
  • P3373 【模板】线段树 2
    【模板】线段树2如题,已知一个数列,你需要进行下面三种操作:将某区间每一个数乘上\(x\);将某区间每一个数加上\(x\);求出某区间每一个数的和。输入格式第一行包含三个整数\(n,q,m\),分别表示该数列数字的个数、操作的总个数和模数。第二行包含\(n\)个用空格分隔的整数,其中第\(i\)......
  • 洛谷 P3373 总结
    洛谷P3373题意给定长度为\(n\)的整数序列,有以下三种操作共\(q\)次:将区间\([l,r]\)每一个数乘上\(k\);将区间\([l,r]\)每一个数加上\(k\);求出区间\([l,r]\)的区间和对\(m\)取模后的结果。\(1\leqslantn,q\leqslant10^5\)。思路这个题非常明确......
  • P3373 【模板】线段树 2
    【模板】线段树2如题,已知一个数列,你需要进行下面三种操作:将某区间每一个数乘上\(x\);将某区间每一个数加上\(x\);求出某区间每一个数的和。输入格式第一行包含三个整数\(n,q,m\),分别表示该数列数字的个数、操作的总个数和模数。第二行包含\(n\)个用空格分隔的整数,其......