当前位置: 首页 > web >正文

P1438 无聊的数列/P1253 扶苏的问题

因为这两天在写线性代数的作业,没怎么写题……

P1438 无聊的数列

题目背景

无聊的 YYB 总喜欢搞出一些正常人无法搞出的东西。有一天,无聊的 YYB 想出了一道无聊的题:无聊的数列。。。

题目描述

维护一个数列 ai​,支持两种操作:

  • 1 l r K D:给出一个长度等于 r−l+1 的等差数列,首项为 K,公差为 D,并将它对应加到 [l,r] 范围中的每一个数上。即:令 al​=al​+K,al+1​=al+1​+K+D…ar​=ar​+K+(r−l)×D。

  • 2 p:询问序列的第 p 个数的值 ap​。

输入格式

第一行两个整数数 n,m 表示数列长度和操作个数。

第二行 n 个整数,第 i 个数表示 ai​。

接下来的 m 行,每行先输入一个整数 opt。

若 opt=1 则再输入四个整数 l r K D;

若 opt=2 则再输入一个整数 p。

输出格式

对于每个询问,一行一个整数表示答案。

输入输出样例

输入 #1复制

5 2
1 2 3 4 5
1 2 4 1 2
2 3

输出 #1复制

6

说明/提示

数据规模与约定

对于 100% 数据,0≤n,m≤105,−200≤ai​,K,D≤200,1≤l≤r≤n,1≤p≤n。

思路:

最要注意的是他的结果会超过int型,所以要用 long long 来记录结果

  1. 等差数列的分解

    • 等差数列可以分解为常数项和线性项:

      • 常数项:A = K - l × D

      • 线性项系数:D

    • 位置 i 的增加值:add(i) = (K - l × D) + (i - l) × D = A + D × i

  2. 两个树状数组维护

    • 树状数组 tr1:维护常数项(A)

      • 在 l 处加 A

      • 在 r+1 处减 A(若 r+1 ≤ n)

    • 树状数组 tr2:维护线性项系数(D)

      • 在 l 处加 D

      • 在 r+1 处减 D(若 r+1 ≤ n)

  3. 查询计算

    • 位置 p 的值 = 初始值 + tr1 的前缀和(p) + tr2 的前缀和(p) × p

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct ss {long long k, d;int l, r;
}a[400005];
int  b[100005];
void XiaFang(int i) {a[i * 2].k += a[i].k;a[i * 2].d += a[i].d;a[i * 2 + 1].k += a[i].k + (a[i * 2 + 1].l - a[i].l) * a[i].d;a[i * 2 + 1].d += a[i].d;a[i].k = 0;a[i].d = 0;
}
void Chu(int l, int r, int i) {a[i].l = l, a[i].r = r, a[i].d = 0;if (l == r) {a[i].k = b[a[i].l];return;}a[i].k = 0;int mid = (l + r) >> 1;Chu(l, mid, i * 2);Chu(mid + 1, r, i * 2 + 1);
}
void ChaRu(int l, int r, int k, int d,int i) {if (a[i].l >= l && a[i].r <= r) {a[i].k += k + (a[i].l - l) * d;a[i].d += d;return;}int mid = (a[i].l + a[i].r) >> 1;if (a[i].d != 0 || a[i].k != 0) {XiaFang(i);}if (l<=mid ) {ChaRu(l, r, k, d, i * 2);}if (mid+1 <= r) {ChaRu(l, r, k, d, i * 2 + 1);}
}
long long Cha(int p, int i) {if (a[i].l == p&&a[i].r==p) {return a[i].k;}int mid = (a[i].l + a[i].r) >> 1;if (a[i].d != 0 || a[i].k != 0) {XiaFang(i);}if ( p<=mid ) {return Cha(p, i * 2);}else {return Cha(p, i * 2 + 1);}
}
int p, l, r, k, d, n, m, q;
int main(){ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> b[i];}Chu(1,n,1);for (int i = 0; i < m; i++) {cin >> q;if (q == 1) {cin >> l >> r >> k >> d;ChaRu(l, r, k, d, 1);}else {cin >> p;cout << Cha(p, 1) << endl;}}return 0;
}

 P1253 扶苏的问题

题目描述

给定一个长度为 n 的序列 a,要求支持如下三个操作:

  1. 给定区间 [l,r],将区间内每个数都修改为 x。
  2. 给定区间 [l,r],将区间内每个数都加上 x。
  3. 给定区间 [l,r],求区间内的最大值。

输入格式

