社区讨论

树状数组过不去了,可是为什么嘞?

P1908逆序对参与者 12已保存回复 24

讨论操作

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

当前回复
24 条
当前快照
1 份
快照标识符
@mi7coj0e
此快照首次捕获于
2025/11/20 19:30
4 个月前
此快照最后确认于
2025/11/20 22:36
4 个月前
查看原帖
**所有大佬都说数据加强,树状数组过不去了,但本蒟想不通为何,求救大佬,望大佬赏赐Hack数据```cpp #include #include #include using namespace std; struct yan { int data; int num; } a[500001]; int n; int tree[500001]; int lowbit(int x) { return x&(-x); } bool cmp(const yan &x,const yan &y) { return x.data<y.data; } int main() { scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%d",&a[i].data); a[i].num=i; } sort(a+1,a+n+1,cmp); int ans=0; for(int i=1; i<=n; i++) { int o=a[i].num; while(o<=n) { tree[o]++; o+=lowbit(o); } o=a[i].num; int u=0; while(o) { u+=tree[o]; o-=lowbit(o); } ans+=i-u; } printf("%d",ans); return 0; }

回复

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

正在加载回复...