[关闭]
@zzzc18 2017-09-07T11:46:06.000000Z 字数 951 阅读 524

LA 4329

UVA UVALive


Problem Link

其实我们只要利用树状数组就可以知道:某一位置前比它小的数的个数,以及其后比它大的个数,怎么着乘一下就有答案了。

可是我写这个并不是说这个题怎么了,而是关于树状数组,一定要非常注意树状数组的长度究竟是多少,就像本题中,长度不是 而是 ,否则 WA×14 orz

Code:

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. typedef long long LL;
  6. const int MAXN = 100000+9;
  7. int a[MAXN];
  8. int n;
  9. int c[MAXN],d[MAXN];
  10. int tree[MAXN];
  11. int lowbit(int x){
  12. return x&-x;
  13. }
  14. void addnum(int pos,int v){
  15. int i;
  16. for(i=pos;i<=100000;i+=lowbit(i))
  17. tree[i]+=v;
  18. }
  19. int getsum(int pos){
  20. int i;
  21. int re=0;
  22. for(i=pos;i>=1;i-=lowbit(i))
  23. re+=tree[i];
  24. return re;
  25. }
  26. void solve1(){
  27. int i;
  28. for(i=1;i<=100000;i++)
  29. tree[i]=0;
  30. for(i=1;i<=n;i++){
  31. addnum(a[i],1);
  32. c[i]=getsum(a[i]-1);
  33. }
  34. for(i=1;i<=100000;i++)
  35. tree[i]=0;
  36. for(i=n;i>=1;i--){
  37. addnum(a[i],1);
  38. d[i]=getsum(a[i]-1);
  39. }
  40. }
  41. void solve2(){
  42. int i;
  43. LL ans=0;
  44. for(i=1;i<=n;i++){
  45. ans+=(LL)c[i]*(n-i-d[i]);
  46. ans+=(LL)(i-c[i]-1)*d[i];
  47. }
  48. printf("%lld\n",ans);
  49. }
  50. int main(){
  51. int kase;
  52. scanf("%d",&kase);
  53. while(kase--){
  54. scanf("%d",&n);
  55. int i;
  56. for(i=1;i<=n;i++)
  57. scanf("%d",&a[i]);
  58. solve1();
  59. solve2();
  60. }
  61. return 0;
  62. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注