题解：P1637 三元上升子序列
wjr_jok
·
·
题解
发现值域很小，所以考虑对它分块。
对于分块部分，$x,y,fk$ 三个数组分别记录每个块的左右端点以及每个数对应的块（注意这里的数指的是值域中的数值），$cc,tj$ 为值域标记数组，用于记录每个数值出现了多少次，每个块内的数值共出现了多少次。
对于 $q _ {i}$，通过遍历 $1$ $\sim$ $xl _ {i} - 1$ 的值域覆盖的块求得，$h _ {i}$ 就从 $xl _ {i} + 1$ $\sim$ $maxx$ 的值域覆盖的块求得。为了保证先后顺序，这里求取 $q$ 数组时正序遍历，求取 $h$ 数组时倒序遍历。
最后我们枚举每个数作为三元上升子序列的中间数，将答案累加，即为 $\begin{aligned} \sum _ {i = 1} ^ n q_{i} \times h_{i} \end{aligned}$。
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,l,r,cnt,ans,maxx;
int xl[30001],q[30001],h[30001],tj[320];
int x[320],y[320],cc[100001],fk[100001];
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>xl[i];
maxx=max(maxx,xl[i]);//求值域
}
for(int i=1;i<=(int)sqrt(maxx);i++){
cnt++;
x[cnt]=y[cnt-1]+1;
y[cnt]=x[cnt]+(int)sqrt(maxx)-1;
for(int j=x[cnt];j<=y[cnt];j++){
fk[j]=cnt;
}
}
if(y[cnt]<maxx){
cnt++;
x[cnt]=y[cnt-1]+1;
y[cnt]=maxx;
for(int i=x[cnt];i<=y[cnt];i++){
fk[i]=cnt;
}
}
for(int i=1;i<=n;i++){
l=1,r=xl[i]-1;//1~xl[i-1]的值域
for(int j=l;j<=min(y[fk[l]],r);j++){
q[i]+=cc[j];
}
if(fk[l]!=fk[r]&&fk[r]){
for(int j=x[fk[r]];j<=r;j++){
q[i]+=cc[j];
}
}
for(int j=fk[l]+1;j<fk[r]&&fk[r];j++){
q[i]+=tj[j];
}
cc[xl[i]]++;
tj[fk[xl[i]]]++;//录入当前值
}
for(int i=1;i<=maxx;i++){
cc[i]=tj[fk[i]]=0;
}//清空
for(int i=n;i>=1;i--){//注意为倒序
l=xl[i]+1,r=maxx;//xl[i]+1~maxx的值域
for(int j=l;j<=min(y[fk[l]],r);j++){
h[i]+=cc[j];
}
if(fk[l]!=fk[r]&&fk[l]){
for(int j=x[fk[r]];j<=r;j++){
h[i]+=cc[j];
}
}
for(int j=fk[l]+1;j<fk[r]&&fk[l];j++){
h[i]+=tj[j];
}
cc[xl[i]]++;
tj[fk[xl[i]]]++;//录入当前值
}
for(int i=1;i<=n;i++){
ans+=q[i]*h[i];//求和
}
cout<<ans;
return 0;
}
```