「CH 4201」楼兰图腾 (树状数组)

CH 4201
题意：给出$n$点个点$(i,y_i)$，
若存在三点$(x_1,y_1), (x_2,y_2),(x_3,y_3)$，满足$x_1 > x_2 > x_3, y_1 > y_2, y_3 > y_2$则这三点称为v
若存在三点$(x_1,y_1), (x_2,y_2),(x_3,y_3)$，满足$x_1 > x_2 > x_3, y_1 < y_2, y_3 < y_2$则这三点称为^

请计算v, ^的个数

方法1：
根据$y$排序，对于^，每次加入一个点前询问比这个点$y$值小的$[1,x)$和$(x, INF)$的点的个数，答案加上他们的乘积，对于v同理

方法2：
根据$x$排序，对于v，对于每个数算出左右比$y$他大的点的个数，答案加上他们的乘积，对于^同理

知识点：

// 根据 y 排序
#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 200000 + 5;

    struct data {
        LL x, y;
        bool operator < (const data &rhs) const {return y < rhs.y;}
    } pos[MAXN];

    LL n, a[MAXN], ans1, ans2;

    LL lowbit(LL x) {return x & (-x);}
    void add(LL p) {
        for (LL i = p; i <= 200000ll; i += lowbit(i)) ++a[i]; 
    }
    LL query(LL p) {
        LL ret = 0ll;
        for (LL i = p; i; i -= lowbit(i)) ret += a[i];
        return ret;
    }

    void clean() {
    }
    int solve() {
        clean();
        scanf("%lld", &n);
        for (LL i = 1; i <= n; ++i) scanf("%lld", &pos[i].y), pos[i].x = i;
        sort(pos + 1, pos + 1 + n);
        ans1 = 0ll;
        ms(a, 0ll);
        for (LL i = 1; i <= n; ++i) {
            ans1 += query(pos[i].x - 1ll) * (query(200000ll) - query(pos[i].x));
            add(pos[i].x);
        }
        ans2 = 0ll;
        ms(a, 0ll);
        for (LL i = n; i; --i) {
            ans2 += query(pos[i].x - 1ll) * (query(200000ll) - query(pos[i].x));
            add(pos[i].x);
        }
        printf("%lld %lld\n", ans2, ans1);
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}