P1637 三元上升子序列[线段树维护 + 离散化]
P1637 三元上升子序列
时间限制: 1.00s 内存限制: 128.00MB
复制 Markdown
中文
退出 IDE 模式
题目描述
Erwin 最近对一种叫thair的东西巨感兴趣。。。
在含有 n 个整数的序列 a1,a2,…,an 中，三个数被称作thair当且仅当 i<j<k 且 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 3
- 1 2 4
- 1 2 3
- 1 2 4
- 1 3 4
- 2 3 4
- 2 3 4
数据规模与约定
- 对于 30% 的数据 保证 n≤100；
- 对于 60% 的数据 保证 n≤2000；
- 对于 100% 的数据 保证 1≤n≤3×104，1≤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 N=3e4+5; int n,low[N],up[N],cnt,num[N]; pair<int ,int>a[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[N<<2]; void pushup(int p){ sum(p)=sum(p<<1)+sum(p<<1|1); } void build(int p,int l,int r){ l(p)=l,r(p)=r; if(l==r){sum(p)=0;return;} int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,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(pos<=mid)update(p<<1,pos); else update(p<<1|1,pos); pushup(p); } int query(int p,int l,int r){ if(l<=l(p)&&r>=r(p)) return sum(p); int mid =(l(p)+r(p))>>1; int val=0; if(l<=mid)val+=query(p<<1,l,r); if(r>mid)val+=query(p<<1|1,l,r); return val; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++)cin>>a[i].first,a[i].second=i; sort(a+1,a+1+n); for(int i=1;i<=n;i++){ if(a[i].first>a[i-1].first)cnt++; num[a[i].second]=cnt; } build(1,1,cnt); for(int i=1;i<=n;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 i=n;i>=1;i--){ if(num[i]<cnt)up[i]=query(1,num[i]+1,cnt); else up[i]=0; update(1,num[i]); } int ans=0; for(int i=1;i<=n;i++){ ans+=low[i]*up[i]; } cout<<ans<<'\n'; return 0; }