怎么搭建wap网站,阿里巴巴网站特色,站长统计入口,wordpress二次元风格因为这两天在写线性代数的作业#xff0c;没怎么写题……
P1438 无聊的数列
题目背景
无聊的 YYB 总喜欢搞出一些正常人无法搞出的东西。有一天#xff0c;无聊的 YYB 想出了一道无聊的题#xff1a;无聊的数列。。。
题目描述
维护一个数列 ai#xff0c;支持两种操…因为这两天在写线性代数的作业没怎么写题……
P1438 无聊的数列
题目背景
无聊的 YYB 总喜欢搞出一些正常人无法搞出的东西。有一天无聊的 YYB 想出了一道无聊的题无聊的数列。。。
题目描述
维护一个数列 ai支持两种操作 1 l r K D给出一个长度等于 r−l1 的等差数列首项为 K公差为 D并将它对应加到 [l,r] 范围中的每一个数上。即令 alalK,al1al1KD…ararK(r−l)×D。 2 p询问序列的第 p 个数的值 ap。
输入格式
第一行两个整数数 n,m 表示数列长度和操作个数。
第二行 n 个整数第 i 个数表示 ai。
接下来的 m 行每行先输入一个整数 opt。
若 opt1 则再输入四个整数 l r K D
若 opt2 则再输入一个整数 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 来记录结果 等差数列的分解 等差数列可以分解为常数项和线性项 常数项A K - l × D 线性项系数D 位置 i 的增加值add(i) (K - l × D) (i - l) × D A D × i 两个树状数组维护 树状数组 tr1维护常数项A 在 l 处加 A 在 r1 处减 A若 r1 ≤ n 树状数组 tr2维护线性项系数D 在 l 处加 D 在 r1 处减 D若 r1 ≤ n 查询计算 位置 p 的值 初始值 tr1 的前缀和(p) tr2 的前缀和(p) × p
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includeiostream
#includebits/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 (lmid ) {ChaRu(l, r, k, d, i * 2);}if (mid1 r) {ChaRu(l, r, k, d, i * 2 1);}
}
long long Cha(int p, int i) {if (a[i].l pa[i].rp) {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 ( pmid ) {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要求支持如下三个操作
给定区间 [l,r]将区间内每个数都修改为 x。给定区间 [l,r]将区间内每个数都加上 x。给定区间 [l,r]求区间内的最大值。
输入格式
第一行是两个整数依次表示序列的长度 n 和操作的个数 q。 第二行有 n 个整数第 i 个整数表示序列中的第 i 个数 ai。 接下来 q 行每行表示一个操作。每行首先有一个整数 op表示操作的类型。
若 op1则接下来有三个整数 l,r,x表示将区间 [l,r] 内的每个数都修改为 x。若 op2则接下来有三个整数 l,r,x表示将区间 [l,r] 内的每个数都加上 x。若 op3则接下来有两个整数 l,r表示查询区间 [l,r] 内的最大值。
输出格式
对于每个 op3 的操作输出一行一个整数表示答案。
输入输出样例
输入 #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% 的数据nq1。对于 40% 的数据n,q≤103。对于 50% 的数据0≤ai,x≤104。对于 60% 的数据op1。对于 90% 的数据n,q≤105。对于 100% 的数据1≤n,q≤1061≤l,r≤nop∈{1,2,3}∣ai∣,∣x∣≤109。
提示
请注意大量数据读入对程序效率造成的影响。
思路 线段树节点设计 每个节点包含三个字段setv区间赋值标记、addv区间加法标记和 maxv区间最大值。 setv 为 LLONG_MIN 时表示该节点没有赋值标记。 addv 为 0 时表示没有加法标记。 标记下传 如果当前节点有赋值标记setv ! LLONG_MIN则将其下传到子节点并清除子节点的加法标记。 如果当前节点有加法标记addv ! 0则根据子节点的标记类型进行更新 如果子节点有赋值标记则将加法标记加到赋值标记上。 否则将加法标记加到子节点的加法标记上。 更新子节点的最大值并清除当前节点的标记。 标记上传 用子节点的最大值更新当前节点的最大值。 区间赋值操作 当节点区间完全被目标区间覆盖时设置节点的 setv 为指定值清除 addv并更新 maxv。 否则下传标记后递归处理子节点最后更新当前节点的最大值。 区间加法操作 当节点区间完全被目标区间覆盖时 如果有赋值标记则更新赋值标记。 否则更新加法标记。 更新节点的最大值。 否则下传标记后递归处理子节点最后更新当前节点的最大值。 区间最大值查询 当节点区间完全被查询区间覆盖时直接返回 maxv。 否则下传标记后递归查询子节点并返回子节点中的最大值。
然后就是他这个题目的结构体还是有一点说法 的如果你把x放进去记录那比较好些一点但你一开始向我一样懒的话就只能在op1下滑时a[i * 21].Max0 a[i].Max0-a[i].op2;先op1在op2)
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includeiostream
#includebits/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 * 21].Max0 a[i].Max0-a[i].op2;a[i * 21].op2 0;a[i * 21].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;
}
