头像

未名湖畔的梦

炸天帮




离线:2小时前


最近来访(45)
用户头像
吴子涵
用户头像
yxc的接班人
用户头像
不正常人类研究家
用户头像
lqh540
用户头像
唯手熟尔
用户头像
nor
用户头像
acWing_lbwnb
用户头像
Feelme
用户头像
姚军
用户头像
smile_zyk
用户头像
Draper
用户头像
hncj202013018
用户头像
妖娆
用户头像
弗兰克
用户头像
Jacobxzqq
用户头像
小小霸王学习机
用户头像
殇ベ_11
用户头像
Studying
用户头像
czsnb
用户头像
凌乱之风

活动打卡代码 AcWing 217. 绿豆蛙的归宿

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 1e5 + 5;

int n, m;
int bo[N];
int h[N], ne[N<<1], e[N<<1], w[N<<1], idx;
double E[N];

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

void add(int u, int v, int k){
    e[idx] = v, w[idx] = k, ne[idx] = h[u], h[u] = idx ++ ;
}

double dp(int u){
    if(E[u]) return E[u];
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        E[u] += (dp(j) + w[i]) / bo[u];
    }
    return E[u];
}

int main(){
    read(n); read(m);

    memset(h, -1, sizeof h);

    for(int i = 1; i <= m; i++){
        int x, y, w;
        read(x); read(y); read(w);

        bo[x] ++ ; // 计算出度
        add(x, y, w);
    }

    printf("%.2lf", dp(1));
    return 0;
}


分享 算法总章

$$学习笔记$$

$\qquad $ 我深怕自己本非美玉,故而不敢加以刻苦琢磨;却又半信自己是块美玉,故又不肯庸庸碌碌,与瓦砾为伍。于是我渐渐地脱离凡尘,疏远世人,结果便是一任愤懑与羞恨日益助长内心那怯弱的自尊心。----《山月记》

写在前:作者自认为自己是一个不自觉的人,在自己职业生涯的最后一年(这样写的比较装逼,虽然我很菜),即使不太可能进入省队,在最后几个月里,总想留下点足迹,至少证明我以前来过,留下过一些什么,不要给自己的青春留下遗憾;于是乎有了写分享的计划,加以督促自己赶紧汲取知识。

本书以lyd大神的《算法竞赛进阶指南》为标准,作者自学并且记录笔记和心得,部分题目会附上题解,由于高中学业繁忙,不定时更新QAQ。(有这时间写博客还不去刷题???)

条件有限,可能配不了图,等到了大学有了属于自己的电脑(平板)就补上.有看不懂的可以发在对应博客下面的评论,我看到了会解答的(当复习不亏)。

共勉!!!


快读快输模板

第一章:基本算法

  • 位运算
  • 递推与递归
  • 前缀和与差分
  • 二分
  • 排序
  • 倍增
  • 贪心

第二章:基本数据结构

第三章:搜索

  • 树与图的遍历
  • 深度优先搜索
  • 剪枝
  • 迭代加深
  • 广度优先搜索
  • A*
  • IDA*

第四章:数学

  • 质数
  • 约数
  • 同余
  • 矩阵
  • 高斯消元与线性空间
  • 组合数学
  • 容斥原理与莫比乌斯函数
  • 概率与数学期望
  • 0/1分数规划
  • 博弈论与SG函数

第五章:数据结构

  • 并查集
  • 树状数组
  • 线段树
  • 分块
  • 点分治
  • 二分查找树与平衡树初步
  • 离线分治
  • 可持久化数据结构

第六章:动态规划

  • 线性DP
  • 背包
  • 区间DP
  • 树形DP
  • 环形与后效性处理
  • 状态压缩DP
  • 倍增优化DP
  • 数据结构优化DP
  • 单调队列优化DP
  • 斜率优化
  • 四边形不等式
  • 计数类DP

第七章:图论

  • 最短路
  • 最小生成树
  • 树的直径与最近公共祖先(LCA)
  • 基环树
  • 负环与差分约束
  • Tarjan与无向图连通性
  • Tarjan与有向图连通性
  • 二分图匹配
  • 二分图覆盖于独立集
  • 网络流初步

