社区讨论
求助玄关树状数组(全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 条回复,欢迎继续交流。
正在加载回复...