企业官网建设流程全解析

深圳企业品牌网站,重庆专业网站建设公司,推广方法及策略,dz采集wordpressP1438 无聊的数列 题目背景 无聊的 YYB 总喜欢搞出一些正常人无法搞出的东西。有一天#xff0c;无聊的 YYB 想出了一道无聊的题#xff1a;无聊的数列。。。 题目描述 维护一个数列 aia_iai​#xff0c;支持两种操作#xff1a;1 l r K D#xff1a;给出一个长度等于 r−…P1438 无聊的数列题目背景无聊的 YYB 总喜欢搞出一些正常人无法搞出的东西。有一天无聊的 YYB 想出了一道无聊的题无聊的数列。。。题目描述维护一个数列aia_iai​支持两种操作1 l r K D给出一个长度等于r−l1r-l1r−l1的等差数列首项为KKK公差为DDD并将它对应加到[l,r][l,r][l,r]范围中的每一个数上。即令alalK,al1al1KD…ararK(r−l)×Da_la_lK,a_{l1}a_{l1}KD\ldots a_ra_rK(r-l) \times Dal​al​K,al1​al1​KD…ar​ar​K(r−l)×D。2 p询问序列的第ppp个数的值apa_pap​。输入格式第一行两个整数n,mn,mn,m表示数列长度和操作个数。第二行nnn个整数第iii个数表示aia_iai​。接下来的mmm行每行先输入一个整数optoptopt。若opt1opt1opt1则再输入四个整数l r K Dl\ r\ K\ DlrKD若opt2opt2opt2则再输入一个整数ppp。输出格式对于每个询问一行一个整数表示答案。输入输出样例 #1输入 #15 2 1 2 3 4 5 1 2 4 1 2 2 3输出 #16说明/提示数据规模与约定对于100%100\%100%数据0≤n,m≤105,−200≤ai,K,D≤200,1≤l≤r≤n,1≤p≤n0\le n,m \le 10^5,-200\le a_i,K,D\le 200, 1 \leq l \leq r \leq n, 1 \leq p \leq n0≤n,m≤105,−200≤ai​,K,D≤200,1≤l≤r≤n,1≤p≤n。图解代码注释#includebits/stdc.husingnamespacestd;typedeflonglongintll;constintN1e55;structnode{//线段树各节点(表示原数列的不同区间)intl,r,//该区间在原数列的区间左右边界c,//懒标记1,区间内单元素关于等差数列增量的“基础部分 ”d;//懒标记2,用于计算区间等差数列和的因pos递增的部分/* 原数列下标 1 2 3 4 5 6 7 8 9 10 原数列数值 8 2 5 4 9 7 3 10 6 1 在原数列的L4、R7区间间增加等差数列 等差数列下标 1 2 3 4 等差数列数值 13 16 19 22 区间:l1,r4,lenr-l14 区间和1316192270 区间和等差数列任意连续区间的和 区间平均项值 × 区间项数 区间和len*(d(l)d(r))/24*(1322)/270 ———————————————— 首项k13公差d3 等差数列各元素下标pos 等差数列pos下标处的值k(pos-l)*dkpos*d-l*d(k-l*d)pos*dcpos*d 懒标记1:ck-l*d13-4*31 懒标记2:d3 区间和pos从1到4该等差数列元素(cpos*d)的和len*clen原序列序号*d 其中len和len*(lr)/24*(47)/222 ———————————————— 懒标记1部分len*c4*14 懒标记2部分len长原序列序号和*d和(4,5,6,7)*dlen*(lr)/24*(47)/222*366 70 */ll val;//区间值}tree[4*N];//数组存储线段树各节点每节点表示原数列的不同区间。左子父*2右子父*21intn,q,arr[N];//原数列voidbuild(intf,intl,intr){//构建线段树tree[f].ll,tree[f].rr,tree[f].ctree[f].d0;//初始化线段树每节点对应原数列区间的左右边界和双懒标记if(lr){tree[f].valarr[l];return;}//细分到区间左右边界重合最小区间对应原数列某元素intml((r-l)1);//区间中点build(f1,l,m);//递归左半区间构建线段树build(f1|1,m1,r);//右半区间tree[f].valtree[f1].valtree[f1|1].val;//更新区间值左子区间区间值右子区间区间值}voidpushdown(intf){//下传双懒标记noderoottree[f],ltree[f1],rtree[f1|1];//建立区间和区间左右子区间的引用if(root.c0root.d0)return;//该区间没有双懒标记则停止下传intllenl.r-l.l1;//左子区间宽度l.valroot.c*llen(ll)root.d*llen*(l.ll.r)/2;//增加左子区间区间值。llen*(l.ll.r)/2该区间等差数列和l.croot.c;l.droot.d;//左子区间下传双懒标记intrlenr.r-r.l1;//右子区间宽度r.valroot.c*rlen(ll)root.d*rlen*(r.lr.r)/2;//增加右子区间区间值r.croot.c;r.droot.d;//往右子区间下传双懒标记root.croot.d0;//清空该区间双懒标记}voidadd(intf,ints,inte,intc,intd){//增加区间区间值intltree[f].l,rtree[f].r,lenr-l1,ml((r-l)1);//区间左右边界区间宽度区间中点if(slre){//该区间完全在操作区间内tree[f].valc*len(ll)d*len*(lr)/2;//计算出整个区间的区间增加值tree[f].cc,tree[f].dd;//放置双懒标记以备往后提到该节点时下传双懒标记return;//递归基是递和归间的转换点往后就得归}pushdown(f);//下传此前得到的双懒标记if(sm)add(f1,s,e,c,d);//递归在左区间增加区间增加值if(me)add(f1|1,s,e,c,d);//递归右子区间tree[f].valtree[f1].valtree[f1|1].val;//更新该节点的区间值左右子区间区间值的和}llquery(intf,intx){//查找原数组某下标的新值intltree[f].l,rtree[f].r,ml((r-l)1);if(lr)returntree[f].val;//左右边界重叠说明找到了pushdown(f);//下传以前得到的双懒标记if(xm)returnquery(f1,x);//在左区间找elsereturnquery(f1|1,x);//在右区间找}intmain(){//freopen(data.cpp,r,stdin);cinnq;for(inti1;in;i)cinarr[i];build(1,1,n);//建立线段树while(q--){//操作次数intop;cinop;//操作类型if(op1){intl,r,k,d,c;cinlrkd;ck-l*d;add(1,l,r,c,d);//给l到r区间增加k开始公差为d的公差数列}else{intx;cinx;coutquery(1,x)endl;//查询原数组x位置在线段树中的新值}}return0;}小结原数组是原始数据载体所有区间操作的目标都是面向「原数组」的指定区间进行的。线段树数组是对原数组的区间重构与分层存储所有区间操作的计算、标记、结果最终都体现在线段树数组的节点中。线段树的父子节点下标关系固定左子节点下标 2父节点下标右子节点下标 2父节点下标1。线段树的每个节点都维护区间边界 tree[f].l 和 tree[f].r该边界就是映射「原数组」的一段连续区间范围。本题线段树的核心功能实现「原数组指定区间」加等差数列并支持单点查询核心计算是求【区间等差数列的总增量和】。对原数组的操作区间[l,r][l, r][l,r]加首项为kkk、公差为ddd的等差数列 → 原数组中任意位置pos\boldsymbol{pos}posl≤pos≤rl\le pos\le rl≤pos≤r的增量值 k(pos−l)∗d\boldsymbol{k (pos-l)*d}k(pos−l)∗d其中lll是本次区间操作的左边界。操作区间lll到rrr的等差数列总增量和len×c(区间下标和)×d\boldsymbol{len\times c (区间下标和) \times d}len×c(区间下标和)×d其中ck−l×dc k - l\times dck−l×dlenr−l1len r-l1lenr−l1区间长度区间下标和 len×(lr)2\frac{len\times(lr)}{2}2len×(lr)​补充区间下标和 → 就是原数组操作区间[l,r][l,r][l,r]内所有位置pos的总和pos从l到r连续。