第八章:STL的使用

  • 常见STL与使用

Markdown语法手册




$$矩阵$$

1.定义:一组数的整体,在[ ]内排列成 m 行 n 列的数表

  • 对于矩阵$A$,主对角线是指$ A_{i,i} $ 的元素
  • 单位矩阵$I$: 行和列数相等;且主对角线元素都为 1;

$$
I:
\left[
\begin{matrix}
1 & 0 & \cdots & 0 \\
0 & 1 & \cdots & 0 \\
\vdots & 0 & \ddots & 0 \\
0 & 0 & \cdots & 1 \\
\end{matrix}
\right] \tag{1}
$$

2. 性质

  • 矩阵的逆: $A$ 的逆矩阵 $P$ 是使得 $ A * P = I$ 的矩阵 (可以使用高斯消元求得)

3.运算:

  • 加法和减法: 两个矩阵相对应的位置相加减即可
  • 矩阵乘法: $C_{i,j}$ = $\sum_{k=1}^{1} {A_{i,k}}$ $B_{k,j};$ $\qquad$ $A是n * m 的矩阵, B是r * m的矩阵$
  • 简便记忆(矩阵原理): 对于 $C_{i,j}$ 是由$ A $的 第$ i $ 行 $B $的第$ j $行 一 一对应相乘在求和而得到的
  • 注意:矩阵乘法满足结合律,不满足一般的交换律。

$$
\left[
\begin{matrix}
1 & 2 \\
3 & 4 \\
5 & 6 \\
\end{matrix}
\right]
\times
\left[
\begin{matrix}
1 & 2 \\
3 & 4 \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
1\times1+2\times3 & 1\times2+2\times4 \\
3\times1+4\times3 & 3\times2+4\times4 \\
5\times1+6\times3 & 5\times2+6\times4 \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
7 & 10 \\
15 & 22 \\
23 & 34 \\
\end{matrix}
\right] \tag{2}
$$

由于方阵的特殊性质(能自己乘自己),在做递推时可以利用矩阵的性质降低时间复杂度

例题:斐波那契

$$f(n)=
\begin{cases}
1 & \text{$n \leq 2$} \\
f(n-1) + f(n-2) & \text{$n \geq 3$}
\end{cases}\tag{3}$$

对于 $f_n$和$f_{n-1}$有

$$ f_n = f_{n-1} + f_{n-2} \tag{4} $$
$$ f_{n-1} = f_{n-1} + 0 * f_{n-2} \tag{5}$$

构造出矩阵

$$
\left[
\begin{matrix}
f(n) & f(n-1) \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
f(2) & f(1) \\
\end{matrix}
\right]
\times
\left[
\begin{matrix}
1 & 1 \\
1 & 0 \\
\end{matrix}
\right]^{(n-2)} \tag{6}
$$

对于后面这一项可以使用快速幂使复杂度降到$O(logn)$,总时间复杂度$O(k\times logn)$

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int sz = 2, MOD = 10000;
typedef long long ll;

int n;

struct mat{
    ll a[sz][sz];  // 对于 fib 只要 2 * 2 的矩阵就足够了

    // 初始化函数,没有这个函数那么初始 a 是随机的,会出错误
    inline mat() {memset(a, 0, sizeof a); }

    // 矩阵加法
    inline mat operator + (const mat &T) const{
        mat res ;
        for(int i = 0; i < sz; i++)
          for(int j = 0; j < sz; j++)
            res.a[i][j] = (a[i][j] - T.a[i][j]) % MOD;
        return res;
    }

    // 矩阵减法
    inline mat operator - (const mat &T) const{
        mat res;
        for(int i = 0; i < sz; i++)
          for(int j = 0; j < sz; j++)
            res.a[i][j] = (a[i][j] + T.a[i][j]) % MOD;
        return res;
    }

