241. 楼兰图腾

题目链接：https://www.acwing.com/problem/content/description/243/

思路

遍历1-n，每次往树状数组的arr[i]位置插入1，表示arr[i]出现过一次。每当遍历到i时，就能通过树状数组查询小于arr[i]的元素个数，和大于arr[i]的元素个数。
和权值线段树一样的操作。

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
int arr[maxn];
int Lmax[maxn],Rmax[maxn],Lmin[maxn],Rmin[maxn];
int tr[maxn];

int lowbit(int x){
    return x&-x;
}
void add(int idx,int v){
    for(int i = idx;i<=N;i += lowbit(i)) tr[i] += v;
}
int query(int r){
    int sum = 0;
    for(int i = r;i>=1;i -= lowbit(i)) sum += tr[i];
    return sum;
}
int main(){
    ios;
    cin>>N;
    for(int i = 1;i<=N;i++) cin>>arr[i];
    for(int i = 1;i<=N;i++){
        Lmin[i] = query(arr[i]-1);
        Lmax[i] = query(N) - query(arr[i]);
        add(arr[i],1);
    }
    memset(tr,0,sizeof tr);
    for(int i = N;i>=1;i--){
        Rmin[i] = query(arr[i]-1);
        Rmax[i] = query(N) - query(arr[i]);
        add(arr[i],1);
    }
    ll res1 = 0,res2 = 0;
    for(int i = 1;i<=N;i++){
        res1 += (ll)Lmax[i] * Rmax[i];
        res2 += (ll)Lmin[i] * Rmin[i];
    }
    cout<<res1<<" "<<res2<<endl;
    return 0;
}