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

2023NOIP A层联测6 数点

题目大意

给你一个排列 p p p,对于每一个 i i i,我们在平面上,放置一个点 ( i , p i ) (i,p_i) (i,pi)。对于坐标上下限都在 1 ∼ n 1\sim n 1n内的全体 ( n ( n + 1 ) 2 ) 2 (\frac{n(n+1)}{2})^2 (2n(n+1))2矩形,求每个矩形内部点数的 k k k次方之和。

形式化地,请你计算

∑ 1 ≤ l ≤ r ≤ n ∑ 1 ≤ d ≤ u ≤ n ∣ { i ∣ l ≤ i ≤ r ∨ d ≤ p i ≤ u } ∣ \sum\limits_{1\leq l\leq r\leq n}\sum\limits_{1\leq d\leq u\leq n}|\{i|l\leq i\leq r\vee d\leq p_i\leq u\}| 1lrn1dun{ilirdpiu}

1 ≤ n ≤ 1 0 5 , 1 ≤ k ≤ 3 1\leq n\leq 10^5,1\leq k\leq 3 1n105,1k3


题解

我们可以考虑拆贡献,点数的 k k k次方可以看成选 k k k个点的方案的线性组合。

什么意思呢?就是在这 n n n个点中有序地可重地选择 k k k个点,将所有包含这 k k k个点的矩形的贡献 + 1 +1 +1,注意所有从 n n n个点中有序地可重地选 k k k个点的方案都要被计算贡献。

为什么可以这样呢?对于每个矩形,设这个矩形内的点数为 t t t,在这个矩形中有序地可重地选 k k k个点的方案数为 t k t^k tk,也就是说这个矩形在上面计算贡献的时候将贡献加了 t k t^k tk次一。

下面,我们来求 k k k为不同的值时的答案。

k = 1 k=1 k=1

对每个点 ( x , p x ) (x,p_x) (x,px),答案的贡献增加 x × ( n − x + 1 ) × p x × ( n − p x + 1 ) x\times (n-x+1)\times p_x\times (n-p_x+1) x×(nx+1)×px×(npx+1)

k = 2 k=2 k=2

我们考虑选的两个点相同的情况和两个点不同的情况。

对于两个点相同的情况,这其实就是 k = 1 k=1 k=1的情况,每种情况会被算一次。

对于两个点不同的情况,我们可以分为顺序对和逆序对来考虑:

  • 对于顺序对 x < y , p x < p y x<y,p_x<p_y x<y,px<py,其贡献为 x × p x × ( n − y + 1 ) × ( n − p y + 1 ) x\times p_x\times (n-y+1)\times (n-p_y+1) x×px×(ny+1)×(npy+1),将 x × p x x\times p_x x×px存入树状数组中,再用 ( n − y + 1 ) × ( n − p y + 1 ) (n-y+1)\times (n-p_y+1) (ny+1)×(npy+1)来乘即可
  • 对于逆序对 x < y , p x > p y x<y,p_x>p_y x<y,px>py将排列翻转之后按顺序对的方法来做即可

因为选点是有序的,每种顺序对和逆序对都用两种选法被选到,所以两个点不同的情况的贡献要乘 2 2 2

k = 3 k=3 k=3

k = 1 k=1 k=1的贡献计算一次(三次选择同一个点), k = 2 k=2 k=2的贡献计算两次(三次选择两个不同的点),下面再考虑三次选择三个不同的点的贡献。

分为两种本质不同的情况:

情况1
------
|*   |
| *  |
|  * |
------

这种情况出现了 2 2 2次(按 i i i左右翻转,总共有 2 2 2次),用两个树状数组维护即可。

情况2
------
|  * |
|*   |
| *  |
------

这种情况总共出现了 4 4 4次(按 i i i左右翻转,按 p i p_i pi上下翻转,四个角度各一次,总共有 4 4 4次),用线段树来维护即可。可以在加入第一个点时直接在对应位置上加数,在加入第二个点时将其后缀乘上对应的数,再加入第三个点时查询前缀和。

因为选点是有序的,每种顺序对和逆序对都用六种选法被选到,所以两个点不同的情况的贡献要乘 6 6 6

时间复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)

code