    // 矩阵乘法
    inline mat operator * (const mat &T) const{
        mat res;  int r ;
        for(int i = 0; i < sz; i++) 
          for(int k = 0; k < sz; k++) {
              r = a[i][k];                        // 对于小的矩阵,可以直接展开循环以减小常数。
              for(int j = 0; j < sz; j ++)        // 也可以写一个矩阵乘法函数mul; 
                  res.a[i][j] = (res.a[i][j] + T.a[k][j] * r) % MOD; // res.a[i][j] = mul(a[i][k],T.a[k][j]);
          }
        return res;
    }

    // 矩阵 快速幂 k 次方
    inline mat operator ^ (ll k) const{
        mat res, base;
        res.a[0][0] = res.a[0][1] = 1; // 构造初始矩阵
        base.a[0][0] = base.a[0][1] = base.a[1][0] = 1;

       /* 或者这么写;对于矩阵比较小而且初始化都差不多的时候,第一种会更方便;否则建议使用for接受数值
        for(int i = 0; i < sz; i++)
          for(int j = 0; j < sz; j++)
            base.a[i][j] = a[i][j]; 
        */   
        while(k){ // 快速幂
            if(k & 1) res = res * base; // 注意不能写成 res *= base , 因为没有重载 *=
            base = base * base;
            k >>= 1;
        }
        return res;
    }

}ans, bas;

// 初始化矩阵
void init(){
    bas.a[0][0] = bas.a[0][1] = bas.a[1][0] = 1;
    ans.a[0][0] = ans.a[0][1] = 1;
}

int main(){
    while(cin >> n && n != -1){
        if(n == 0) { puts("0"); continue; }

        init();
        ans = ans * (bas ^ (n - 2)); // 由于初始化就有 f1 f2 , 再乘一次就是 f3所以是 (n - 2) 次方
        cout << ans.a[0][0] % MOD << endl;
    }
    return 0;
}


活动打卡代码 AcWing 205. 斐波那契

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int sz = 2, MOD = 10000;

typedef long long ll;

int n;

void mul(ll f[2], ll a[2][2]){
    ll c[2] = {0};

    for(int i = 0; i < 2; i ++)
      for(int j = 0; j < 2; j ++)
        c[i] = (c[i] + f[j] * a[j][i]) % MOD;

    memcpy(f, c, sizeof c);
}

void mulself(ll a[2][2]){
    ll c[2][2] = {0};
    for(int i = 0; i < 2; i++)
      for(int j = 0; j < 2; j++)
        for(int k = 0; k < 2; k++) 
           c[i][j] = (c[i][j] + a[i][k] * a[k][j]) % MOD;
    memcpy(a, c, sizeof c);
}

int main(){
    while(cin >> n && n != -1){
        ll f[2] = {0, 1};
        ll a[2][2] = { {0,1}, {1,1} };

        while(n){
            if(n & 1) mul(f, a);
            mulself(a);
            n >>= 1;
        }
        cout << f[0] << endl;
    }

    return 0;
}



原题:矩阵

  • 问题描述;写的结构体重载怎么用啊???
  • 现在请身为大佬的你为我解决一下这个简单的问题,谢谢!
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 105;
typedef long long ll;

ll p, q, x, y, n, MOD;
// p*x + q*y  第 n 项 除以MOD

// 矩阵 加法 减法 乘法
struct mat{
    #define sz 2
    ll a[sz][sz]; 

    inline mat() {memset(a, 0, sizeof a); }
    // 矩阵加法
    inline mat operator + (const mat &T) const{
        mat res ;
        for(int i = 0; i < sz; i++)
          for(int j = 0; j < sz; j++)
            res.a[i][j] = (a[i][j] - T.a[i][j]) % MOD;
        return res;
    }

    // 矩阵减法
    inline mat operator - (const mat &T) const{
        mat res;
        for(int i = 0; i < sz; i++)
          for(int j = 0; j < sz; j++)
            res.a[i][j] = (a[i][j] + T.a[i][j]) % MOD;
        return res;
    }

