三元子上升序列

大家好，我是讯享网，很高兴认识大家。

展开

题目描述

Erwin 最近对一种叫 thair 的东西巨感兴趣。。。

在含有 nn 个整数的序列 a1,a2,....an 中，三个数被称作thair当且仅当 i<j<k且 ai<aj<ak

求一个序列中 thair 的个数。

输入格式

开始一行一个正整数 nn,

以后一行 nn 个整数 a1,a2,...,an

讯享网

输出格式

一行一个整数表示 thair 的个数。

数据规模与约定

对于 30\%30% 的数据保证 n\le100n≤100；
对于 60\%60% 的数据保证 n\le2000n≤2000；
对于 100\%100% 的数据保证 1 \leq n\le3\times10^41≤n≤3×104，0\le a_i\lt 10^50≤ai<105。

做法

这里采用的做法 O(nlog(n)) ，首先我们先对题目分析统计三元上升组的个数，得到对于一个数

记录左边比他小的数的个数，右边比它大的数的个数。乘法原理，我们用两个树状数组来维护左边比他小的，和右边比它大的。

对于左边比他小的，只需要统计（val -1）的树状数组的前缀和，对于右边比它大的，只需要统计 n-i-(v-1)//除掉本身外比v大的数的个数，最后再扫描一遍乘法原理计数

#pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3,"Ofast","inline") #include<bits/stdc++.h> #define re register #define fi first #define se second #define endl '\n' #define int long long #define wrn puts("NO") #define wry puts("YES") #define bug(x) cout<<#x<<"=="<<x<<endl #define fast_oi ios::sync_with_stdio(false);cin.tie(0) using namespace std; typedef pair<int,int>PII; typedef long long ll; typedef unsigned long long ull; const int N=3e4+5;//注意数组大小 const int INF=0x3f3f3f3f; const int mod=; ll qpow(ll a, ll b) {ll res = 1;while(b) {if(b & 1) res = (res * a) % mod;a = (a * a) % mod;b >>= 1;}return res%mod;} inline ll read() { ll x=0,w=1; char c=getchar(); while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();} while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar(); return w==1?x:-x; } inline void write(ll x) { if(x>=10) write(x/10); putchar(x%10+'0'); } inline ll lowbit(ll x) { return x&(-x); } template<class T> struct BT{//Fenwick tree T *a;int size; BT(int n){ size=n; a=new int[n+3]; memset(a,0,sizeof(int)*(n+2)); } ~BT(){delete []a;} void add(int i,T v){ while (i<=size) a[i]+=v,i+=lowbit(i); } T sum(int i){ T ans=0; while (i) ans+=a[i],i-=lowbit(i); return ans; } }; int n,a[N],b[N],m; int pos[N],dp[N]; int l[N],r[N]; void solverun() { n = read(); for (int i = 1; i <= n; i++) { a[i] = read(); b[i] = a[i]; } sort(b + 1 , b + 1 + n); m = unique(b + 1, b + 1 + n) - b - 1; BT<int>c(m); BT<int>d(m); //枚举中间结点 找出左边结点个数 右边结点个数 再用乘法原理 for (int i = 1; i <= n; ++i) { int p = lower_bound(b + 1, b + 1 + m , a[i]) - b; c.add(p,1); l[i]=c.sum(p - 1); } for (int i = n; i >= 1; i--) { int p = lower_bound(b + 1, b + 1 + m, a[i]) - b; d.add(p,1); r[i] = n - i - (d.sum(p) - 1); // sum - 1 是小于等于b[i](除掉本身的个数) } //乘法原理 ll res = 0; for (int i = 2; i < n; i++) { res += 1ll * l[i] * r[i]; } cout << res << endl; } signed main() { #ifdef ONLINE_JUDGE #else freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif fast_oi; int cas = 1; // cin >> cas; while (cas--) { solverun(); } return 0; }

讯享网

题目描述

输入格式

输出格式

数据规模与约定

做法

相关推荐