首页 > 其他分享 >1277. 维护序列

1277. 维护序列

时间:2024-03-07 09:01:32浏览次数:21  
标签:int res 更新 1277 pushdown tag 序列 维护 include

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#define For(i, j, n) for(int i = j ; i <= n ; ++i)
using namespace std;

typedef long long LL;

const int N = 1e5 + 5;

int n, m, P, a[N];

struct node{
    int l, r;
    int add, mul, sum;
}tr[N<<2];

void pushup(node &u, node &l, node &r)
{
    u.sum = ((LL)l.sum + r.sum) % P;
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void pushdown(node &u, node &l, node &r)
{
    l.sum = ((LL)l.sum * u.mul + (LL)u.add * (l.r - l.l + 1)) % P;
    l.mul = (LL)l.mul * u.mul % P;
    l.add = (LL)l.add * u.mul % P;
    l.add = (LL)l.add + u.add % P;
    r.sum = ((LL)r.sum * u.mul + (LL)u.add * (r.r - r.l + 1)) % P;
    r.mul = (LL)r.mul * u.mul % P;
    r.add = (LL)r.add * u.mul % P;
    r.add = (LL)r.add + u.add % P;
    u.add = 0; u.mul = 1;
}

void pushdown(int u)
{
    pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

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

void modify(int u, int l, int r, int m, int a)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum = ((LL)tr[u].sum * m + (LL)a * (tr[u].r - tr[u].l + 1)) % P;
        tr[u].mul = (LL)m * tr[u].mul % P;
        tr[u].add = (LL)m * tr[u].add % P;
        tr[u].add = (LL)a + tr[u].add % P;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if(l <= mid) modify(u << 1, l, r, m, a);
    if(r > mid) modify(u << 1 | 1, l, r, m, a);
    pushup(u);
}

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

int main()
{
    scanf("%d%d", &n, &P);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    scanf("%d", &m);
    build(1, 1, n);
    int l, r, c, flag;
    while(m--)
    {
        scanf("%d", &flag);
        if(flag == 1)
        {
            scanf("%d%d%d", &l, &r, &c);
            modify(1, l, r, c, 0);
        }
        else if(flag == 2)
        {
            scanf("%d%d%d", &l, &r, &c);
            modify(1, l, r, 1, c);
        }
        else
        {
            scanf("%d%d", &l, &r);
            printf("%d\n", query(1, l, r));
        }
    }
    return 0;
}

注意懒标记的意义是:tag[u]表示要对u的所有子孙做的操作,因此在更新节点u的值时,是先更新sum,再更新tag

另外,由于这道题更新节点信息的操作被多次使用,我们可以把他封装成一个函数

标签:int,res,更新,1277,pushdown,tag,序列,维护,include
From: https://www.cnblogs.com/smartljy/p/18058093

相关文章

  • Java 枚举(Enums)解析:提高代码可读性与易维护性
    接口在Java中,实现抽象的另一种方式是使用接口。接口定义接口是一个完全抽象的类,用于将具有空方法体的相关方法分组://接口interfaceAnimal{publicvoidanimalSound();//接口方法(没有具体实现体)publicvoidrun();//接口方法(没有具体实现体)}实现接口要访问......
  • 106. 从中序与后序遍历序列构造二叉树 c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/structTreeNode*buidl_tree(int*inorder,inthead1,intn1,int*postorder,inthead2,intn2){if(n1<......
  • PHP反序列化漏洞
    0x00何为类和对象说到序列化和反序列化就不得不提到两个词:类和对象那么什么是类,什么是对象教科书式的答案是类是对象的抽象,对象是类的实例那啥叫个抽象,啥叫个实例呢简单的说,类就是对象的一个标准模板,而对象就是按照模板做出来的实物举个栗子人,是一个类所有的人都有一个......
  • day56 动态规划part13 代码随想录算法训练营 674. 最长连续递增序列
    题目:674.最长连续递增序列我的感悟:网速快是不一样!!这个题别看简单,写不出递推公式也白搭理解难点:递推公式,是只跟昨天的比,如果没有,就重新计算!听课笔记:我的代码:classSolution:deffindLengthOfLCIS(self,nums:List[int])->int:dp=[1]*len(nums)......
  • day56 动态规划part13 代码随想录算法训练营 300. 最长递增子序列
    题目:300.最长递增子序列我的感悟:之前做过,都忘记了,这次好好记思路理解难点:dp[i]是由昨天的历史遍历后,得到今天的值 听课笔记:我的代码:classSolution:deflengthOfLIS(self,nums:List[int])->int:#难点是dp的推导公式,#dp[i]是截止到n......
  • 神舟数据库日常维护
    1.查看所有配置SQL>showall; 2.查看具体某个参数SQL>showmax_connections;name|setting--------------------------+---------MAX_CONNECTIONS|200MAX_CONNECTIONS_PER_USER|0SQL>showNAME_CASE_SENSITIVE;name......
  • 记一次openfeign反序列化异常复盘
    前言之前业务部门有2个通用响应类,一个是负责和前端交互的响应类AjaxResult,一个是负责和后端RPC接口交互的响应类RpcResult。一开始这两个响应类的值字段都一样,形如下 privateBooleansuccess; privateStringmessage; privateIntegercode; privateTdata;因为前端和......
  • R:基因的蛋白序列多行转单行
    从Phytozome上导出来的,这个用于后续的基因家族分析,通过此脚本将序列变为一行#清除所有变量rm(list=ls())#设置工作目录setwd("C:/Users/Administrator/Desktop")#定义读取和处理序列数据的函数process_sequences<-function(file_path){#读取文件内容lines......
  • R语言多元Copula GARCH 模型时间序列预测|附代码数据
    原文链接  http://tecdat.cn/?p=2623原文出处:拓端数据部落公众号 最近我们被要求撰写关于CopulaGARCH的研究报告,包括一些图形和统计输出。和宏观经济数据不同,金融市场上多为高频数据,比如股票收益率序列。直观的来说,后者是比前者“波动”更多且随机波动的序列,在一元或多元......
  • 基因序列中的一些名词区别
      1.基因分为编码区和非编码区,编码区包含外显子和内含子,一般非编码区具有基因表达的调控功能,如启动子在非编码区。编码区则转录为mRNA并最终由外显子部分翻译成多肽(蛋白质)。2. 内含子(intron)是真核生物细胞DNA中的间插序列。这些序列被转录在前体RNA中,经过剪接被去除,最终不存......