Easy DP Problem

https://codeforces.com/gym/102770/problem/E

给一个dp转移式子,求dp[m][k] m=r-l+1

dp不是玄学吗?

话说给我了一个式子,我直接转不就好了,发现n<1e5,那算了

分析一个小例子发现dp[m][k]=\sum_{i=1}^{m} i^{2}+\sum_{val=No.1}^{No.k} val

前面式子用循环求或者公式,后面维护区间前k之和即可

主席树板子

记得io优化,开ll,还有多组样例,主席树清空

// Problem: E. Easy DP Problem
// Contest: Codeforces - The 17th Zhejiang Provincial Collegiate Programming Contest
// URL: https://codeforces.com/gym/102770/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<vector>
#define INF 1e6
using namespace std;
typedef long long ll;
const int N=1e5+9;
int a[N];
vector<int> X;
//主席树
ll binary(int x){return lower_bound(X.begin(),X.end(),x)-X.begin()+1;
}
struct ZXSEG{struct node{int l,r;//左右儿子,关系int s;//节点值域中有多少个数ll sum;ll val;}seg[N*22];//n*(logn*3);logn+3向上取整#define tl(id) seg[id].l//宏定义简洁#define tr(id) seg[id].rint root[N],index;//根节点,节点数量void reset(int n){for(int i=1;i<=n;i++){root[i]=0;}index=0;}void build(int &id,int l,int r){//传引用,通过子空间id值给父空间的gx[0],gx[1]赋值id=++index;if(l==r){return;}int mid=(l+r)>>1;build(tl(id),l,mid);build(tr(id),mid+1,r);}/*递归建立各个历史版本的线段树post是前一个版本的节点指针,curr是当前版本的节点指针curr是传引用,通过子空间curr值,给父空间的tl(curr),tr(curr)赋值*/void insert(int post,int &curr,int l,int r,int v){curr=++index;//开新节点seg[curr]=seg[post];//赋值seg[curr].s++;//更新seg[curr].sum+=X[v-1];if(l==r){seg[curr].val=X[v-1];return;}int mid=(l+r)>>1;if(v<=mid){//在左边递归insert(tl(post),tl(curr),l,mid,v);}else{insert(tr(post),tr(curr),mid+1,r,v);}}/*找区间[l,r]内的第k小,插入r的历史版本,进行二分[l,r]==[1,r]-[1,l-1];*/ll query(int post,int curr,int l,int r,ll k){if(l==r){//return seg[curr].val*k;}int mid=(l+r)>>1;int s=seg[tr(curr)].s-seg[tr(post)].s;//变化信息if(k<=s){//找k的位置return query(tr(post),tr(curr),mid+1,r,k);}else{return seg[tr(curr)].sum-seg[tr(post)].sum+query(tl(post),tl(curr),l,mid,k-s);//减去左边的}}
}t;
void solve(){int n;cin>>n;X.clear();t.reset(n);for(int i=1;i<=n;i++){cin>>a[i];X.push_back(a[i]);}sort(X.begin(),X.end());X.erase(unique(X.begin(),X.end()),X.end());int xn=X.size();t.build(t.root[0],1,xn);for(int i=1;i<=n;i++){t.insert(t.root[i-1],t.root[i],1,xn,binary(a[i]));}int q;cin>>q;for(int i=1;i<=q;i++){int l,r,k;cin>>l>>r>>k;ll m=(r-l+1);ll t1=m*(m+1ll)*(2ll*m+1ll);t1/=6ll;ll t2=t.query(t.root[l-1],t.root[r],1,xn,k);ll ans=t1+t2;cout<<ans<<'\n';}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){solve();}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/392002.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Unity 资源之 Break Items - Toon VFX破碎物品与卡通硬币动画分享

Unity 特效资源分享 - 破碎物品与卡通硬币动画 一、前言二&#xff0c;资源包内容三、免费获取资源包 一、前言 今天为大家带来一份超级实用的视觉特效资源分享&#xff01;我们精心整理了 6 个令人惊叹的破碎物品效果和 1 个萌趣十足的卡通硬币动画视觉特效&#xff0c;让您的…

传统ERP vs 零代码ERP:企业究竟应当选哪条路?

在大环境变幻莫测的今天&#xff0c;每个企业都像是航行在数字化浪潮中的一艘船&#xff0c;而ERP系统&#xff0c;就像是这艘船的导航系统&#xff0c;帮助企业精准定位、高效航行。 但面对传统ERP与新兴零代码ERP&#xff0c;不少企业家可能会感到迷茫&#xff1a;是该坚守传…

火猫奥运会:西班牙国奥VS摩洛哥国奥预测,进决赛已无悬念

北京时间8月6日,巴黎奥运会男足半决赛西班牙国奥VS摩洛哥国奥的巅峰对决将正式打响。西班牙国奥被外界视为本届奥运会夺金大热门,球队在八强战中横扫日本国奥,已经露出冠军相。要知道日本国奥整体实力并不差,小组赛发挥抢眼。没想到,日本国奥八强战遇到夺金大热门西班牙国奥,竟…

PointNet和PointNet++论文解读

目录 一、导言 二、PointNet介绍 三、PointNet网络结构 1、损失函数 2、正则化 四、PointNet 1、分层次的点集抽象层 五、PointNet网络结构 1、点特征传播 2、分组方法 一、导言 PointNet来自CVPR2017&#xff0c;是最早直接处理点云数据用于计算机视觉的模型&#…

优思学院|质量经理如何开展工作?

如果你本来是一个质量工程师&#xff0c;经过了多年的努力&#xff0c;终于成为质量经理&#xff0c;你或者会很困惑&#xff0c;我到底应该如何开展质量管理的工作呢&#xff1f;质量管理对于任何企业来说都是至关重要的&#xff0c;它不仅决定了产品的合格率和市场竞争力&…

STL中的vector以及简单实现

vector的简单介绍&#xff1a; 头文件&#xff1a; #include<vector> vector是属于STL的一员&#xff0c;虽然vector的英文意思是向量&#xff0c;但是vector就是一个顺序表&#xff1b; 对于vector来说&#xff0c;面对string的设计的复杂和冗余&#xff0c;vector就…

【从零开始一步步学习VSOA开发】创建VSOA的server端

创建VSOA的server端 创建工程 参考 hellovsoa 工程&#xff0c;创建 server 工程&#xff0c;工程源码修改如下&#xff1a; #include <stdio.h> #include <stdlib.h> #include <string.h> #include <netinet/in.h> #include <arpa/inet.h> #…

【数据结构面试有那些常见问题?】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

提升实训效果,智慧校园实验室建设计划解析

在智慧校园解决方案中&#xff0c;实训管理系统的实验室建设计划功能深刻展示了基础设置建设的重要性&#xff0c;它不仅聚焦于教育资源的精准投放&#xff0c;更是教学质量与科研创新的重要推手。这一功能的核心价值&#xff0c;在于运用先进的数字化工具&#xff0c;实现从需…

RabbitMQ高级特性 - 消费者消息确认机制

文章目录 RabbitMQ 消息确认机制背景消费者消息确认机制概述手动确认&#xff08;RabbitMQ 原生 SDK&#xff09;手动确认&#xff08;Spring-AMQP 封装 RabbitMQ SDK&#xff09;AcknowledgeMode.NONEAcknowledgeMode.AUTO&#xff08;默认&#xff09;AcknowledgeMode.MANUAL…

JAVA通过debezium实时采集mysql数据

前期准备 需要提前安装mysql并且开启binlog,需要准备kafka和zookeeper环境 示例采用debezium1.9.0版本 Maven配置 <version.debezium>1.9.0.Final</version.debezium> <dependency> <groupId>io.debezium</groupId> <artifactId>debe…

Java获取exe文件详细信息:产品名称,产品版本等

使用Maven项目&#xff0c;在pom.xml文件中注入&#xff1a; <dependency><groupId>com.kichik.pecoff4j</groupId><artifactId>pecoff4j</artifactId><version>0.4.1</version></dependency> 程序代码&#xff1a; import …

Sun Frame:基于 SpringBoot 的轻量级开发框架(个人开源项目)

文章目录 &#x1f31e; Sun Frame&#xff1a;基于 SpringBoot 的轻量级开发框架&#xff08;个人开源项目&#xff09;&#x1f680; 欢迎使用 Sun Frame&#x1f31f; 项目亮点&#x1f4e6; 模块结构&#x1f310; Sun-Cloud&#x1f4e6; Sun-Common &#x1f4a1; 示例与…

微力同步如何安装使用并使用内网穿透配置公网地址远程访问

文章目录 1.前言2. 微力同步网站搭建2.1 微力同步下载和安装2.2 微力同步网页测试2.3 内网穿透工具安装 3.本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置 4. 公网访问测试5. 结语 1.前言 私有云盘作为云存储概念的延伸&#xff0c;虽然谈不上多么新颖&#xff0c;但是其广…

主成分分析和线性判别分析

主成分分析 (PCA) PCA 是一种线性降维方法&#xff0c;通过投影到主成分空间&#xff0c;尽可能保留数据的方差。 原理 PCA 通过寻找数据投影后方差最大的方向&#xff0c;主成分是这些方向上的正交向量。 公式推理 对数据中心化&#xff1a; 其中&#xff0c;μ 是数据的…

“微软蓝屏”事件敲响网络安全的警钟

文章目录 前言一、对网络安全的警醒二、我们如何应对&#xff1f;总结 前言 “微软蓝屏”事件是一次由微软合作伙伴CrowdStrike的终端安全产品更新与操作系统内核冲突导致的全球性技术故障。这一事件不仅影响了多个国家的航空、银行、金融、零售、餐饮等多个行业&#xff0c;还…

吴恩达老师机器学习-ex8

data1 导入库&#xff0c;读取数据并进行可视化 因为这次的数据是mat文件&#xff0c;需要使用scipy库中的loadmat进行读取数据。 通过对数据类型的分析&#xff0c;发现是字典类型&#xff0c;查看该字典的键&#xff0c;可以发现又X等关键字。 import numpy as np import…

十七、Intellij IDEA2022.1.1下载、安装、激活

目录 &#x1f33b;&#x1f33b; 一、下载二、 安装三、激活 一、下载 官网下载地址 本地直接下载 目前Intellij IDEA的最新版本已经更新到了 2024.1.4&#xff0c;由于最新版本可能存在不稳定的问题&#xff0c;此处选择其他版本进行下载&#xff0c;此处以2022.1.1为例进行下…

【Spring】Bean详细解析

1.Spring Bean的生命周期 整体上可以简单分为四步&#xff1a;实例化 —> 属性赋值 —> 初始化 —> 销毁。初始化这一步涉及到的步骤比较多&#xff0c;包含 Aware 接口的依赖注入、BeanPostProcessor 在初始化前后的处理以及 InitializingBean 和 init-method 的初始…

基于STM32的智能家居安防系统教程

目录 引言环境准备智能家居安防系统基础代码实现&#xff1a;实现智能家居安防系统 门窗传感器模块视频监控模块报警与通知模块用户界面与远程控制应用场景&#xff1a;家庭安防与监控常见问题与解决方案收尾与总结 引言 随着智能家居的普及&#xff0c;家庭安防系统成为保护…