题没有很难,但题解比较少,于是乎我就水一篇
题目描述
老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。
有长为 $N$ 的数列,不妨设为 $a_1,a_2,…,a_N$。
有如下三种操作形式:
- 把数列中的一段数全部乘一个值;
- 把数列中的一段数全部加一个值;
- 询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模 P 的值。
输入格式
第一行两个整数 $N$ 和 $P$;
第二行含有 $N$ 个非负整数,从左到右依次为 $a_1,a_2,…,a_N$;
第三行有一个整数 $M$,表示操作总数;
从第四行开始每行描述一个操作,输入的操作有以下三种形式:
操作 $1$:1 t g c
,表示把所有满足 $t≤i≤g$ 的 $a_i$ 改为 $a_i\times c$;
操作 $2$:2 t g c
,表示把所有满足 $t≤i≤g$ 的 $a_i$ 改为 $a_i+c$;
操作 $3$:3 t g
,询问所有满足 $t≤i≤g$ 的 $a_i$ 的和模 $P$ 的值。
同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。
输出格式
对每个操作 $3$,按照它在输入中出现的顺序,依次输出一行一个整数表示询问结果。
数据范围
$1≤N,M≤10^5,$
$1≤t≤g≤N,$
$0≤c,a_i≤10^9,$
$1≤P≤10^9$
算法1
(线段树)
线段树板子不多说了吧。
基本就是一个log的复杂度。
线段树的思想就是说把一个区间分成一段一段,第一层一段,第二层两段,第三层4段......
然后再进行修改。
我们可以把整个维护的区间看成一颗树,这是一颗满二叉树。
u节点的左儿子是$u << 1$,右儿子是$u << 1 | 1$,然后每次更新时利用下面的节点更新就行了,这样的话代码会跑的飞快。
其实线段树一个挺高大上的名字,除了debug,剩下的都挺简单
板子不多说了,具体的可以看代码里的注释。
然后就是懒标记,有的时候加来加去很烦对吧,于是我们在线段树里开一个变量,来记录一下加多少,然后在统一加上就行了。
懒标记要满足一个性质叫可叠加性,就是说你可以通过上面的来算出下面两个儿子的值,也可以反推回去。
比如这道题吧, 先加再乘不行的原因就是不满足可叠加性,pushdown的时候就会有bug。
所以我们不妨改一下,先乘再加,就可以了。
这就是思路,比较行云流水没啥难度。
然后说一下代码吧,代码如下:(代码后面还有内容,先别离开~)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
#define ll long long
int n, p, m;
int w[N];
struct Node
{
int l, r;
int add, sum, malt;//建立线段树节点,sum表示区间和,l, r废话少说,add和malt是懒标记
}tr[N * 4];//懒标记和这个维护的sum要有可叠加性,所以选择了先乘再加
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
tr[u].sum = tr[u].sum % p;//更新这个sum,没啥好说的
}
void pushdown(int u)
{
tr[u << 1].sum = ((ll)tr[u << 1].sum * tr[u].malt + (ll)tr[u].add * (tr[u << 1].r - tr[u << 1].l + 1)) % p;
tr[u << 1 | 1].sum = ((ll)tr[u << 1 | 1].sum * tr[u].malt + (ll) tr[u].add * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1)) % p;
tr[u << 1].add = ((ll)tr[u << 1].add * tr[u].malt + tr[u].add) % p;
tr[u << 1 | 1].add = ((ll)tr[u << 1 | 1].add * tr[u].malt + tr[u].add) % p;
tr[u << 1].malt = (ll)tr[u << 1].malt * tr[u].malt % p;
tr[u << 1 | 1].malt = (ll)tr[u << 1 | 1].malt * tr[u].malt % p;//先乘再加,然后取模,注意longlong,不然就像我第一次搞的时候一样建祖宗了
tr[u].add = 0;//最后记得清空懒标记
tr[u].malt = 1;//乘法的懒标记一定是1,不然就全都0了
}
void build(int u, int l, int r)//开始建树
{
if(l == r) tr[u] = {l, r, 0, w[r], 1};//只要是叶节点的话就直接建立,sum自然是w[r],当然写w[l]也行
else
{
tr[u] = {l, r, 0, 0, 1};//乘法懒标记搞成1
int mid = (l + r) >> 1;
build(u << 1, l, mid);//build左右两边
build(u << 1 | 1, mid + 1, r);
pushup(u);//最后记得上传,build是一层层往下的,不用分裂处理,也就是不用pushdown
}
}
void change(int u, int l, int r, int malt, int add)//改变函数,我习惯change
{
if(tr[u].l >= l && tr[u].r <= r)//如果包含在区间内部
{
//改变懒标记和sum,先乘后加!!!注意开long long
tr[u].sum = ((ll)tr[u].sum * malt + (ll)add * (tr[u].r - tr[u].l + 1)) % p;
tr[u].add = ((ll)tr[u].add * malt + add) % p;
tr[u].malt = (ll)tr[u].malt * malt % p;
}
else//分裂处理,先pushdown
{
pushdown(u);//处理懒标记
int mid = (tr[u].l + tr[u].r) >> 1;//算一下终点
if(l <= mid) change(u << 1, l, r, malt, add);//算左右两边
if(r > mid) change(u << 1 | 1, l, r, malt, add);
pushup(u);//合并一下,然后处理sum
}
}
int query(int u, int l, int r)//查询操作
{
if(tr[u].l >= l && tr[u].r <= r)
{
return tr[u].sum;//如果在区间之内直接返回
}
pushdown(u);//这个跟修改很像,也先分裂一下,处理懒标记
int mid = (tr[u].l + tr[u].r) >> 1;//处理左右两边
ll res = 0;//开个res记录
if(l <= mid)
{
res += query(u << 1, l, r);
res = res % p;//取模不要忘啊
}
if(r > mid)
{
res += query(u << 1 | 1, l, r);
res = res % p;
}
return res;
}
int main()
{
cin >> n >> p;//读入没啥好说的
for(int i = 1; i <= n; i ++) cin >> w[i];
build(1, 1, n);//记得建树,不然就凉了
cin >> m;
while(m --)
{
int op;
int l, r;
int c;
cin >> op;
if(op == 2)
{
cin >> l >> r >> c;
change(1, l, r, 1, c);//这个我写的是加法,你们可以改一下
//加法相当于*1+c,不能把malt制成0,我这么干了,结果答案成了00000。。。
}
else if(op == 1)
{
cin >> l >> r >> c;
change(1, l, r, c, 0);//一样,*c+0
}
else
{
cin >> l >> r;
cout << query(1, l, r) << endl;//查询操作
}
}
return 0;//愉快结束
}
然后就是debug的问题。
一般写完会CE不多说了。
然后总结几个SF的问题:首先先看一下自己开没开4倍空间,注意四倍指的并不是N的四倍,而是维护区间长度的4倍。
这是个大坑,具体请出门左转查看亚特兰蒂斯那道题,(推荐秦大佬的题解)扫描线啥的这里题一下。
就是说用一条线扫过一个范围,然后在扫描线上维护一个线段树,遇到障碍就区间+1,障碍消失就区间-1,最后就是个区间修改区间查询的板子。
然后就是看看自己有没有把l
和tr[u].l
搞混,不要乱,建树的时候一般用l,其他时候用另一个。
如果还调试不出来,那可能就位运算写错了,好好看看吧。
如果位运算也没问题,那就得看看逻辑上有没有错误了。
SF调完一般调WA。
WA的话先看看开没开long long,我就因为没开ll卡了10分钟。
然后就是看看有没有明显的逻辑错误,这时候建议肉眼调试。
最后如果还不行可以输出一下tr数组的变动,看看是不是pushdown的逻辑处理错了。
然后是TLE,首先看看有没有什么可以优化的,举几个例子:
前缀和:查询区间和时可以使用
差分:区间加法时能用,具体可以出门左转,去看区间最大公约数那道题。
二分:优化查找部分,一般和离散化配套使用。
离散化:具体不多说了,还是那句话,出门左拐,去看亚特兰蒂斯那道题。
dp:线段树优化dp,很难了,去学闫式dp分析法吧。
好了如果你海没有debug出来。那我也没办法了。
zs
正在调一道线段树,正好
Segmentation Fault
哪到题目啊
洛谷P2574 XOR的艺术
可以
hhh
洛谷上有个板子题,顺手推荐一下,不是很简单,套路偏多。
link
其实是个可持久化啦~
pushdown为什么不先判断是否为0,不然这还有啥意义和没有优化一个样,还不如不用懒标记
因为pushdown每次只向下执行一次,相当于把更新这个操作分摊到以后的传递了,只要访问子节点,就清空当前节点(不管原先是不是空,不影响时间复杂度)
谢谢,已经考公去了,🤭
祝上岸,😉
大佬终于更了
拖更了