AcWing-241. 楼兰图腾

2023 年 01 月 31 日

272 次浏览

787字数

![2265409832.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023/02/02/2265409832.png)

~~~cpp
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<fstream>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int n;
ll a[N], gr[N], sm[N];//gr比第i个数大的数，sm比第i个数小的数
ll tree[N];//树状数组

int lowbit(int x){
	return x & (-x);
}

void add(int x, int c){
	for(int i = x; i <= n; i += lowbit(i))
		tree[i] += c;
}

ll query(int x){
	ll res = 0;
	for(int i = x; i; i -= lowbit(i))
		res += tree[i];
	return res;
}

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= n; i++){
		int t = a[i];
		gr[i] = query(n) - query(t);//比当前数大的数的个数，相当于前缀和的(t, n]中数的个数
		sm[i] = query(t - 1);//相当于比[1, t - 1]的比当前数小的数
		add(t, 1);//把这个数放到树状数组
	}
	ll res1 = 0, res2 = 0;
	for(int i = 1; i <= n; i++){
		int t = a[i];
		res1 += gr[i] * (n - gr[i] - t);//v的个数就是左边比t大的数乘右边比t大的数的个数
					//因为比t大的数有n-t个，左边占了gr个，右边剩下n-t-gr[i]
		res2 += sm[i] * (t - 1 - sm[i]);
	}
	cout << res1 << " " << res2 << endl;
	return 0;
}
~~~

最后修改：2023 年 02 月 02 日