POJ 2299
上課講了下數據結構，因為暫時沒找到分塊的板子題，所以做一下這道題加深一下對樹狀數組的理解。
題意就是求逆序對，從逆序對的定義就可以看出，方法有兩種：歸并 or 樹狀數組。
感覺樹狀數組更高級一點，寫起來也比較容易（其實是不會歸并）
在這里由于a[i]太大（0~999999999），因此離散化一下，也就是開個結構體排序后看一下它在第幾個。
一個數產生的逆序對數就是它前面的比它大的個數。
因此對于x，先查詢sum(x+1,n)的值，再add(x)即可。
CODE
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL N=;
struct data
{
LL x,num;
}a[N];
LL p[N],c[N],i,n,ans;
inline void read(LL &x)
{
x=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
inline void write(LL x)
{
if (x/) write(x/);
putchar(x%+'');
}
inline LL comp(data a,data b)
{
return a.x<b.x;
}
inline LL lowbit(LL x)
{
return x&(-x);
}
inline LL get(LL x)
{
LL res=;
while (x)
{
res+=c[x];
x-=lowbit(x);
}
return res;
}
inline void add(LL x)
{
while (x<=n)
{
c[x]+=;
x+=lowbit(x);
}
}
int main()
{
for (;;)
{
memset(c,,sizeof(c));
read(n); ans=;
if (!n) break;
for (i=;i<=n;++i)
read(a[i].x),a[i].num=i;
sort(a+,a+n+,comp);
for (i=;i<=n;++i)
p[a[i].num]=i;
for (i=;i<=n;++i)
ans+=get(n)-get(p[i]),add(p[i]);
write(ans); putchar('\n');
}
return ;
}
總結
- 上一篇： CCF 送货 + 欧拉路模板
- 下一篇： DataGridView的Validat