    // 矩阵乘法
    inline mat operator * (const mat &T) const{
        mat res;  int r;
        for(int i = 0; i < sz; i++) 
          for(int k = 0; k < sz; k++) {
              r = a[i][k];  
              for(int j = 0; j < sz; j ++)
                  res.a[i][j] = (res.a[i][j] + T.a[k][j] * r) % MOD;
          }
        return res;
    }

    // 矩阵 快速幂 k 次方
    inline mat operator ^ (ll k) const{
        mat res, base;
        res.a[0][0] = y, res.a[0][1] = x; // 初始化矩阵 [a2, a1] 
        base.a[0][0] = p, base.a[0][1] = 1, base.a[1][0] = q;

        while(k){   // 快速幂
            if(k & 1) res = res * base;
            base = base * base;
            k >>= 1;
        }
        return res;
    }

}ans, bas;

int main(){
    cin >> p >> q >> x >> y >> n >> MOD;

    ans.a[0][0] = y, ans.a[0][1] = x;
    bas.a[0][0] = p, bas.a[0][1] = 1, bas.a[1][0] = q;

    ans = ans * (bas ^ (n - 2));

    cout << ans.a[0][0] % MOD << endl;

    return 0;
}
/*
2 3 1 2 30 23
7 20 15 21 18 7 22 19 12 12 14 18 9 3 10 6 19 10 8 0 1 2 7 20 15 21 18 7 

1 1 1 1 10 7
2 3 5 1 6 0 6 6 6
*/



$$ 单调队列 $$

1.定义: 一个满足内部单调递增或者递减的数据结构

2.实质(实现方式): 双端队列

3.应用: 利用其单调性,常用来维护区间最值问题, 或者降低DP维数,以达到降低空间及时间的目的

4.性质:

  • 队列中的元素对应原来列表的位置(即下标)必须是单调递增(递减)的
  • 队列中的元素必须是单调递增(递减)的

求区间最值例题:滑动窗口

分析:对于求最大值(求最小值一样):

  • 维护队首:队列首下标小于当前元素下标的 k 个之前(就是队列的长度超出了要求),弹出队首
  • 维护队尾:比较当前元素与队尾元素的大小,若当前元素更大,一直弹出队尾,直到满足队尾元素更大。

原因:对于$a_x$ 和 $a_y$,$x < y$且$a_x < a_y $ 那么队列在加入元素 $a_y$之后$a_x$就再也不可能是最大值了,直接踢掉.

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e6 + 5;

int n, k;
int a[N];
int q[N], v[N];
// q --> 添加元素,维护队尾 v --> 添加下标,维护队首
// 不过也有 只用一个数组 q 充当小标, 此时, a[q[tt]] 为队尾元素 a[q[hh]] 队首元素

void maxx(){
    int tt = 0, hh = 1;                         // 队列初始化
    for(int i = 1; i <= n; i++){                // 遍历所有元素,是否加入队列
        while(tt >= hh && q[tt] < a[i]) tt -- ; // 当队列不为空 并且 队尾元素小于当前值, 队尾出队
        q[++tt] = a[i];                         // 加入当前元素
        v[tt] = i;                              // 记录下标
        while(v[hh] <= i - k) ++ hh;            // 当对头元素小于 i - k,即队列长度超出要求,队首出队
        if(i >= k) printf("%d ", q[hh]);        // 当队列全部进去才输出(滑动窗口从全部进来了)
    }
}

void minn(){
    int tt = 0, hh = 1;                         // 初始化
    for(int i = 1; i <= n; i++){
        while(hh <= tt && q[tt] > a[i]) tt--;   // 是否满足条件
        q[++tt] = a[i];                         // 添加当前元素
        v[tt] = i;                              // 队首添加下标
        while(v[hh] <= i - k) ++ hh ;           // 判断是否超出限制大小
        if(i >= k) printf("%d ", q[hh]);
    }puts("");
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];

    minn(); maxx();

    return 0;
}



#include<iostream>
#include<cstring> 
using namespace std;
const int N=31;

typedef long long ll; 

