ac代码
代码语言：javascript复制#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define mp make_pair
#define pi acos(-1)
#define pii pair<int, int>
#define pll pair<long long , long long>
#define ll long long
#define ld long double
#define MEMS(x) memset(x, -1, sizeof(x))
#define MEM(x) memset(x, 0, sizeof(x))
const int inf = 0x3f3f3f3f;
const int maxn = 500001;
using namespace std;
int n;
struct Intg
{
int data;
int pos;
bool operator<(const Intg num) const
{
return data < num.data;
}
}a[maxn];
int p[maxn], d[maxn];
int lowbit(int x)
{
return x & (-x);
}
void update(int x)
{
while(x <= maxn)
{
d[x] ;
x = lowbit(x);
}
}
int getsum(int x)
{
int ans = 0;
while(x) //一定写成这种形式，否则写成for循环形式会导致超时
{
ans = d[x];
x -= lowbit(x);
}
return ans;
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
while(scanf("%d", &n) != EOF && n)
{
for(int i = 1; i <= n; i )
{
scanf("%d", &a[i].data);
a[i].pos = i;
}
sort(a 1, a n 1);
p[a[1].pos] = 1;
int idx = 1;
for(int i = 2; i <= n ; i )
{
if(a[i].data == a[i-1].data)
p[a[i].pos] = idx;
else
p[a[i].pos] = idx;
}
ll ans = 0;
memset(d, 0, sizeof(d));
for(int i = 1; i <= n; i )
{
update(p[i]);
ans = i - getsum(p[i]);
}
printf("%lldn", ans);
}
}
