最新要闻
- 天天快消息!男生考研分到高中母校被班主任监考:网友一句话扎心
- 天天信息:山东小伙用1个月微缩30倍农村老屋:惟妙惟肖
- 每日播报!2022年优化最差游戏榜单出炉:《巫师3》次世代版上榜
- 世界通讯!能跑虚幻5特效!Centerpiece机械键盘自带CPU+GPU
- 环球滚动:康辉被调侃为“天选打工人”:连上六天班、领带惹眼
- 世界百事通!Redmi K60首款素皮机身揭秘:参照跑车内饰 拟真缝线工艺
- 上海今起对快递外卖每人每天补贴60元 元旦春节补贴150元
- 全球观焦点:15.5小时!阿里云史上最长大规模中断:官方公告四大问题
- 不吃饭光吃补充剂 真的可以避免营养缺乏吗?
- 历时9个月 时速350高铁成功“穿海入城”
- 别再说RTX 4090功耗比A卡高了:4K 120帧仅需150W
- 简讯:权威结果出炉:今年画质最好的游戏有答案了
- 炉石关服前夕:网易同类卡牌游戏《秘境对决》宣布恢复运营
- 环球热议:大货车雪地滑坡 山东小伙神操作“拔草相助”!后续令网友感动
- 超长寿命TLC闪存 金邦2TB PCIe 4.0硬盘679元:5GB/s速度
- 热门:再不努力就要归零 2nm工艺成日本半导体最后的机会
广告
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
AcWing241. 楼兰图腾
(相关资料图)
传送门
题目大意
\(\qquad\)\(1.\)给你一个序列,让你统计三个数\(i,j,k\)(\(i
解题思路
\(\qquad\)我们已经知道如何利用树状数组求出一个数的后面有多少个数比它小。所以我们可以采取这种算法:\(\qquad\)\(1.\)对于^
字符,我们需要的其实是:\(\qquad\)\(\qquad\)\(a.\)找出每个数i
的前面比它小的字符数,记作l[i]
\(\qquad\)\(\qquad\)\(b.\)找出每个数i
后面比它大的字符数,记作r[i]
\(\qquad\)\(\qquad\)然后根据\(\color{#ff003f}{乘法原理}\),当一个数\(num\)被当做分界点\(j\)的时候,此时第一个数\(i\)的选法有l[num]
种(只要比\(num\)小且在\(num\)的前面就行),第三个数\(k\)的选法有r[num]
种(只要比\(num\)大而且在\(num\)的后面就行),所以以\(num\)为分界点时,方案有\(l[num] \times r[num]\),而在一个序列中,每个数都可以作为分界点,所以枚举每个数,用resA
统计\(\qquad\)\(2.\)同样地对于字符V
,我们也这样统计。\(\\\)
解题代码
这里代码放两份,一份是规矩扫描,另一份是边扫描第二次边统计。
代码1
#include #include #include using namespace std;using LL = long long;const int N = 2e5 + 10;int n, a[N], Al[N], Bl[N], tr[N], Ar[N], Br[N];void add(int x, int v) { for (; x <= n; x += x & -x) tr[x] += v;}int ask(int x) { int res = 0; for (; x; x -= x & -x) res += tr[x]; return res;}int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); for (int i = 1; i <= n; i ++ ) { int j = a[i]; Al[j] += ask(j - 1), Ar[j] += ask(n) - ask(j); //Al是一个数前面比它小的,Ar是一个数前面比它大的 add(j, 1); } memset(tr, 0, sizeof tr); LL resA = 0, resV = 0; for (int i = n; i; i -- ) { int j = a[i]; Br[j] += ask(j - 1), Bl[j] += ask(n) - ask(j); //Br是后面比它小的,Bl是后面比它大的 add(j, 1); } for (int i = 1; i <= n; i ++ ) { int j = a[i]; resA += (LL) Al[j] * Br[j]; resV += (LL) Ar[j] * Bl[j]; } printf("%lld %lld\n", resV, resA); return 0;}
代码2
#include #include #include using namespace std;using LL = long long;const int N = 2e5 + 10;int n, a[N], low[N], big[N], tr[N];void add(int x, int v) { for (; x <= n; x += x & -x) tr[x] += v;}int ask(int x) { int res = 0; for (; x; x -= x & -x) res += tr[x]; return res;}int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); for (int i = 1; i <= n; i ++ ) { int j = a[i]; low[j] += ask(j - 1), big[j] += ask(n) - ask(j); add(j, 1); } memset(tr, 0, sizeof tr); LL resA = 0, resV = 0; for (int i = n; i; i -- ) { int j = a[i]; resA += (LL) low[j] * ask(j - 1); resV += (LL) big[j] * (ask(n) - ask(j)); add(j, 1); } printf("%lld %lld\n", resV, resA); return 0;}
\(\color{Green}{成功AC!}\)
-
天天速递!CentOS7配置静态IP
一:编辑ifcfg-ens33cd etc sysconfig network-scripts viifcfg-ens33二:BOOTPROTO修改为static并添加以下几行BOOTPR
来源: AcWing241. 楼兰图腾
天天速递!CentOS7配置静态IP
天天快消息!男生考研分到高中母校被班主任监考:网友一句话扎心
天天信息:山东小伙用1个月微缩30倍农村老屋:惟妙惟肖
MAUI新生6.1-Shell导航视觉层次结构
每日播报!2022年优化最差游戏榜单出炉:《巫师3》次世代版上榜
世界通讯!能跑虚幻5特效!Centerpiece机械键盘自带CPU+GPU
环球滚动:康辉被调侃为“天选打工人”:连上六天班、领带惹眼
世界百事通!Redmi K60首款素皮机身揭秘:参照跑车内饰 拟真缝线工艺
上海今起对快递外卖每人每天补贴60元 元旦春节补贴150元
全球观焦点:15.5小时!阿里云史上最长大规模中断:官方公告四大问题
不吃饭光吃补充剂 真的可以避免营养缺乏吗?
历时9个月 时速350高铁成功“穿海入城”
别再说RTX 4090功耗比A卡高了:4K 120帧仅需150W
简讯:权威结果出炉:今年画质最好的游戏有答案了
炉石关服前夕:网易同类卡牌游戏《秘境对决》宣布恢复运营
今日最新!洛谷 P5721 【入门3】循环结构
【pygame游戏】用Python实现一个蔡徐坤大战篮球的小游戏,可还行?【附源码】
环球热议:大货车雪地滑坡 山东小伙神操作“拔草相助”!后续令网友感动
超长寿命TLC闪存 金邦2TB PCIe 4.0硬盘679元:5GB/s速度
热门:再不努力就要归零 2nm工艺成日本半导体最后的机会
教你用JavaScript实现搜索展开
天天新资讯:李斌:创业的没有几个真的是骗子 要多鼓励
AMD 8年真身接连被破 Intel 13代酷睿“开挂“:超频无敌了
【焦点热闻】索尼被质疑虚假宣传:上市两年后 PS5仍不支持8K
中国千年酒文化传承 酒祖杜康白酒大促:礼盒装110两瓶
今日聚焦!李斌再回应蔚来数据泄露:会承担所有责任 哪怕破产也不妥协
环球微动态丨「杂题乱写」AtCoderDP26 题
(二)elasticsearch 源码目录
【新视野】碳纤维纹理后盖!Redmi K60回归硬核设计:刀锋战士理念
速看:无惧严寒!网易严选牛奶绒床品四件套:159元起
新的全国铁路列车运行图实行:石家庄至北京将实现一小时通达
新版以太坊Ethereum库ethersV5.0配合后端Golang1.18实时链接区块链钱包(Metamask/Okc)以及验签操作
环球关注:高速上飞来钢管插进驾驶室:差点害死驾驶员
热消息:联想:小红点会在ThinkPad笔记本上永远存在
天天头条:正式发布前 盒装RTX 4070 Ti线下偷跑:售价感人
天天热资讯!保时捷为Taycan推出全新充电器:充电速度提升一倍 改装费用上万
环球通讯!Epic喜加一!免费送大作《地铁》:下款将是《死亡搁浅》
每日头条!2023考研报告发布:“逆向考研”成亮点!附报告源文
世界快播:锐龙7000系列三款非X型号曝光:价格感受下
囧!日本老师暴打初二男生 因学“左手定则”时比中指
老人故意推倒摩托车损坏被抓:车主回应希望判决不手软 惯犯了
焦点速递!Sentinel的规则
天天热议:一加11下周官宣:安卓性能天花板
MAUI新生5.3-Layout布局类控件难点
国产OS统信UOS家庭版22.0明年1月发布:免费用1年 可与Windows共存
全靠移民硬撑?美国人口增长率仍贴近历史低位
视点!18岁女生因焦虑2个月减25斤:最终瘦成95斤
天天消息!男子无聊送外卖发现2小时挣150:开豪车也干
天天精选!Kubernetes监控手册03-宿主监控实操
今日观点!一路用到安卓17?OPPO将提供4年ColorOS重大更新
环球即时看!同价位罕见!雷军:Redmi K60系列这三款全都上2K直屏
微资讯!“联盟号”发生泄漏:俄罗斯或派遣救援飞船接回机组人员
世界播报:cmake-4
Redmi可穿戴新品公布:手表、耳机全都有
行业最快!红魔8 Pro系列搭载520Hz游戏体感肩键:毫秒级触控响应
《阿凡达2:水之道》国内票房突破6亿:卡梅隆光环褪色 回本太难
每日焦点!终结起火、爆炸困扰!红旗全固态电芯试制完成:10Ah级大容量
27款笔记软件的介绍
全球视点!ts10_使用webpack打包ts文件3
环球今日报丨C#封装GRPC类库及调用简单实例
百事通!Spring IOC官方文档学习笔记(四)之依赖项(下)
【天天报资讯】Web 标准 & W3C 规范
今日热闻!研究人员在柬埔寨发现超级蚊子:对杀虫剂免疫
焦点关注:C++基础3
焦点滚动:惧怕《阿凡达2》 输不起?郭帆回应《流浪地球2》撤档 春节见
播报:Redmi K60全系标配2K柔性屏 专家:国产技术已破局超越
环球即时看!以小博大外小内大,Db数据库SQL优化之小数据驱动大数据
全球快资讯丨最高799元 迪士尼再发布涨价公告:开业以来已涨4次
质感一绝!一加11证件照公布:双曲面屏、流动天阶设计
速递!共计100小时:全球首架C919自12月26日起验证飞行
ts09_使用webpack打包ts文件2
环球热头条丨2022贺岁档票房破10亿!《阿凡达:水之道》5.9亿元能拯救院线吗
曾因“双标”遭网友痛批:好丽友旗舰店发布闭店公告
全球热头条丨AcWing1134/洛谷P1144 最短路计数
WPF开发之Prism详解【内附源码】
不愧是宝马 因机油渗漏:近500台S1000系列摩托车被召回
最新快讯!Codeforces 1097 G Vladislav and a Great Legend 题解 (DP)
焦点日报:肾脏衰竭 球王贝利病情继续恶化:家人开始筹备葬礼
02.关于线程你必须知道的8个问题(上)
当前头条:喜提安卓13!小米平板5/Pro 12.4推送MIUI 14开发版:支持光子引擎
每日热文:SSD/内存白菜价难持续:国产厂商被制裁 三星等大厂减产提价
天天热点!我的2022年个人总结
环球焦点!FreeSWITCH学习笔记:EventSocket
AMD RX7900被吐槽空气卡 溢价千元普遍:国内用户持币等 买它还是4080?
【世界播资讯】小米又一爆款诞生!小米净水器销量破500万台
热推荐:新冠后丧失嗅觉的关键原因找到了 科学家:长期失灵也能恢复
环球通讯!3199元起 爱奇艺奇遇MIX VR一体机发布:4K级3000吋巨幕 支持Steam串流
焦点快播:趁早加满!下轮国内油价上调几成定局
影驰发布全球第三款8GHz DDR5内存:如此"光污染" 绝了
焦点速讯:电解质水到底有没有用?我来告诉你
美国人预期寿命降至25年来最低:三大因素导致一半的死亡
11月智能手机销量出炉:小米大卖340万台 国产第一
天天短讯!多方安全计算(6):MPC中场梳理
云原生时代,18 岁的 NGINX 过时了吗?
AcWing1131. 拯救大兵瑞恩
今日最新!东京奥运会陷入丑闻:审计人员发现实际成本高出20%
经典大富翁游戏《富甲天下3》登陆Steam 2023年1月9日发售
全球新资讯:Apache Log4j 远程代码执行漏洞(CVE-2021-44228、CVE-2021-45046)修复方案
全球速看:美国“毅力号”在火星上丢了个东西:意义重大