#include<bits/stdc++.h>
#define N 200010
#define ll long long // 开long long
using namespace std;
ll n,m,a[N],c[N],f[2][N*4],ans1=0,ans2=0,x,y;
void init(ll x,ll l,ll r,ll rt){ // 初始化f[1]
if(l==r){
f[x][rt] = c[l];
return ;
}
ll mid = (l+r)>>1;
init(x,l,mid,rt<<1);
init(x,mid+1,r,(rt<<1)+1);
f[x][rt] = f[x][rt<<1]+f[x][(rt<<1)+1];
}
void add(ll y,ll x,ll l,ll r,ll rt){ // 单点修改,x为f[x],y是修改的位置
if(l==r){
if(x)f[x][rt]-=1; // 判断是加法还是减法
else f[x][rt]+=1;
return ;
}
ll mid = (l+r)>>1;
if(y<=mid)add(y,x,l,mid,rt<<1);
else add(y,x,mid+1,r,(rt<<1)+1);
f[x][rt] = f[x][rt<<1]+f[x][(rt<<1)+1];
return ;
}
ll get(ll x,ll y,ll z,ll l,ll r,ll rt){ // 区间查询
if(x > y) return 0;
if(x<=l and r<=y){
return f[z][rt];
}
ll mid = (l+r)>>1,ans=0;
if(x<=mid) ans+=get(x,y,z,l,mid,rt<<1);
if(y>mid) ans+=get(x,y,z,mid+1,r,(rt<<1)+1);
return ans;
}
signed main(){
cin >> n;
for(ll i=1;i<=n;i++){
cin >> a[i];
m = max(m,a[i]+1); // 获得最大值（它貌似没有给a[i]大小）
c[a[i]]++;
}
init(1,1,m,1);
add(a[1],1,1,m,1); // 提前在f[0]放一个
add(a[1],0,1,m,1);
for(ll i=2;i<n;i++){ // 遍历中间的点既可
ans1 += get(a[i]+1,m,0,1,m,1)*get(a[i]+1,m,1,1,m,1);
ans2 += get(1,a[i]-1,0,1,m,1)*get(1,a[i]-1,1,1,m,1);
add(a[i],1,1,m,1);
add(a[i],0,1,m,1);
}
cout << ans1 << " " << ans2<<endl;
return 0;
}
P10589 楼兰图腾
题目简述
对于一个数组$A_1,A_2,\dots,A_n$，找出$1\le i\le j\le k\le n$，求$A_j>A_i$且$A_j>A_k$的个数（∧），
与$A_j<A_i$且$A_j<A_k$的个数（ V）。
提示1
首先思考暴力做法：对于任意$i (1<i<n)$，找出小于$A_i$在i之前与i之后的个数，将两个数乘起来并加上所有i的情况即为∧的答案。另一种只需要把小于换成大于即可。
题解
使用树状数组或线段树维护两个可以单点修改区间查询的数据结构，记录i前与i后的两个相当于桶的东西，速度$O(n)$，总时间复杂度$O(n\log_2n)$，满足题意。
下面的代码我使用线段树实现，(f[0]与f[1]两棵线段树，f[0]代表i之前所有数的记录，f[1]代表i之后所有数的记录)。提前先将所有数据存储在f[i]中，每次遍历将f[1][a[i]]--，并f[0][a[i]]++（这里使用简写，其实是线段树的单点修改实现）
记得开long long