fork download
  1. //#pragma comment(linker, "/STACK:16777216")
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <algorithm>
  6. #include <string>
  7. #include <cstring>
  8. #include <vector>
  9. #include <stack>
  10. #include <queue>
  11. #include <deque>
  12. #include <map>
  13. #include <set>
  14. #include <limits>
  15. #include <climits>
  16. #include <cmath>
  17. #include <functional>
  18. #include <ctime>
  19. #include <cstdlib>
  20. #include <fstream>
  21. #include <typeinfo>
  22. #include <cassert>
  23.  
  24. #define endl '\n'
  25. #define remainder safdskhaslfa
  26. #define pow aafkhffhlgsdas
  27. #define distance dagkjsdsdsara
  28. #define left askfjasieqwskajdaks
  29. #define right sakjjlkjlkjlashfjas
  30. #define y0 kshjlhlliahjajkdhkasfdg
  31. #define y1 kjlajhjaskhajkhjfkahgjahjkas
  32.  
  33. using namespace std;
  34.  
  35. const int SIZE = 1<<17;
  36.  
  37. int n,tests;
  38. int a[SIZE],x[SIZE];
  39. int best;
  40. long long inv_cnt,max_inv;
  41.  
  42. struct fenwick_tree {
  43. int a[SIZE];
  44. void Initialize() {
  45. memset(a,0,sizeof(a));
  46. }
  47. void Update(int pos, int val) {
  48. for(;pos<SIZE;pos+=pos&(-pos)) a[pos]+=val;
  49. }
  50. int Query(int pos) {
  51. int ans=0;
  52. for(;pos>=1;pos-=pos&(-pos)) ans+=a[pos];
  53. return ans;
  54. }
  55. }it;
  56.  
  57. int next(int p) {
  58. p++;
  59. if(p>n) p=1;
  60. return p;
  61. }
  62.  
  63. bool compare(int idx1, int idx2) {
  64. int cnt;
  65. for(cnt=1;cnt<=n;cnt++,idx1=next(idx1),idx2=next(idx2)) {
  66. if(a[idx1]<a[idx2]) return true;
  67. if(a[idx1]>a[idx2]) return false;
  68. }
  69. return false;
  70. }
  71.  
  72. int main() {
  73. ios_base::sync_with_stdio(false);
  74. cin.tie(NULL);
  75. //ifstream cin("test.txt");
  76. //freopen("test.txt","r",stdin);
  77. int i,left,right,middle;
  78.  
  79. cin>>tests;
  80. while(tests--) {
  81. cin>>n;
  82. for(i=1;i<=n;i++) cin>>a[i];
  83. for(i=1;i<=n;i++) x[i]=a[i];
  84. sort(x+1,x+1+n);
  85. for(i=1;i<=n;i++) {
  86. if(a[i]==x[1]) a[i]=1;
  87. else {
  88. left=1;
  89. right=n;
  90. while(right-left>1) {
  91. middle=(left+right)>>1;
  92. if(x[middle]<a[i]) left=middle;
  93. else right=middle;
  94. }
  95. a[i]=right;
  96. }
  97. }
  98. //for(i=1;i<=n;i++) assert(a[i]>=1 && a[i]<SIZE);
  99.  
  100. it.Initialize();
  101. inv_cnt=0;
  102. for(i=n;i>=1;i--) {
  103. inv_cnt+=it.Query(a[i]-1);
  104. it.Update(a[i],1);
  105. }
  106. max_inv=inv_cnt;
  107. best=0;
  108. for(i=1;i<n;i++) {
  109. inv_cnt-=it.Query(a[i]-1);
  110. inv_cnt+=it.Query(SIZE-1)-it.Query(a[i]);
  111. if(inv_cnt>max_inv) {
  112. max_inv=inv_cnt;
  113. best=i;
  114. }
  115. else if(inv_cnt==max_inv) {
  116. if(compare(i+1,best+1)) best=i;
  117. }
  118. }
  119. cout<<best<<' '<<max_inv<<endl;
  120. }
  121.  
  122. return 0;
  123. }
  124.  
Success #stdin #stdout 0s 4772KB
stdin
Standard input is empty
stdout
Standard output is empty