猿生体节

有彩蛋

oi , 50 分的人看过来

题意

逆序对个数

在学排序的时候学了

但是现在要用树状数组

思路

待写...

代码

不开 long long 见祖宗(50分)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,l,sum=0;
int a[500005];
int b[500005];
void add(int x,int k)
{
	for(;x<=l;x+=x&-x)
		b[x]+=k;
}
int ask(int x)
{
	int ans=0;
	for(;x;x-=x&-x)
		ans+=b[x];
	return ans;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		b[i]=a[i];
	sort(b+1,b+1+n);
	l=unique(b+1,b+1+n)-(b+1);
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+1+l,a[i])-b;
	memset(b,0,sizeof b);
	for(int i=n;i>=1;i--)
	{
		sum+=ask(a[i]-1);
		add(a[i],1);
	}
	cout<<sum;
	return 0;
}

彩蛋

吕泽楷传奇输入m

题意

输出对于 $1\le i<j\le n$，满足 $a_i<a_j$ 的个数。

思路

其实找逆序对相当于把数组反过来然后找正序对。

然后我们每遇到一个数，先将总个数加上比 $a_i$ 小的数的个数之和（sum += c.query(a[i] - 1)，$c$ 是树状数组），再将桶数组 $t_{a_i}++$。

但是我们发现输入的数的范围高达 $10^9$，所以我们要离散化一下。这里离散化后用不到原数组了，所以可以覆盖原数组

代码

#include <bits/stdc++.h>
using namespace std;
template<typename tp>
class BIT{
	private:
		size_t n;
		vector<tp> c;
		size_t lowbit(size_t x){
			return x & -x;
		}
	public:
		BIT(size_t n){
			this->n = n;
			c = vector<tp>(n);
		}
		BIT(vector<tp> a){
			n = a.size();
			for (size_t i = 1;i <= n;i++){
				add(i,a[i]);
			}
		}
		BIT(tp *a,size_t n){
			this->n = n; 
			for (size_t i = 1;i <= n;i++){
				add(i,a[i]);
			}
		}
		BIT(BIT<tp> &a){
			n = a.size();
			c = a;
		}
		size_t size(){
			return n;
		}
		void add(size_t i,tp val){
			for (;i <= n;i += lowbit(i))
				c[i] += val;
		}
		tp query(size_t r){
			tp res = 0;
			for (;r;r -= lowbit(r))
				res += c[r];
			return res;
		}
		tp query(size_t l,size_t r){
			return query(r) - query(l - 1);
		}
};

typedef long long ll;
const int N = 5e5 + 5;
int a[N],b[N];
ll sum;
BIT<ll> c(N);
int main(int argc, char **argv){
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b + 1,b + n + 1);
	int m = unique(b + 1,b + n + 1) - b;
	for (int i = 1;i <= n;i++){
		a[i] = lower_bound(b + 1,b + m,a[i]) - b;
	}
	
	for (int i = n;i > 0;i--){
		sum += c.query(a[i] - 1);	// 减 1 是因为不把 a[i] 包括进去（a[i] > a[j]） 
		c.add(a[i],1);
	}
	cout << sum;
	return 0;
}