[玄关]树状数组 60pts WA 求调
查看原帖
[玄关]树状数组 60pts WA 求调
1327843
如履薄冰楼主2025/7/3 18:49
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5 * 1e5 + 10;
namespace rooney
{
	int lowbit(int x)
	{
		return x & -x;
	}
}
struct Node{
	int v, id;
	bool operator < (const Node &o) const
	{
		if (v != o.v)
		{
			return v < o.v;
		}
		else
		{
			return id < o.id;
		}
	}
}a[maxn];
int n, ans, rk[maxn], tree[maxn];
void update(int cur, int add)
{
	while (cur <= n)
	{
		tree[cur] += add;
		cur += rooney::lowbit(cur);
	}
}
int query(int cur)
{
	int ret = 0;
	while (cur > 0)
	{
		ret += tree[cur];
		cur -= rooney::lowbit(cur);
	}
	return ret;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++ i)
	{
		cin >> a[i].v;
		a[i].id = i;
	}
	sort (a + 1, a + 1 + n);
	for (int i = 1; i <= n; ++ i)
	{
		rk[a[i].id] = i;
	}
	for (int i = 1; i <= n; ++ i)
	{
	    update(rk[i], 1);
		cout << query(rk[i]- 1) << " ";
	}
	return 0;
}

2025/7/3 18:49
加载中...