#include<bits/stdc++.h>
#define lc k<<1
#define rc k<<1|1
using namespace std;
const long long mod=998244353;
int n,K,p[100005];
long long tr1[100005],tr2[100005];
long long s[500005],hv[500005],ly[500005];
int lb(int i){return i&(-i);
}
void pt1(int i,long long v){while(i<=n){tr1[i]=(tr1[i]+v)%mod;i+=lb(i);}
}
long long find1(int i){long long re=0;while(i){re=(re+tr1[i])%mod;i-=lb(i);}return re;
}
void pt2(int i,long long v){while(i<=n){tr2[i]=(tr2[i]+v)%mod;i+=lb(i);}
}
long long find2(int i){long long re=0;while(i){re=(re+tr2[i])%mod;i-=lb(i);}return re;
}
void build(int k,int l,int r){s[k]=hv[k]=ly[k]=0;if(l==r) return;int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);
}
void down(int k){s[lc]=(s[lc]+hv[lc]*ly[k])%mod;s[rc]=(s[rc]+hv[rc]*ly[k])%mod;ly[lc]=(ly[lc]+ly[k])%mod;ly[rc]=(ly[rc]+ly[k])%mod;ly[k]=0;
}
void ch(int k,int l,int r,int x,long long y){if(l==r&&l==x){hv[k]=y;s[k]=ly[k]=0;return;}if(ly[k]) down(k);int mid=l+r>>1;if(x<=mid) ch(lc,l,mid,x,y);else ch(rc,mid+1,r,x,y);hv[k]=(hv[lc]+hv[rc])%mod;s[k]=(s[lc]+s[rc])%mod;
}
void ts(int k,int l,int r,int x,int y,long long v){if(l>=x&&r<=y){ly[k]=(ly[k]+v)%mod;s[k]=(s[k]+v*hv[k])%mod;return;}if(ly[k]) down(k);int mid=l+r>>1;if(x<=mid) ts(lc,l,mid,x,y,v);if(y>mid) ts(rc,mid+1,r,x,y,v);s[k]=(s[lc]+s[rc])%mod;
}
long long find(int k,int l,int r,int x,int y){if(l>=x&&r<=y) return s[k];if(ly[k]) down(k);int mid=l+r>>1;long long re=0;if(x<=mid) re=(re+find(lc,l,mid,x,y))%mod;if(y>mid) re=(re+find(rc,mid+1,r,x,y))%mod;return re;
}
long long gt(){long long re=0;build(1,1,n);for(int i=1;i<=n;i++){re=(re+find(1,1,n,1,p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;ts(1,1,n,p[i],n,p[i]);ch(1,1,n,p[i],i);}return re;
}
long long gt1(){long long re=0;for(int i=1;i<=n;i++){re=(re+1ll*i*(n-i+1)%mod*p[i]%mod*(n-p[i]+1)%mod)%mod;}return re;
}
long long gt2(){long long re=0;for(int i=1;i<=n;i++){re=(re+find1(p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;pt1(p[i],1ll*i*p[i]%mod);}for(int i=1;i<=n;i++){tr1[i]=0;if(i<n-i+1) swap(p[i],p[n-i+1]);}for(int i=1;i<=n;i++){re=(re+find1(p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;pt1(p[i],1ll*i*p[i]%mod);}for(int i=1;i<=n;i++){tr1[i]=0;if(i<n-i+1) swap(p[i],p[n-i+1]);}return re;
}
long long gt3(){long long re=0;for(int i=1;i<=n;i++){long long now=find1(p[i]);pt1(p[i],1ll*i*p[i]%mod);re=(re+find2(p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;pt2(p[i],now);}for(int i=1;i<=n;i++){tr1[i]=tr2[i]=0;if(i<n-i+1) swap(p[i],p[n-i+1]);}for(int i=1;i<=n;i++){long long now=find1(p[i]);pt1(p[i],1ll*i*p[i]%mod);re=(re+find2(p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;pt2(p[i],now);}for(int i=1;i<=n;i++){tr1[i]=tr2[i]=0;if(i<n-i+1) swap(p[i],p[n-i+1]);}re=(re+gt())%mod;for(int i=1;i<=n;i++)if(i<n-i+1) swap(p[i],p[n-i+1]);re=(re+gt())%mod;for(int i=1;i<=n;i++)p[i]=n-p[i]+1;re=(re+gt())%mod;for(int i=1;i<=n;i++)if(i<n-i+1) swap(p[i],p[n-i+1]);re=(re+gt())%mod;return re;
}
int main()
{freopen("points.in","r",stdin);freopen("points.out","w",stdout);scanf("%d%d",&n,&K);for(int i=1;i<=n;i++){scanf("%d",&p[i]);}if(K==1) printf("%lld",gt1());else if(K==2)  printf("%lld",(gt1()+2*gt2())%mod);else{printf("%lld",(gt1()+6*gt2()+6*gt3())%mod);}return 0;
}

相关文章:

2023NOIP A层联测6 数点

题目大意 给你一个排列 p p p&#xff0c;对于每一个 i i i&#xff0c;我们在平面上&#xff0c;放置一个点 ( i , p i ) (i,p_i) (i,pi​)。对于坐标上下限都在 1 ∼ n 1\sim n 1∼n内的全体 ( n ( n 1 ) 2 ) 2 (\frac{n(n1)}{2})^2 (2n(n1)​)2矩形&#xff0c;求每个矩形…...

Jmeter 链接MySQL测试

1.环境部署 1.1官网下载MySQL Connector https://dev.mysql.com/downloads/connector/j/ 1.2 解压后&#xff0c;将jar放到jmeter/lib目录下 1.3 在测试计划中添加引用 2.脚本设置 2.1设置JDBC Connection Configuration 先添加一个setUp线程中&#xff0c;在setUp中添加“…...

jwt的了解和使用以及大致代码分析

jwt简介 以下介绍来自官网&#xff08;https://jwt.io/&#xff09; SON Web 令牌 &#xff08;JWT&#xff09; 是一种开放标准 &#xff08;RFC 7519&#xff09;&#xff0c;它定义了一种紧凑且独立的方式&#xff0c;用于在各方之间以 JSON 对象的形式安全地传输信息。此信…...

uniapp中videojs、renderjs的使用

在uniapp中使用了某些前端库或iframe&#xff0c;需要操作这些库中的dom的时候&#xff0c; 而uni上又没有document等基础对象。也就无法操作这些dom去实现一些交互逻辑&#xff0c;那么&#xff0c;涉及到这些的前端类库就无法使用&#xff0c;例如html2、canvas、image、vide…...

AIGC AI绘画 Midjourney 参数大全详细列表

AIGC ChatGPT 职场案例 AI 绘画 与 短视频制作, Power BI 商业智能 68集, 数据库Mysql8.0 54集 数据库Oracle21C 142集, Office 2021实战, Python 数据分析, ETL Informatica 案例实战 Excel 2021实操,函数大全,图表大全,大屏可视化制作 加技巧500集 数据分析可视化T…...

安装hadoop,并配置hue

0、说明 对于大数据学习的初始阶段&#xff0c;我也曾尝试搭建相应的集群环境。通过搭建环境了解组件的一些功能、配置、原理。 在实际学习过程中&#xff0c;我更多的还是使用docker来快速搭建环境。 这里记录一下我搭建hadoop的过程。 1、下载hadoop 下载地址&#xff1a;…...

23种经典设计模式:单例模式篇(C++)

前言&#xff1a; 博主将从此篇单例模式开始逐一分享23种经典设计模式&#xff0c;并结合C为大家展示实际应用。内容将持续更新&#xff0c;希望大家持续关注与支持。 什么是单例模式&#xff1f; 单例模式是设计模式的一种&#xff08;属于创建型模式 (Creational Pa…...

ros中对move_base的调用

move_base包中自带costmap2d, global planner 等功能 也可以直接调用其中make_plan进行路径规划 #include "geometry_msgs/PoseStamped.h" #includde "nav_msgs/GetPlan.h"void fillPathRequest(nav_msgs::GetPlan::Request &request, float start_x…...

Git从本地库撤销已经添加的文件或目录

场景 在提交时, 误将一个目录添加到了暂存区, 而且commit 了本地库,同批次commit 的还有其他需要提交的文件。 commit 之后发现这个目录下所有的文件都不需要提交, 现在需要撤销这个提交, 使这个目录不被push到远端库。 这里以远端服务器github 为例,在Git GUI下看到的…...

百度SEO优化的特点(方式及排名诀窍详解)

百度SEO优化的特点介绍&#xff1a; 百度SEO优化是指对网站进行优化&#xff0c;使其在百度搜索引擎中获得更好的排名&#xff0c;进而获取更多的流量和用户。百度SEO优化的特点是综合性强、效果持久、成本低廉、投资回报高。百度的搜索算法不断更新&#xff0c;所以长期稳定的…...

Gin 文件上传操作(单/多文件操作)

参考地址: 单文件 | Gin Web Framework (gin-gonic.com)https://gin-gonic.com/zh-cn/docs/examples/upload-file/single-file/ 单文件 官方案例: func main() {router := gin.Default()// 为 multipart forms 设置较低的内存限制 (默认是 32 MiB)router.MaxMultipartMem…...

分类预测 | MATLAB实现KOA-CNN-LSTM开普勒算法优化卷积长短期记忆神经网络数据分类预测

分类预测 | MATLAB实现KOA-CNN-LSTM开普勒算法优化卷积长短期记忆神经网络数据分类预测 目录 分类预测 | MATLAB实现KOA-CNN-LSTM开普勒算法优化卷积长短期记忆神经网络数据分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述 1.MATLAB实现KOA-CNN-LSTM开普勒算法优化…...

Qt应用开发(基础篇)——列表视图 QListView

一、前言 QListView类继承于QAbstractItemView类&#xff0c;提供了一个列表或者图标视图的模型。 视图基类 QAbstractItemView QListView效果相当于Windows文件夹右键->查看->图标和列表&#xff0c;使用setViewMode()设置视图模式&#xff0c;并且提供setIconSize()函数…...

vue-6

一、声明式导航-导航链接 1.需求 实现导航高亮效果 如果使用a标签进行跳转的话&#xff0c;需要给当前跳转的导航加样式&#xff0c;同时要移除上一个a标签的样式&#xff0c;太麻烦&#xff01;&#xff01;&#xff01; 2.解决方案 vue-router 提供了一个全局组件 router…...

温度在线检测技术在电力电缆线路的应用

在电力电缆的日常运行检测中&#xff0c;针对电缆温度的状况&#xff0c;所采用的电力温度在线检测技术也得到了大范围的普及。电网系统中&#xff0c;其单位时间内可输送的电力能源受到其温度的变化影响。因此&#xff0c;采用更有效的方式实时检测电缆系统运行温度&#xff0…...

2023年中国自动化微生物样本处理系统竞争现状及行业市场规模分析[图]

微生物检测能够对感染性疾病的病原体或者代谢物进行检测分析&#xff0c;是IVD的细分领域之一。2022年中国体外诊断市场规模1424亿元。 2015-2022年中国体外诊断市场规模 资料来源&#xff1a;共研产业咨询&#xff08;共研网&#xff09; 微生物检测由于样本类型多样&#xf…...

硬链接和软连接的区别

软链接&#xff08;也称为软连接或符号链接&#xff09;是一种特殊的文件&#xff0c;其内容是另一个文件的路径。当你使用软链接时&#xff0c;实际上是在操作另一个文件。软链接的优点是它可以跨文件系统使用&#xff0c;因此可以跨分区或磁盘链接文件。此外&#xff0c;软链…...

保护隐私与增强网络安全之网络代理技术

目录 前言 一、网络代理技术原理 二、网络代理技术类型 1. HTTP代理 2. SOCKS代理 3. DNS代理 4. 加密代理 5. 反向代理 三、网络代理技术应用 1. 加速网络访问速度 2. 绕过网络限制 3. 保护个人隐私 4. 节省带宽 5. 改善网络安全 四、网络代理技术优缺点 网络…...

【每日一题】CF1680C. Binary String | 双指针 | 简单

题目内容 原题链接 给定一个长度为 n n n 的 01 01 01 字符串&#xff0c;对于一个子串 s u b sub sub &#xff0c;子串内部的 0 0 0 的数量为 x x x &#xff0c;子串以外的 1 1 1 的数量为 y y y &#xff0c;子串的代价为 m a x ( x , y ) max(x, y) max(x,y) &…...

10.selenium进阶

文章目录 1、嵌套网页1、1 什么是嵌套页面1、2 selenium获取嵌套页面的数据 2、执行JavaScript代码3、鼠标动作链4、selenium键盘事件5、其他方法5、1 选择下拉框5、2 弹窗的处理 6、selenium设置无头模式7、selenium应对检测小结 1、嵌套网页 ​ 在前端开发中如果有这么一个需…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

RushDB开源程序 是现代应用程序和 AI 的即时数据库。建立在 Neo4j 之上

一、软件介绍 文末提供程序和源码下载 RushDB 改变了您处理图形数据的方式 — 不需要 Schema&#xff0c;不需要复杂的查询&#xff0c;只需推送数据即可。 二、Key Features ✨ 主要特点 Instant Setup: Be productive in seconds, not days 即时设置 &#xff1a;在几秒钟…...

Qt的学习(二)

1. 创建Hello Word 两种方式&#xff0c;实现helloworld&#xff1a; 1.通过图形化的方式&#xff0c;在界面上创建出一个控件&#xff0c;显示helloworld 2.通过纯代码的方式&#xff0c;通过编写代码&#xff0c;在界面上创建控件&#xff0c; 显示hello world&#xff1b; …...

EEG-fNIRS联合成像在跨频率耦合研究中的创新应用

摘要 神经影像技术对医学科学产生了深远的影响&#xff0c;推动了许多神经系统疾病研究的进展并改善了其诊断方法。在此背景下&#xff0c;基于神经血管耦合现象的多模态神经影像方法&#xff0c;通过融合各自优势来提供有关大脑皮层神经活动的互补信息。在这里&#xff0c;本研…...