企业官网建设流程全解析

南京高端定制网站建设,贵阳网站定制电话,怎么推广app,万网域名注册接口P1637 三元上升子序列 时间限制: 1.00s 内存限制: 128.00MB 复制 Markdown 中文 退出 IDE 模式 题目描述 Erwin 最近对一种叫 thair 的东西巨感兴趣。。。 在含有 n 个整数的序列 a1​,a2​,…,an​ 中#xff0c;三个数被称作thair当且仅当 ijk 且 ai​aj…P1637 三元上升子序列时间限制: 1.00s 内存限制: 128.00MB复制 Markdown中文退出 IDE 模式题目描述Erwin 最近对一种叫thair的东西巨感兴趣。。。在含有 n 个整数的序列 a1​,a2​,…,an​ 中三个数被称作thair当且仅当 ijk 且 ai​aj​ak​。求一个序列中thair的个数。输入格式开始一行一个正整数 n,以后一行 n 个整数 a1​,a2​,…,an​。输出格式一行一个整数表示thair的个数。输入输出样例输入 #1复制运行4 2 1 3 4输出 #1复制运行2输入 #2复制运行5 1 2 2 3 4输出 #2复制运行7说明/提示样例2 解释7 个thair分别是1 2 31 2 41 2 31 2 41 3 42 3 42 3 4数据规模与约定对于 30% 的数据 保证 n≤100对于 60% 的数据 保证 n≤2000对于 100% 的数据 保证 1≤n≤3×1041≤ai​≤105。数字范围大于数组范围 防止浪费空间可以开离散化我们可以用一个桶 然后每次在对应位置上加1 那么当添加了i-1个数字的时候 比第i个数字小的数字就是桶i前面的所有桶的数字之和 这个过程正反均来一遍就可以得到一个数字前面有多少比他小以及后面有多少比他大 最后的答案乘起来即可离散化后 num[i]就表示 第i个数字的大小 由于离散化 和桶排序 也代表了桶的序号统计num[i]的情况的时候 就需要算出1~num[i]-1的所有桶的数字和 就是有多少个数字小于他大于同理#include bits/stdc.h using namespace std; #define int long long const int N3e45; int n,low[N],up[N],cnt,num[N]; pairint ,inta[N]; struct SegmentTree{ int l,r,sum; #define l(x) tree[x].l #define r(x) tree[x].r #define sum(x) tree[x].sum }tree[N2]; void pushup(int p){ sum(p)sum(p1)sum(p1|1); } void build(int p,int l,int r){ l(p)l,r(p)r; if(lr){sum(p)0;return;} int mid(lr)1; build(p1,l,mid); build(p1|1,mid1,r); pushup(p); } void update(int p,int pos){ if(l(p)r(p)l(p)pos){ sum(p); return; } int mid (l(p)r(p))1; if(posmid)update(p1,pos); else update(p1|1,pos); pushup(p); } int query(int p,int l,int r){ if(ll(p)rr(p)) return sum(p); int mid (l(p)r(p))1; int val0; if(lmid)valquery(p1,l,r); if(rmid)valquery(p1|1,l,r); return val; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinn; for(int i1;in;i)cina[i].first,a[i].secondi; sort(a1,a1n); for(int i1;in;i){ if(a[i].firsta[i-1].first)cnt; num[a[i].second]cnt; } build(1,1,cnt); for(int i1;in;i){ if(num[i]1)low[i]query(1,1,num[i]-1); else low[i]0; update(1,num[i]); } build(1,1,cnt); for(int in;i1;i--){ if(num[i]cnt)up[i]query(1,num[i]1,cnt); else up[i]0; update(1,num[i]); } int ans0; for(int i1;in;i){ anslow[i]*up[i]; } coutans\n; return 0; }