计算客 商品推荐走马灯(简单)(求区间全部连续的回文串价值)
计算 简单 推荐 价值 连续 全部 区间 商品
2023-09-27 14:23:30 时间
有一个新的研究显示,人在看见一系列的图片时,假设它们的排列有一定的轴对称性,则会更为认为赏心悦目。依据这个特性,作为阿里巴巴旗下重要的电子商务交易平台的淘宝,希望了解商品推荐的图片走马灯如今的赏心悦目情况。以便推断是否之后须要做出调整。比如,当价值分别为 1,2,1 的商品图片排列在一起的时候,人们能够看到它的全部非空区间 [1]、[2]、[1]、[1,2]、[2,1]、[1,2。1] 中有四个是轴对称的,所以这组图片的展示价值是全部轴对称的非空区间的全部价值总和 1 + 2 + 1 + (1 + 2 + 1) = 8。
输入格式对于如今淘宝商品推荐的图片走马灯序列里的图片,我们从左到右将它们自 1 開始依次递增编号。如今我们希望了解。对于每次由两个编号 li, ri 组成的第i次询问,若将
li 到 ri 的这些图片选出进行展示,他们的展示价值是多少。
第一行输入两个整数 n (1 ≤ n ≤ 105), m (1 ≤ m ≤ 105)。分别代表图片总数和询问次数。
第二行一共 n 个整数 ci (-100 ≤ ci ≤ 100),表示从编号 1 到编号 n 的图片价值。
接下来 m 行,每行两个整数 li, ri (1 ≤ li ≤ ri ≤ n)。表示一组询问 [li, ri]。
输入数据保证询问区间合法,图片价值 ci 满足 -100 ≤ ci ≤ 100。
对于简单版本号。1 ≤ n, m ≤ 300。
对于中等版本号,1 ≤ n ≤ 20000,1 ≤ m ≤ 3000;
对于困难版本号,1 ≤ n, m ≤ 100000。
输出格式
一共输出 m 行,每行输出一组询问相应的展示价值。
例子1
输入:
5 2 1 1 0 1 0 2 4 1 2
输出:
4 4
#include<stdio.h> #include<string.h> #include<string> #include<iostream> #include<queue> using namespace std; const int N = 200005; int main() { int n,m,c[N]; while(scanf("%d%d",&n,&m)>0) { for(int i=1; i<=n; i++) scanf("%d",&c[i]); int l,r; while(m--){ scanf("%d%d",&l,&r); long long ans=0; for(int i=l; i<=r; i++){ int tl,tr; long long tans=c[i]; ans+=tans; tl=i-1; tr=i+1; while(tl>=l&&tr<=r&&c[tl]==c[tr]){ tans=tans+c[tl]+c[tr]; ans+=tans; tl--;tr++; } tans=0; tl=i; tr=i+1; while(tl>=l&&tr<=r&&c[tl]==c[tr]){ tans=tans+c[tl]+c[tr]; ans+=tans; tl--;tr++; } } printf("%lld\n",ans); } } }
相关文章
- Google Earth Engine(GEE)——JavaScript基本功能介绍(单个几何特征的简单计算)
- linux中计算文本文件中某个字符的出现次数
- 云计算以及云计算周边词概念简单介绍
- 云计算对比IDC的优势简单说明-行云管家
- 中国跻身量子计算第一梯队,为何它是硬科技必争之地?丨两会唠科
- 云计算前沿—详解PaaS之Cloudfoundry
- 树莓派微计算机新玩法:构建免费个人云计算服务器
- 大数据实时处理:百分点实时计算架构和算法
- 【前端】JS耗时计算/时间转换/日期/本周/本月/格式化
- 《混合云计算》——2.4 检查云集成的需求
- 大数据与云计算、物联网的关系
- H3C 示例:计算子网内可用地址数
- 函数式编程世界观:计算、映射、流领域的描述语言
- 如何计算时间复杂度
- 《从问题到程序:用Python学编程和计算》——2.6 简单脚本程序
- 《数据科学R语言实践:面向计算推理与问题求解的案例研究法》一一2.6 对个人跑步时间的变化进行建模
- 长周期指标的计算优化方案
- 【历史上的今天】12 月 14 日:计算复杂性理论先驱出生;雅虎群组被关闭;W3C 召开第一次会议
- 云计算工具,框架,服务简单介绍
- 简单计算器、超速判断、用天平找小球、分段计算居民水费、猜数字游戏
- 钱包又要挨刀了:DDN升级EXAScaler Lustre高性能计算存储设备
- Vue-计算属性(computed)简单说明和使用
- 计算流体力学(CFD)技术将节约数据中心运营成本
- Python计算自由下落距离
- C++基础 简单计算