ll f[N][N][N][N][N]; 
int s[10],n;
int main(){
    while(cin>>n){ 
        if(n==0)return 0;
        memset(s,0,sizeof s); 
        for(int i=1;i<=n;i++) cin>>s[i]; 
        f[0][0][0][0][0]=1;
        for(int i=1;i<=s[1];i++)
          for(int j=0;j<=s[2]&&j<=i;j++)
            for(int k=0;k<=s[3]&&k<=j;k++) 
              for(int q=0;q<=s[4]&&q<=k;q++) 
                for(int p=0;p<=s[5]&&p<=q;p++){ 
                    ll &x=f[i][j][k][q][p]=0; 
                    x+=f[i-1][j][k][q][p]; 
                    if(j)x+=f[i][j-1][k][q][p]; 
                    if(k)x+=f[i][j][k-1][q][p]; 
                    if(q)x+=f[i][j][k][q-1][p]; 
                    if(p)x+=f[i][j][k][q][p-1]; 
                } 
        cout<<f[s[1]][s[2]][s[3]][s[4]][s[5]]<<"\n"; 
    } 
}




活动打卡代码 AcWing 282. 石子合并

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 305;

int n;
int a[N];
int f[N][N];

int main(){
    cin >> n;
    memset(f, 0x3f, sizeof f);

    for(int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i-1], f[i][i] = 0;

    for(int len = 2; len <= n; len++){
        for(int l = 1; l + len - 1 <= n; l++){
            int r = l + len - 1;
            for(int k = l; k < r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k+1][r]);
            f[l][r] += a[r] - a[l-1];
        }
    }
    cout << f[1][n] << endl;

    return 0;
}



活动打卡代码 AcWing 154. 滑动窗口

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e6 + 5;

int n, k;
int a[N];
int q[N], v[N];

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

void minn(){
    int tt = 0, hh = 1;
    for(int i = 1; i <= n; i++){
        while(hh <= tt && q[tt] > a[i]) tt--;
        q[++tt] = a[i];
        v[tt] = i;
        while(v[hh] <= i - k) ++ hh ;
        if(i >= k) printf("%d ", q[hh]);
    }puts("");
}

void maxx(){
    int tt = 0, hh = 1;
    for(int i = 1; i <= n; i++){
        while(tt >= hh && q[tt] < a[i]) tt -- ;
        q[++tt] = a[i];
        v[tt] = i;
        while(v[hh] <= i - k) ++ hh;
        if(i >= k) printf("%d ", q[hh]);
    }
}

int main(){
    read(n); read(k);
    for(int i = 1; i <= n; i++) read(a[i]);

    minn(); maxx();

    return 0;
}



$$线段树$$

1.线段树的应用:广泛应用于解决在区间上维护信息的问题

支持1.区间求和, 2.区间最值, 3 区间修改,4.区间查询等操作

2.本质:二叉搜索树(也称左右子树)

3.实现思想: 将区间 $[1,n] $ 平均分成2个更小的区间, 直到区间长度为 1(无法再分)

其中$[l,r] $ 存储节点信息,叶节点的长度为 1, 即 $ l == r$。

4.线段树的储存: 堆

父节点编号为 $root$ ,则左儿子编号为 $root * 2$, 右儿子编号 $root * 2 + 1$, 利用二进制优化成 $root << 1$ 和 $root << 1 | 1$,$root << 1$ 即乘以 2, 此时 对应二进制末尾一定是$ 0 $,再$ | 1 $ 末尾一定是 1, 其余位置不变

| 操作:一个为 1 一个为 0 结果为 1

注意:对于一个长度为n的区间, 需要建立大小为4 * n 的数组维护

