首页 > 其他分享 >二次差分维护

二次差分维护

时间:2022-12-14 11:14:37浏览次数:68  
标签:二次 int upd tr 差分 ur ul 维护 mod

原理类似,用线段树来维护区间求和,只是一个是一次差分的值,一个是二次差分的值

P1438 无聊的数列

每次加上等差数列,单点查询

#include <bits/stdc++.h>
using namespace std;
#define ul (u<<1)
#define ur (u<<1|1)
#define len(u) (tr[u].r-tr[u].l+1)
#define mid (tr[u].l+tr[u].r>>1)
#define int long long
const int M=1e6+5;

struct Tree {
    int l,r;
    int s,la;
}tr[M<<2];
int a[M];

void pu(int u) {
    tr[u].s=tr[ul].s+tr[ur].s;
}

void pd(int u) {
    if(tr[u].la==0)return ;
    tr[ul].la+=tr[u].la;
    tr[ur].la+=tr[u].la;
    tr[ul].s+=len(ul)*tr[u].la;
    tr[ur].s+=len(ur)*tr[u].la;
    tr[u].la=0;
}

void build(int u,int l,int r) {
    tr[u]={l,r,0,0};
    if(l==r){tr[u].s=a[l];return ;}
    build(ul,l,mid);build(ur,mid+1,r);
    pu(u);
}

void up(int u,int l,int r,int c) {
    if(tr[u].l>=l&&tr[u].r<=r) {
        tr[u].s+=len(u)*c;
        tr[u].la+=c;
        return ;
    }
    pd(u);
    if(l<=mid)up(ul,l,r,c);
    if(r>mid)up(ur,l,r,c);
    pu(u);
}

int query(int u,int l,int r) {
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].s;
    if(tr[u].l>r||tr[u].r<l)return 0;
    pd(u);
    return query(ul,l,r)+query(ur,l,r);
}

signed main() {
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=n;i;i--)a[i]-=a[i-1];
    build(1,1,n);
    for(int i=0;i<m;i++) {
        int op,l,r;
        cin>>op;
        if(op==1) {
            int k,d;cin>>l>>r>>k>>d;
            up(1,l,l,k);
            if(l!=r)up(1,l+1,r,d);
            if(r<n)up(1,r+1,r+1,-(k+d*(r-l)));
        }
        else {
            int t;cin>>t;
            cout<<query(1,1,t)<<endl;
        }
    }
    return 0;
}

牛牛的等差数列

每次加上等差数列,区间查询

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M=2e5+5;
const int mod=3*5*7*11*13*17*19*23;
#define ul u<<1
#define ur u<<1|1

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}

int a[M];
struct Tree {
    int l,r,len;
    int sum,la1,la2;//首项,公差记录一下就可以了
}tr[M<<2];

void pu(int u) {
    tr[u].sum=(tr[ul].sum+tr[ur].sum)%mod;
}

void build(int u,int l,int r) {
    tr[u]={l,r,r-l+1,a[l],0,0};
    if(l==r)return ;
    int mid=l+r>>1;
    build(ul,l,mid);
    build(ur,mid+1,r);
    pu(u);
}

void upd(int &x,int y) {
    x=(x+y)%mod;
}

void pd(int u) {//更新
    if(tr[u].la1||tr[u].la2) {
        int d1=tr[u].la1,d2=(tr[u].la1+tr[ul].len*tr[u].la2%mod)%mod;
        upd(tr[ul].la1,d1);upd(tr[ul].la2,tr[u].la2);
        upd(tr[ur].la1,d2);upd(tr[ur].la2,tr[u].la2);
        upd(tr[ul].sum,d1*tr[ul].len%mod+tr[ul].len*(tr[ul].len-1)/2%mod*tr[u].la2%mod);
        upd(tr[ur].sum,d2*tr[ur].len%mod+tr[ur].len*(tr[ur].len-1)/2%mod*tr[u].la2%mod);
        tr[u].la1=tr[u].la2=0;
    }
}

int query(int u,int l,int r) {
    if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;
    if(tr[u].l>r||tr[u].r<l)return 0;
    pd(u);
    return (query(ul,l,r)+query(ur,l,r))%mod;
}

