codeforeces 540E(树状数组-白红宇

codeforeces 540E(树状数组

阅读量：4994 次

发布时间：2019-06-12

本文共 869 字，大约阅读时间需要 2 分钟。

题意：交换自然数中的若干对数，求交换后总共有多少逆序数对。

思路：因为题目数字范围比较大，不能直接用树状数组算，首先要离散化。然后一种算法是官方题解中根据逆序对数是否属于交换过的数分类讨论统计。我的算法是把没有交换的连续的数看成一个数，使用树状数组统计的时候直接加上这个区间的数字个数，这样就不需要比较易错的讨论了。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define pb push_back#define fs first#define se secondusing namespace std;typedef long long ll;typedef pair
                 
                   P;const int maxv=1e5*4;struct BIT{ ll a[maxv]; void add(int p,int x){ while(p
                  
                   0){ ans+=a[p]; p-=p&-p; } return ans; } ll after(int a){ return sum(maxv-1)-sum(a); }}B;int a[maxv];int b[maxv];int c[maxv];int mid[maxv];int sq[maxv];int n;map
                   
                     mii;int main(){ freopen("/home/files/CppFiles/in","r",stdin); cin>>n; for(int i=0;i

View Code

转载于:https://www.cnblogs.com/Cw-trip/p/4675146.html

你可能感兴趣的文章

【问题解决方案】之 Word 公式编辑器使用小tips