BZOJ 1798: [Ahoi2009]Seq 维护序列seq
发布日期:2021-07-27 13:45:12
浏览次数:1
分类:技术文章
本文共 3504 字,大约阅读时间需要 11 分钟。
Description
老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。 有长为N的数列,不妨设为a1,a2,…,aN 。有如下三种操作形式: (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模P的值。 Input 第一行两个整数N和P(1≤P≤1000000000)。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M,表示操作总数。从第四行开始每行描述一个操作,输入的操作有以下三种形式: 操作1:“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。 操作2:“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3:“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。 Output 对每个操作3,按照它在输入中出现的顺序,依次输出一行一个整数表示询问结果。 Sample Input 7 43 1 2 3 4 5 6 7 5 1 2 5 5 3 2 4 2 3 7 9 3 1 3 3 4 7Sample Output
2 35 8HINT
【样例说明】
初始时数列为(1,2,3,4,5,6,7)。
经过第1次操作后,数列为(1,10,15,20,25,6,7)。 对第2次操作,和为10+15+20=45,模43的结果是2。 经过第3次操作后,数列为(1,10,24,29,34,15,16} 对第4次操作,和为1+10+24=35,模43的结果是35。 对第5次操作,和为29+34+15+16=94,模43的结果是8。测试数据规模如下表所示
数据编号 1 2 3 4 5 6 7 8 9 10
N= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000 M= 10 1000 1000 10000 60000 70000 80000 90000 100000 100000维护一棵线段树,有一个加法标记,乘法标记。
说着容易,然而蜜汁wa。。。 几个星期后。。。 下传乘法标记时忘了改变加法标记。下面是ac代码
#include#include using namespace std;const int maxn=100000;struct node{ int l,r; long long sum,cheng,jia;}tree[4*maxn+5];int n,m,p,data[maxn+5];inline void build(int l,int r,int num)//建树 { tree[num].l=l; tree[num].r=r; tree[num].cheng=1; tree[num].jia=0; if(l==r) { tree[num].sum=data[l]%p; return ; } int mid=l+r>>1; build(l,mid,2*num); build(mid+1,r,2*num+1); tree[num].sum=(tree[2*num].sum+tree[2*num+1].sum)%p;}inline void update(int num){ tree[num*2].jia=(tree[num*2].jia*tree[num].cheng+tree[num].jia)%p; tree[num*2+1].jia=(tree[num*2+1].jia*tree[num].cheng+tree[num].jia)%p; tree[num*2].cheng=(tree[num*2].cheng*tree[num].cheng)%p; tree[num*2+1].cheng=(tree[num*2+1].cheng*tree[num].cheng)%p; tree[num*2].sum=(tree[num*2].sum*tree[num].cheng+(tree[num*2].r-tree[num*2].l+1)*tree[num].jia)%p; tree[num*2+1].sum=(tree[num*2+1].sum*tree[num].cheng+(tree[num*2+1].r-tree[num*2+1].l+1)*tree[num].jia)%p; tree[num].jia=0; tree[num].cheng=1;}inline void mul(int l,int r,int num,int x)//修改(乘) { if(tree[num].l>r||tree[num].r =l&&tree[num].r<=r) { tree[num].cheng=(x*tree[num].cheng)%p; tree[num].jia=(x*tree[num].jia)%p; tree[num].sum=(tree[num].sum*x)%p; return ; } update(num); mul(l,r,2*num,x); mul(l,r,2*num+1,x); tree[num].sum=(tree[2*num].sum+tree[2*num+1].sum)%p;}inline void add(int l,int r,int num,int x){ if(tree[num].l>r||tree[num].r =l&&tree[num].r<=r) { tree[num].jia=(x+tree[num].jia)%p; tree[num].sum=(tree[num].sum+x*(tree[num].r-tree[num].l+1))%p; return ; } update(num); add(l,r,2*num,x); add(l,r,2*num+1,x); tree[num].sum=(tree[2*num].sum+tree[2*num+1].sum)%p;}inline long long query(int l,int r,int num){ if(tree[num].l>r||tree[num].r =l&&tree[num].r<=r) return tree[num].sum%p; update(num); return (query(l,r,2*num)+query(l,r,2*num+1))%p;}int main(){ scanf("%d%d",&n,&p); for(int i=1;i<=n;i++) scanf("%d",data+i); build(1,n,1); scanf("%d",&m); for(int i=1;i<=m;i++) { int k,t,g,c; scanf("%d%d%d",&k,&t,&g); if(k==3) printf("%lld\n",query(t,g,1)); else { scanf("%d",&c); if(k==1) mul(t,g,1,c); else add(t,g,1,c); } } return 0;}
转载地址:https://blog.csdn.net/Rlt1296/article/details/51905983 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月09日 13时25分47秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
关于spring bean 生命周期代码详解-产生到消亡
2021-06-30
spring 启动之全过程 源码解析
2021-06-30
Spring AOP 原理
2021-06-30
mysql 分库分表分区 动态扩容 总结
2021-06-30
分布式事务 四种方案
2021-06-30
redis和spring整合
2021-06-30
iis6 和iis7s上整个网站重定向
2021-06-30
iis7 url重写和重定向
2021-06-30
XStream xml与javabean之间的互转
2021-06-30
Kubernetes基础:MacOS上设定Dashboard
2021-06-30
#力扣 MySQL196. 删除重复的电子邮箱 @FDDLC
2021-06-30
Seekbar 属性 记录
2021-06-30
textview设置独特字颜色和背景颜色
2021-06-30
背景+带边框(圆角)的textview怎么设置
2021-06-30
第二技能
2021-06-30
算法的设计
2021-06-30
linux c : get curent tty info
2021-06-30
JAVA Freemarker(9)---常见语法大全
2021-06-30
Java MyBatis(1)--- Generator 详解
2021-06-30