luogu P1637 三元上升子序列

我们可以枚举中间数，然后一分为二计算前面比本元素小的*后面比本元素大的，累加起来就是答案。

首先需要离散化，预处理两个数组l[i],r[i]表示左边比i小和左边比i大的。

开个权值树状数组，l[i]很好计算 ，r[i]需要变化一下，倒序计算r[i],那么当前计算出的sum表示的i+1_{n中小于等于a[i]的，用n-i减去sum就是i+1}n大于a[i]的数量

代码

#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
using namespace std;
typedef long long lxl;
template<typename T>
inline T  max(T &a, T &b) {
	return a > b ? a : b;
}
template<typename T>
inline T  min(T &a, T &b) {
	return a < b ? a : b;
}

inline char gt() {
	static char buf[1 << 21], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void  read(T &x) {
	register char ch = gt();
	x = 0;
	int w(0);
	while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
	while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
	w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x) {
	if(x < 0) x = -x, putchar('-');
	char ch[20];
	int num(0);
	while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
	while(num) putchar(ch[num--]);
	putchar('
');
}
int n;
const int N=3e5+79;
struct BIT{
	int c[N];
	inline int lowbit(int x){
		return x&(-x);
	}
	inline void add(int x,int val){
		for(;x<=n;x+=lowbit(x))
		 c[x]+=val;
	}
	inline lxl ask(int x){
		lxl ans(0);
		for(;x;x-=lowbit(x))
		 ans+=c[x];
		 return ans;
	}
}B,BB;


lxl a[N], k[N];
int l[N],r[N];//左边小于，右边大于 
vector<lxl>b;

inline int getid(int x){
	return lower_bound(b.begin(),b.end(),x)-b.begin()+1;
}

int main() {
	read(n);
	rep(i, 1, n) {
		read(a[i]);
		b.push_back(a[i]);
	}
	sort(b.begin(), b.end());
	b.erase(unique(b.begin(), b.end()), b.end());
	rep(i, 1, n) {
		k[i] = getid(a[i]);
	}
	
	rep(i,1,n){
		l[i]=B.ask(k[i]-1);
		B.add(k[i],1);
	}//查询前面的比 
	
	drp(i,n,1){
		r[i]=n-i-BB.ask(k[i]);
		BB.add(k[i],1);
	}//后i~n中小于k[i] 
	
	lxl ans(0);
	rep(i,2,n-1 )
	 ans=ans+l[i]*r[i];
	out(ans);
	return 0;
}