第一行是两个整数,依次表示序列的长度 n 和操作的个数 q。
第二行有 n 个整数,第 i 个整数表示序列中的第 i 个数 ai​。
接下来 q 行,每行表示一个操作。每行首先有一个整数 op,表示操作的类型。

  • 若 op=1,则接下来有三个整数 l,r,x,表示将区间 [l,r] 内的每个数都修改为 x。
  • 若 op=2,则接下来有三个整数 l,r,x,表示将区间 [l,r] 内的每个数都加上 x。
  • 若 op=3,则接下来有两个整数 l,r,表示查询区间 [l,r] 内的最大值。

输出格式

对于每个 op=3 的操作,输出一行一个整数表示答案。

输入输出样例

输入 #1复制

6 6
1 1 4 5 1 4
1 1 2 6
2 3 4 2
3 1 4
3 2 3
1 1 6 -1
3 1 6

输出 #1复制

7
6
-1

输入 #2复制

4 4
10 4 -3 -7
1 1 3 0
2 3 4 -4
1 2 4 -9
3 1 4

输出 #2复制

0

说明/提示

数据规模与约定

  • 对于 10% 的数据,n=q=1。
  • 对于 40% 的数据,n,q≤103。
  • 对于 50% 的数据,0≤ai​,x≤104。
  • 对于 60% 的数据,op=1。
  • 对于 90% 的数据,n,q≤105。
  • 对于 100% 的数据,1≤n,q≤106,1≤l,r≤n,op∈{1,2,3},∣ai​∣,∣x∣≤109。

提示

请注意大量数据读入对程序效率造成的影响。

思路:

  1. 线段树节点设计

    • 每个节点包含三个字段:setv(区间赋值标记)、addv(区间加法标记)和 maxv(区间最大值)。

    • setv 为 LLONG_MIN 时表示该节点没有赋值标记。

    • addv 为 0 时表示没有加法标记。

  2. 标记下传)

    • 如果当前节点有赋值标记(setv != LLONG_MIN),则将其下传到子节点,并清除子节点的加法标记。

    • 如果当前节点有加法标记(addv != 0),则根据子节点的标记类型进行更新:

      • 如果子节点有赋值标记,则将加法标记加到赋值标记上。

      • 否则,将加法标记加到子节点的加法标记上。

    • 更新子节点的最大值并清除当前节点的标记。

  3. 标记上传

    • 用子节点的最大值更新当前节点的最大值。

  4. 区间赋值操作

    • 当节点区间完全被目标区间覆盖时,设置节点的 setv 为指定值,清除 addv,并更新 maxv

    • 否则,下传标记后递归处理子节点,最后更新当前节点的最大值。

  5. 区间加法操作

    • 当节点区间完全被目标区间覆盖时:

      • 如果有赋值标记,则更新赋值标记。

      • 否则,更新加法标记。

    • 更新节点的最大值。

    • 否则,下传标记后递归处理子节点,最后更新当前节点的最大值。

  6. 区间最大值查询

    • 当节点区间完全被查询区间覆盖时,直接返回 maxv

    • 否则,下传标记后递归查询子节点,并返回子节点中的最大值。

