COGS 1260 三元数对
发布日期:2022-02-05 18:27:31 浏览次数:18 分类:技术文章

本文共 1760 字,大约阅读时间需要 5 分钟。

1260. 三元数对

★   输入文件:
three.in   输出文件:
three.out   
简单对比
时间限制:1 s   内存限制:128 MB

【题目描述】

Chineselyl 最近对一种叫做“三元数对”的东西非常感兴趣。在含有 n 个整数的序列 A1,A2,…An 中,三个数被称作“三元数对”当且仅当i<j<k 且 Ai<Aj<Ak 。现在 Chineselyl 正忙着准备会考呢,他想请你帮忙统计一下一个整数序列中“三元数对”的个数。

【输入格式】

* 第一行一个整数 n

* 接下来有 N 行,分别表示这个整数序列的每一项

【输出格式】

 * 输出这个整数序列中三元数对的个数

【样例输入】

512234

【样例输出】

7

【输入输出样例说明】

这7个三元数对分别是

1 2 31 2 41 2 31 2 41 3 42 3 42 3 4

【数据规模】

30%的数据中 n<=100

60%的数据中 n<=2000

100%的数据中 n<=30000 0<=Ai<=maxlongint

注:大规模数据随机生成。

这个题很像那个 COGS  859 数列 但是Ai的范围扩大了 我们只能按n来建树

维护编号是否存在 查询有多少比自己编号小的存在

要事先排序来保证数据的递增/递减性

#include
#include
#include
#include
using namespace std;const int lim=30011;int sumv[lim<<2];int m,n,a,b,c;struct self{int x,y;}s[lim];long long l[lim],r[lim],z;void pushup(int o){sumv[o]=sumv[o<<1]+sumv[o<<1|1];}int w;int querymin(int o,int l,int r){ if(r<=w)return sumv[o]; int m=(l+r)>>1; int ret=0; if(w>m)ret+=querymin(o<<1|1,m+1,r); ret+=querymin(o<<1,l,m); return ret;}int querymax(int o,int l,int r){ if(l>=w)return sumv[o]; int m=(l+r)>>1; int ret=0; if(w<=m)ret+=querymax(o<<1,l,m); ret+=querymax(o<<1|1,m+1,r); return ret;}void add(int o,int l,int r){ if(l==r) { sumv[o]++; return; } int m=(l+r)>>1; if(w<=m)add(o<<1,l,m); else add(o<<1|1,m+1,r); pushup(o);}int cmp(self a1,self a2){return a1.y
=1)l[b]=querymin(1,1,m);else l[b]=0; } a=b; for(b=1;b<=top;b++) { w=q[b]; add(1,1,m); } } memset(sumv,0,sizeof(sumv)); for(a=m;a>=1;) { top=0; for(b=a;s[b].y==s[a].y;b--) { top++; q[top]=s[b].x; w=s[b].x+1; if(w<=m)r[b]=querymax(1,1,m);else r[b]=0; z+=l[b]*r[b]; } a=b; for(b=1;b<=top;b++) { w=q[b]; add(1,1,m); } } cout<
<

转载地址:https://blog.csdn.net/li412302070/article/details/14000617 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:COGS 859 数列
下一篇:COGS 1266 借教室

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月03日 08时52分42秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

android测试页面,自动执行界面测试 | Android 开发者 | Android Developers 2019-04-21
android 图片点击变色,Android开发实现ListView点击item改变颜色功能示例 2019-04-21
android增删改查布局,Android之父_增删改查 2019-04-21
vowifi android开关,如何配置VoLTE, ViLTE and VoWifi(IMS config for VoLTE, ViLTE and VoWifi) 2019-04-21
电脑端的mafsvr服务关掉_网吧才是电脑优化的精髓!学会3招你也不用羡慕网吧的流畅了... 2019-04-21
html获取文件路径_HTML 文件路径 2019-04-21
mysql滴的一声就关了_关于mysql数据库在输入密码后,滴的一声直接退出界面的解决办法(详细办法)... 2019-04-21
mysql in 有序_mysql中的in排序 mysql按in中顺序来排序 2019-04-21
mysql 行转列 显示_mysql 行转列 (结果集以坐标显示) 2019-04-21
由于连接方在一段时间后没有正确答复或连接的主机_新风换气机使用效果不佳,为何?掌握正确使用方法就好了... 2019-04-21
mysql 查询姓王_MySQL查询语句练习题,测试足够用了 2019-04-21
mysql多实例脚本_mysql多实例脚本 2019-04-21
python如何生成excel文件夹_用python脚本通过excel生成文件夹树结构 2019-04-21
python获取post请求中的所有参数_Django从POST reques获取请求参数 2019-04-21
mysql加密复制_MySQL主从复制使用SSL加密 2019-04-21
python启动远端 exe_python打包exe开机自动启动的实例(windows) 2019-04-21
java当前路径_java获取当前路径的几种方法 2019-04-21
java web传递参数_Javaweb的八种传值方式 2019-04-21
java gui支持的包有哪两个_Java GUI 2019-04-21
java list详解_java集合List解析 2019-04-21