社区讨论

求助玄关树状数组(全RE)

P1908逆序对参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@m2equh71
此快照首次捕获于
2024/10/18 21:06
去年
此快照最后确认于
2025/11/04 16:54
4 个月前
查看原帖
离散化+树状数组 代码:
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,s,ans,a[1000010],b[1000010],c[1000010],ord[1000010];
ll lbt(ll x){ return x&-x; }
void upd(ll pos,ll x)
{
	for(;pos<s;pos+=lbt(pos))c[pos]+=x;
	return;
}
ll query(ll l,ll r)
{
	ll tmp1=0,tmp2=0;
	for(l-=1;l>0;l-=lbt(l))tmp1+=c[l];
	for(;r>0;r-=lbt(r))tmp2+=c[r];
	return tmp2-tmp1;
}
int main()
{
	//freopen("P1908_1.in","r",stdin);
	//freopen("P1908_1.ans","w",stdout);
	//cout<<"wda";
	//read(n);
	cin>>n;
	//cout<<"WDA";
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	//cout<<"daww";
	sort(a+1,a+n+1);
	s=unique(a+1,a+n+1)-a;
	//cout<<s<<" ";
	for(int i=1;i<s;i++)
		ord[a[i]]=i;
	for(int i=1;i<=n;i++)
	{
		upd(ord[b[i]],1);
		ans+=query(ord[b[i]]+1,s-1);
		//cout<<ans<<" ";
	}
	cout<<ans;
	return 0;
}
```
请大佬劳神读一读我这没注释的丑陋程序TAT

回复

6 条回复,欢迎继续交流。

正在加载回复...