当前位置: 首页 > news >正文

做网站寄生虫需要哪些东西wordpress生成xml地图

做网站寄生虫需要哪些东西,wordpress生成xml地图,vs2013做简单的网站,网上营销网站目录 差分:思路代码: 原题链接 差分: 输入一个长度为 n 的整数序列。 接下来输入 m 个操作,每个操作包含三个整数 l,r,c ,表示将序列中 [l,r] 之间的每个数加上 c 。 请你输出进行完所有操作后的序列。 输入格式 第…

目录

    • 差分:
    • 思路
    • 代码:

原题链接

差分:

输入一个长度为 n
的整数序列。

接下来输入 m
个操作,每个操作包含三个整数 l,r,c
,表示将序列中 [l,r]
之间的每个数加上 c

请你输出进行完所有操作后的序列。

输入格式
第一行包含两个整数 n
和 m

第二行包含 n
个整数,表示整数序列。

接下来 m
行,每行包含三个整数 l,r,c
,表示一个操作。

输出格式
共一行,包含 n
个整数,表示最终序列。

数据范围
1≤n,m≤100000
,
1≤l≤r≤n
,
−1000≤c≤1000
,
−1000≤整数序列中元素的值≤1000
输入样例:
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例:
3 4 5 3 4 2

思路

这题按照常规的思路 那就是用for循环l到r直接到数字 时间复杂度比较高
差分
类似于数学中的求导和积分,差分可以看成前缀和的逆运算。

差分数组:

首先给定一个原数组a:a[1], a[2], a[3], a[n];

然后我们构造一个数组b : b[1] ,b[2] , b[3], b[i];

使得 a[i] = b[1] + b[2 ]+ b[3] +, + b[i]

也就是说,a数组是b数组的前缀和数组,反过来我们把b数组叫做a数组的差分数组。换句话说,每一个a[i]都是b数组中从头开始的一段区间和。

考虑如何构造差分b数组?

最为直接的方法

如下:

a[0 ]= 0;

b[1] = a[1] - a[0];

b[2] = a[2] - a[1];

b[3] =a [3] - a[2];

b[n] = a[n] - a[n-1];

图示:

我们只要有b数组,通过前缀和运算,就可以在O(n) 的时间内得到a数组 。

知道了差分数组有什么用呢? 别着急,慢慢往下看。

话说有这么一个问题:

给定区间[l ,r ],让我们把a数组中的[ l, r]区间中的每一个数都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c , a[r] + c;

暴力做法是for循环l到r区间,时间复杂度O(n),如果我们需要对原数组执行m次这样的操作,时间复杂度就会变成O(n*m)。有没有更高效的做法吗? 考虑差分做法。

始终要记得,a数组是b数组的前缀和数组,比如对b数组的b[i]的修改,会影响到a数组中从a[i]及往后的每一个数。

首先让差分b数组中的 b[l] + c ,a数组变成 a[l] + c ,a[l+1] + c, a[n] + c;

然后我们打个补丁,b[r+1] - c, a数组变成 a[r+1] - c,a[r+2] - c,a[n] - c;

为啥还要打个补丁?

因为原来将b[l]+c后 其l后面的每一个数字都会被影响 ,将b[r+1]-c后 r+1后面的数字的影响又被修改了回来

那么等于只有l到r的这一段区间内的值被影响

代码:

#include<iostream>using namespace std;const int N=1e5+10;int a[N],b[N];
int main()
{int m=0,n=0;cin>>m>>n;for(int i=1;i<=m ;i++){scanf("%d",&a[i]);b[i] = a[i]-a[i-1];}//只修改差分数组里面的值即可while(n--){int l=0,r=0;int val=0;cin>>l>>r>>val;b[l] +=val;b[r+1] -=val;}//将差分数组里面的值同步到a数组里面去for(int i=1;i<=m ;i++){a[i] =a[i-1]+b[i];printf("%d ",a[i]);}return 0;}
http://www.yayakq.cn/news/615654/

相关文章:

  • 厦门网页建站申请比较好网站开发语言怎么看
  • 做好网站怎样下载wordpress
  • 网站联系我们怎么做pc网站手机版开发
  • 发簪做的比较好的网站seo网站推广是什么
  • 网站建设与维护 实训秦皇岛网络优化排名
  • 广西建设行政主管部门官方网站vue开发wordpress
  • 那个网站可以做网站测速对比网页设计与制作心得体会1000
  • wordpress nginx php.ini广州seo招聘网
  • 网页设计与网站建设项目教程做网站能力介绍
  • 网站免费网站免费陪玩wordpress 整合ck
  • 局域网多网站建设营销型网站传统网站
  • 不限空间的免费网站传奇网站模板免费下载
  • 企业 网站 制作网站怎么做端口映射
  • 台州做网站最好的官方网站免费制作
  • 廉江网站制作wordpress json 时间
  • 溧阳城乡建设厅网站陕西省建设厅网站月报
  • 个人建立网站网页设计模板免费下载田田田田田田田田田田
  • 网站数据库连接出错wordpress app 发布时间
  • 一流的句容网站建设如何设计制作一般的企业网站
  • php可视化网站开发工具昆山城乡建设局网站
  • 微网站的链接怎么做网站无备案无法登入
  • 舟山市建设信息港网站打不开网站营销外包公司简介
  • 淘客免费网站建设免费建站赚钱
  • 商务网站建设策划书2000字网站开发费算无形资产吗
  • 织梦建的网站在哪户外广告公司
  • 网络推广公司网站郑州短视频培训机构
  • 做网站学多长时间可以学会网站必须做ipv6
  • 甘肃网络公司网站建设中装建设公司待遇好吗
  • 电子商务网站 开发厦门seo招聘
  • 北京网站开发制作公司网页设计教育培训