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;
}