5. 线段树操作:

  • 1.初始化建树: 遍历整棵树即可,左子树 $[l,mid] $, 右子树$[mid+1, r] $
  • 2.单点查询: 遍历整棵树, 到达目标节点返回信息
  • 3.单点修改: 遍历树, 找到节点就修改
  • 4.区间查询: 查询区间 $[x,y]$, 当前遍历到的区间被查询区间包含就返回节点信息;否则,假设当前区间为 $[l, r]$,,中点 $ mid$ ,如果 $x <= mid$ 说明查询区间与&[l,mid]&有交集,返回信息,如果 $y > mid$(右儿子是$[mid + 1, r]$),说明查询区间与 &[mid + 1, r]&有交集,返回信息; 最后合并即可。
  • 5.区间修改: 由于每一次修改一个点的复杂度是线性的,如果每次修改一个点,复杂度退化; 因此引入懒标记:只修改对查询有用的点,没有用的点做好标记,但不会去操作,到要用时再取。

    懒标记使用方法: 遍历到的节点带有懒标记,立即修改当前节点的信息,并且将标记放到左右儿子。


// 线段树基础模板
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long

using namespace std;

const int N = 1e6 + 5;

int n, m;
int a[N];
ll sum[N << 2], add[N << 2];
// 线段树数组, 懒标记数组

// 建树
void build(int root, int l, int r){
    if(l == r){sum[root] = a[l]; return;}

    int mid = (l + r) >> 1;
    build(root<<1 , l, mid);
    build(root<<1|1, mid + 1, r);
    sum[root] = sum[root<<1] + sum[root<<1|1];
}

// 记录懒标,, 区间 [x,y] + val <==>  + length([x,y]) * val 
void update(int root, int l, int r, int val){
    add[root] += val; sum[root] += (ll) (r - l + 1) * val;
}

// 下放懒标记的影响
void pushdown(int root, int l, int r){
    if(!add[root]) return;                   // 被懒标记标过就下放懒标记影响
    int mid = (l + r) >> 1;
    update(root<<1, l, mid, add[root]);      // 下放到左区间
    update(root<<1|1, mid+1, r, add[root]);  // 下放到右区间
    add[root] = 0;                           // 懒标记已经使用过,复原,
}

// 区间修改, 插入 root --> 父节点 l,r --> 线段树数组 x,y --> 修改的区间 val --> 修改的值
void insert(int root, int l, int r, int x, int y, int val){
    if(x <= l && r <= y){ update(root, l, r, val); return;} // 打上懒标记

    pushdown(root, l, r);
    int mid = (l + r) >> 1;
    if(x <= mid) insert(root<<1, l, mid, x, y, val);     // 遍历左儿子
    if(y >  mid) insert(root<<1|1, mid+1, r, x, y, val); // 遍历右儿子
    sum[root] = sum[root<<1] + sum[root<<1|1];
}

// 单点修改, 其实就是区间修改的特殊情况 x == y, 一样的, 就不需要在标记懒数组了
// 因为懒数组是为了简化区间修改的复杂度,最终仍然会加到sum, 而单点修改就本身是在改sum
void add_one(int root, int l, int r, int x, int val){
    if(l == r) { sum[root] += val; return;}
    int mid = (l + r) >> 1;
    if(x <= mid) add_one(k<<1, l, mid, x, v);
    else add_one(k<<1|1, mid + 1, r, x, v);
    sum[k] = sum[k<<1|1] + sum[k<<1];
}

// 区间查询
ll query(int root, int l ,int r, int x, int y){
    if(x <= l && r <= y)  return sum[root];   // 区间被包含, 返回答案

    ll res = 0; 
    int mid = (l + r) >> 1;
    pushdown(root, l, r);                                  //下放懒标记的影响
    if(x <= mid) res += query(root<<1, l, mid, x, y);      // 会用到左儿子,下放到左儿子
    if(y > mid)  res += query(root<<1|1, mid+1, r, x, y);  // 右儿子同理
    return res;
}

int main(){
    scanf("%d%d",&n,&m);

    for(int i = 1; i <= n; i++) scanf("%d", a + i);

    build(1, 1, n); // 建树, root 从 1 开始

    while(m--){
        int op, x, y;
        scanf("%d%d%d", &op,&x,&y);

        if(op == 1){
            int val; scanf("%d", &val);
            insert(1, 1, n, x, y, val);
        }
        else  printf("%lld\n", query(1, 1, n, x, y));
    }

    return 0;
}

例题,单点修改

区间修改

作者能力有限欢迎指正!