POJ 2299 POJ 2352

POJ 2299 POJ 2352"/>

POJ 2299 POJ 2352

2299 ：

求逆序数对的模板题，一个序列的逆序对数等于把它冒泡排序所需要的交换的次数。

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const ll maxn = 5e5 + 5;
ll n,m,temp,num[maxn],num2[maxn];
ll Tree[maxn];
ll lowbit(ll x)
{return x & (-x);
}
ll query(ll x)
{ll res  = 0;while(x){res += Tree[x];x -= lowbit(x);}return res;
}
void add(ll x,ll y)
{while(x <= n){Tree[x] += y;x += lowbit(x);}
}
void lsh()//离散化
{sort(num + 1,num + n + 1);ll h = unique(num + 1,num + 1 + n) - (num + 1);for(int i = 1; i <= n; i++)num2[i] = lower_bound(num + 1,num + h + 1,num2[i]) - num;
}
int main()
{while(cin >> n && n){ll res  = 0;for(int i = 1; i <= n; i++)cin >> num[i],num2[i] = num[i];lsh();for(int i = 1; i <= n; i++)Tree[i] = 0;for(int i = n; i >= 1; i--)//倒着开始放以便统计逆序对{add(num2[i],1);res += query(num2[i] - 1);}cout << res << endl;}return 0;
}

2352：

这道题可以对x进行排序维护y或者对y进行排序维护x，需要注意的是树状数组不会维护0这个点，所以要把所有维护的点加一，还有要注意，数组的大小应该是星星的坐标的大小

#include<algorithm>
#include<iostream>
#include<cstdio>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const ll maxn = 5e5 + 5;
ll Tree[maxn],ans[maxn];
ll n;
struct node
{ll x,y;bool operator <(const node & m) const{if(x != m.x)return x < m.x;elsereturn y < m.y;}
} num[maxn];
ll lowbit(ll x)
{return x & (-x);
}
ll query(ll x)
{ll res  = 0;while(x){res += Tree[x];x -= lowbit(x);}return res;
}
void add(ll x,ll y)
{while(x <= 32005){Tree[x] += y;x += lowbit(x);}
}
int main()
{scanf("%lld",&n);for(int i = 1; i <= n; i++){scanf("%lld %lld",&num[i].x, &num[i].y);num[i].y++;}sort(num + 1, num + n + 1);for(int i = 1; i <= n; i++){ans[query(num[i].y)]++;add(num[i].y,1);}for(int i = 0; i <= n - 1; i++)printf("%lld\n",ans[i]);return 0;
}