然后就是他这个题目的结构体还是有一点说法 的,如果你把x放进去记录那比较好些一点,但你一开始向我一样懒的话就只能在op1下滑时a[i * 2+1].Max0 = a[i].Max0-a[i].op2;(先op1在op2)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct ss {int l, r;long long Max0;long long op2;bool op1;
}a[4000006];
long long b[1000006];
void Chu(int l, int r, int i) {a[i].l = l, a[i].r = r;a[i].op2 = 0, a[i].op1 = false;if (l == r) {a[i].Max0 = b[l];return;}int mid = (l + r) >> 1;Chu(l, mid, i * 2);Chu(mid + 1, r, i * 2 + 1);a[i].Max0 = max(a[i * 2].Max0, a[i * 2 + 1].Max0);
}
void OOp1(int i) {if(a[i].l!=a[i].r) {a[i * 2].Max0 = a[i].Max0-a[i].op2;a[i * 2].op2 = 0;a[i * 2].op1 = true;a[i * 2+1].Max0 = a[i].Max0-a[i].op2;a[i * 2+1].op2 = 0;a[i * 2+1].op1 = true;}a[i].op1 = false;
}
void OOp2(int i) {if (a[i].l != a[i].r) {a[i * 2].Max0 += a[i].op2;a[i * 2].op2 += a[i].op2;a[i * 2 + 1].Max0 += a[i].op2;a[i * 2 + 1].op2 += a[i].op2;}a[i].op2 = 0;
}
void Op1(int l, int r, long long x,int i) {if (a[i].l >= l && a[i].r <= r) {a[i].Max0 = x;a[i].op2 = 0;a[i].op1 = true;return;}if (a[i].op1) {OOp1(i);}if (a[i].op2 != 0) {//可能为负数OOp2(i);}int mid = (a[i].l + a[i].r) >> 1;if (l <= mid) {Op1(l, r,x, i * 2);}if (mid + 1 <= r) {Op1(l, r, x, i * 2 + 1);}a[i].Max0 = max(a[i * 2].Max0, a[i * 2 + 1].Max0);
}
void Op2(int l, int r, long long x, int i) {if (a[i].l >= l && a[i].r <= r) {a[i].Max0 += x;a[i].op2 += x;return;}if (a[i].op1) {OOp1(i);}if (a[i].op2 != 0) {//可能为负数OOp2(i);}int mid = (a[i].l + a[i].r) >> 1;if (l <= mid) {Op2(l, r, x, i * 2);}if (mid + 1 <= r) {Op2(l, r, x, i * 2 + 1);}a[i].Max0 = max(a[i * 2].Max0, a[i * 2 + 1].Max0);
}
long long Op3(int l, int r, int i) {if (a[i].l >= l && a[i].r <= r) {return a[i].Max0;}if (a[i].op1) {OOp1(i);}if (a[i].op2 != 0) {//可能为负数OOp2(i);}int mid = (a[i].l + a[i].r) >> 1;long long w = LLONG_MIN;if (l <= mid) {w = max(w, Op3(l, r, i * 2));}if (mid + 1 <= r) {w = max(w, Op3(l, r, i * 2 + 1));}return w;
}
int n, m, l, r, op;
long long x;
int main(){ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> b[i];}Chu(1, n, 1);for (int i = 1; i <= m; i++) {cin >> op;switch (op){case 1:cin >> l >> r >> x;Op1(l, r, x, 1);break;case 2:cin >> l >> r >> x;Op2(l, r, x, 1);break;case 3:cin >> l >> r;cout << Op3(l, r, 1) << endl;break;default:break;}}return 0;
}

 

http://www.xdnf.cn/news/10858.html

相关文章:

  • 深度学习与特征交叉:揭秘FNN与SNN在点击率预测中的应用
  • 多线程编程的黄金三角模型
  • [yolov11改进系列]基于yolov11使用图像去雾网络UnfogNet替换backbone的python源码+训练源码
  • pytorch基本运算-导数和f-string
  • Easyui悬停组件
  • nav2笔记-250603
  • 国产高性能pSRAM选型指南:CSS6404LS-LI 64Mb QSPI伪静态存储器
  • 【网络安全 | 信息收集】灯塔(资产收集工具)安装教程
  • 【QT】`QTextCursor::insertText()`中插入彩色文本
  • Windows清理之后,资源管理器卡顿-解决方法
  • 【开源工具】Python+PyQt5打造智能桌面单词记忆工具:悬浮窗+热键切换+自定义词库
  • 【论文解读】FeINFN|Fourier-enhanced Implicit Neural Fusion Network for Multispectral
  • 黑马Java面试笔记之 消息中间件篇(Kafka)
  • Linux 软件安装方式全解(适用于 CentOS/RHEL 系统)
  • 【25.06】FISCOBCOS使用caliper自定义测试 通过webase 单机四节点 helloworld等进行测试
  • 多线程环境中,如果多个线程同时尝试向同一个TCP客户端发送数据,添加同步机制
  • 新版 Xcode 中 CoreData 模型编辑器显示拓扑图功能取消的替代方案
  • IBM DB2分布式数据库架构
  • 决策树指南:如何为您的数据选择合适的特征工程策略
  • 【卡点变速】节拍同步 讨论
  • Array.prototype.find()
  • 前端​​HTML contenteditable 属性使用指南
  • EagleTrader采访|在市场中修行的交易之道与实战反思
  • 【计算机系统结构】知识点总结
  • 产品更新丨谷云科技ETLCloud 3.9.3 版本发布
  • 【AI News | 20250603】每日AI进展
  • ElasticStack对接kafka集群
  • 【相等性比较的通解——理解 JavaScript 中的 Object.is()】
  • 高考数学易错考点02 | 临阵磨枪
  • 深入解析Playwright for Python:浏览器功能与代码实例详解