void up(int u,int l,int r,int x,int d) {
    int xx=x+(tr[u].l-l)*d;
    if(tr[u].l>=l&&tr[u].r<=r) {
        upd(tr[u].sum,xx*tr[u].len%mod+tr[u].len*(tr[u].len-1)/2%mod*d%mod);
        upd(tr[u].la1,xx);
        upd(tr[u].la2,d);
        return ;
    }
    if(tr[u].l>r||tr[u].r<l)return ;
    pd(u);
    up(ul,l,r,x,d);
    up(ur,l,r,x,d);
    pu(u);
}

signed main() {
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read()%mod;
    build(1,1,n);
    int q=read();
    while(q--) {
        int op=read();
        if(op==1) {
            int l=read(),r=read(),x=read()%mod,d=read()%mod;
            up(1,l,r,x,d);
        }
        else {
            int l=read(),r=read(),m=read();
            cout<<query(1,l,r)%m<<endl;
        }
    }
    return 0;
}

标签:二次,int,upd,tr,差分,ur,ul,维护,mod
From: https://www.cnblogs.com/basicecho/p/16981515.html

相关文章

  • 06-Go日志库Zap简单二次封装
    Go日志库Zap简单二次封装1.在项目根目录或者项目其他目录下创建二次封装代码存放目录zaplog,其他目录名称也可以2.新建config.go文件和zaplog文件,文件内容如下:config.g......
  • ANSYS二次开发:Python和ANSYS进行交互操作(PyAnsys库,DPF)
    文章目录​​1、简介​​​​2、安装​​​​2.1ansys-mapdl-core​​​​2.2pyaedt​​​​2.3ansys-dpf-core​​​​2.4ansys-dpf-post​​​​2.5ansys-mapdl-read......
  • ANSYS二次开发:Python解析ansys fluent结果文件
    文章目录​​1、简介​​​​2、fluent文件格式​​​​2.1常见格式​​​​2.2结果格式​​​​3、tecplot解析​​​​4、pyfluent解析​​​​4.1安装​​​​4.2示......
  • 04 柱面、锥面、旋转曲面和二次曲面 | 解析几何
    1.柱面1.柱面概念柱面:在空间,由平行于定方向且与一条定曲线相交的一族平行直线所生成的曲面叫做柱面准线:定曲线叫做柱面的准线柱面的准线不是惟一的,每一条与柱面的......
  • 如何维护韩国服务器
    1、安全检测服务器关系到线上所有的重要信息,十分重要,日常安全检测必不可少。具体的检测内容包括以下几个方面:检查服务器启动项是不是正常,重点查看系统目录和重要的......
  • DS哈希查找—二次探测再散列
    题目描述定义哈希函数为H(key)=key%11。输入表长(大于、等于11),输入关键字集合,用二次探测再散列构建哈希表,并查找给定关键字。输入测试次数t每组测试数据格式如下:哈希......
  • 深度之眼(十一)——矩阵对角化及二次型
    文章目录​​一、相似矩阵的定义以及矩阵的对角化​​​​1.1相似矩阵的定义​​​​1.2矩阵的对角化​​​​二、矩阵对角化的条件以及对称矩阵的对角化​​​​2.1一般......
  • 《MySQL必知必会》之事务、用户权限、数据库维护和性能
    第二十六章管理事务处理本章介绍什么是事务处理以及如何利用COMMIT和ROLLBACK语句来管理事务处理事务处理并非所有数据库引擎都支持事务处理常用的InnoDB支持事务处......
  • MySQL与MariaDB核心特性比较详细版v1.0,Oracle ACE主编(覆盖mysql 8.0/mariadb 10.3,包括
    注:本文严禁任何形式的转载,原文使用word编写,为了大家阅读方便,提供pdf版下载。MySQL与MariaDB主要特性比较详细版v1.0(不含HA).pdf链接:https://pan.baidu.com/s/1qAcrxg8eRumRi3......
  • Centos7系统恢复常用维护命令
    Centos7系统备份与恢复:使用root用户切换到根目录然后,使用下面的命令备份完整的系统:tarcvpzfbackup.tgz/--exclude=/proc--exclude=/lost+found--exclude=/backup.tgz......