codeforces 1269E K Integers (二分+树状数组)

链接：https://codeforces.com/contest/1269/problem/E

题意：给一个序列P1,P2,P3,P4....Pi，每次可以交换两个相邻的元素，执行最小次数的交换移动，使得最后存在一个子段1,2，…，k，这是题目所定义的f(k)，题目要求求出所有的f(n)，并依次输出。

思路：首先考虑逆序对问题，比如3 2 1 4这个序列，要使其变为1 2 3 4，最小的移动次数是这个序列中逆序对之和，2+1 = 3，逆序对是（3，2）（3，1）（2，1），但是在比如序列3 5 2 1 6 7 4 8 9，求f(4)怎么做？首先是不是把1 2 3 4这个序列聚成在一起，相连在一起，再去计算逆序对个数，两个过程所花费相加就是答案。那么这个题目就分为两个过程，1.聚合n个数字在一起。2.求逆序对的个数，两者花费相加就行。第1个过程如果使得聚合步数最少呢？其实就是求出聚合后的最中间的位置，其他所有的数字向这个位置靠近所花费的移动次数是最少的，这个过程可以用二分做。第2个过程可以用树状数组，也可以用线段树做。输入的时候记录每个数字的位置，建两个树状数组，一个树状数组维护数字出现的次数，用来求逆序对个数，另一个树状数组维护各个数字在原序列的位置。

AC代码：

 #include<iostream>

 #include<string>

 #include<vector>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long ll;

 ll mod = 1e9+;

 const int maxn = 2e5+;

 ll t[maxn],cnt[maxn];

 ll pos[maxn];

 int n;

 inline int lowbit(ll x){

     return x&(-x);

     ///算出x二进制的从右往左出现第一个1以及这个1之后的那些0组成数的二进制对应的十进制的数

 }

 void add(ll *b , int x, int k) {//单点修改

   while (x <= n) {  //不能越界

     b[x] = b[x] + k;

     x = x + lowbit(x);

   }

 }

 ll getsum(ll *b,int x) {  // a[1]……a[x]的和

   ll ans = ;

   while (x > ) {

     ans = ans + b[x];

     x = x - lowbit(x);

   }

   return ans;

 }

 int main(){

     ios::sync_with_stdio(false);

     cin.tie();

     cin>>n;

     for(int i = ;i<=n;i++){

         int t;

         cin>>t;

         pos[t] = i;

     }

     ll inv = ;

     for(int i = ;i<=n;i++){

         inv += (i--getsum(t,pos[i]));

         add(t,pos[i],);

         add(cnt,pos[i],pos[i]);

         if(i==){

             cout<<<<" ";

             continue;

         }

         int mid,l = ,r = n;

         while(l<=r){

             mid = (l+r)>>;

             if(getsum(t,mid)*<=i){

                 l = mid+;

             }

             else{

                 r = mid-;

             }

         }

         ll ans = ;

         ll cntL = getsum(t,mid);

         ll cntR = i - cntL;

         ll indexL = getsum(cnt,mid);

         ll indexR = getsum(cnt,n)-indexL;

         ans+=((mid+mid-cntL+)*cntL)/-indexL;

         ans+=(indexR-((mid++(mid+cntR))*cntR)/);

         cout<<ans+inv<<" ";

     }

     return ;

 }

巴特西

codeforces 1269E K Integers (二分+树状数组)

最新文章

热门文章