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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年03月03日 08时52分42秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
android增删改查布局,Android之父_增删改查
2019-04-21
html获取文件路径_HTML 文件路径
2019-04-21
mysql in 有序_mysql中的in排序 mysql按in中顺序来排序
2019-04-21
mysql 行转列 显示_mysql 行转列 (结果集以坐标显示)
2019-04-21
mysql 查询姓王_MySQL查询语句练习题,测试足够用了
2019-04-21
mysql多实例脚本_mysql多实例脚本
2019-04-21
python如何生成excel文件夹_用python脚本通过excel生成文件夹树结构
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