codeforces 540E"Infinite Inversions"-白红宇

codeforces 540E"Infinite Inversions"

阅读量：5050 次

发布时间：2019-06-12

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

题意：

　　给你一个无限大的整数序列 p = {1, 2, 3, ...}；

　　有 n 次操作，每次操作交换第 a_i 个数和第 a_j 个数；

　　求序列中逆序对的个数；

题解：

　　考虑交换完后的序列，存在连续的区间 [ i , j ] 使得 p[ i ] = i , 那么分下一下这种区间的特点

　　假设 i 之前有 x 个数大于 p[ i ]，那么可知对于第 i 个数有 x 个逆序对，同理，因为 p[ i+1 ] = p[ i ]

　　所以 i+1 之前也一定有且只有 x 个数大于 p[ i+1 ]，那么第 i+1 个数也有 x 个逆序对，那么对于连续的区间[i,j]

　　易的区间 [ i , j ] 与其之前的数可构成的逆序对的个数为 (j-i+1)*x 个，那么可将其映射为一个值 i ，并记录其有 (j-i+1) 个数；

　　例如，假设 n 次操作为

　　1　　4

　　1　　8

　　那么交换完后，前 8 个数的排列状况为：

　　1　　2　　3　　4　　5　　6　　7　　8

　　8　　2　　3　　1　　5　　6　　7　　4

　　那么可得区间 [2,3] 和区间[5,6]的值未发生改变，当然区间[9,+∞]也为发生改变，但[9,+∞]并不影响答案，所以不用考虑。

　　那么根据之前提到的，将为改变的大区间映射到某个值身上，并记录有多少数映射到这个值上了，如下所示：

　　1　　2　　3　　4　　5

　　8　　2　　1　　5　　4

　　映射完后，区间[2,3]合并到了2上，区间[5,7]合并到了5上，接下来就是求映射完后的数组的逆序对总个数，这就变成了经典的

　　树状数组求逆序对个数的题了。

　　这就完事了么？？？？当然不是~~~

　　考虑 4 这个值，其之前的 5 只给 4 提供了一个逆序对，但实际上 6,7 也会提供，那么这就少算了两个逆序对数，这该怎么办呢？

　　考虑某个区间 [i , j]，一共有 j-i+1 个数，易得区间 [ i , j ] 只会影响其之后且值小于 i 的数，那么就再用一次树状数组，如果来到了某个

　　映射的值，那么将 i 之后的数通过树状数组 +(j-i)，对于某个在其之后且值小于 i 的数 x ,直接在答案上额外加上 Sum(x+1)即可。

AC代码：

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
           5 #include
          
             6 using namespace std;  7 #define lowbit(x) (x&-x)  8 #define ll long long  9 #define mem(a,b) memset(a,b,sizeof(a)) 10 const int maxn=1e6+50; 11  12 int n; 13 map
           
            f;//记录交换后的序列状况 14 int diff[maxn]; 15 int sum[maxn]; 16 struct Date 17 { 18 int val; 19 int id;//初始编号 20 int tot;//如果某个区间映射到值val上，那么tot记录的就是区间的总个数 21 int newVal;//离散后的值 22 Date(int val=0,int id=0,int tot=0):val(val),id(id),tot(tot){} 23 }_date[maxn]; 24 25 struct BIT 26 { 27 int bit[maxn]; 28 void Init() 29 { 30 mem(bit,0); 31 } 32 void Add(int t,int x,int k) 33 { 34 while(t <= k) 35 { 36 bit[t] += x; 37 t += lowbit(t); 38 } 39 } 40 int Sum(int t) 41 { 42 int sum=0; 43 while(t > 0) 44 { 45 sum += bit[t]; 46 t -= lowbit(t); 47 } 48 return sum; 49 } 50 }_bit; 51 52 bool cmp1(Date a,Date b) 53 { 54 return a.val < b.val; 55 } 56 bool cmp2(Date a,Date b) 57 { 58 return a.id < b.id; 59 } 60 61 int Trans() 62 { 63 map
            
             ::iterator it; 64 int index=0; 65 int preIndex=f.begin()->first; 66 int nexIndex; 67 68 for(it=++f.begin();it != f.end();++it) 69 { 70 _date[++index]=Date(f[preIndex],index,1); 71 nexIndex=it->first; 72 73 //判断是否为未改变的区间 74 int tot=nexIndex-preIndex-1; 75 if(tot >= 1) 76 _date[++index]=Date(preIndex+1,index,tot); 77 78 preIndex=nexIndex; 79 } 80 _date[++index]=Date(f[preIndex],index,1); 81 82 sort(_date+1,_date+index+1,cmp1);//按其val由小到大排序，方便离散化 83 for(int i=1;i <= index;++i) 84 _date[i].newVal=i;//离散化 85 sort(_date+1,_date+index+1,cmp2);//按 id 从小到大复原 86 87 return index; 88 } 89 90 ll Solve() 91 { 92 //离散化 93 int index=Trans(); 94 _bit.Init();//树状数组初始化 95 ll ans=0; 96 97 //经典树状数组求逆序对个数 98 for(int i=1;i <= index;++i) 99 {100 int x=_date[i].newVal;101 _bit.Add(x,1,index);102 ans += 1ll*(i-_bit.Sum(x))*_date[i].tot;103 }104 105 //求解区间少加的逆序对个数106 _bit.Init();107 for(int i=1;i <= index;++i)108 {109 int x=_date[i].newVal;110 _bit.Add(x,_date[i].tot-1,index);//只有 tot > 1才会加入到树状数组中111 112 //求解 i 前值 > x 的未改变的区间少加的数的总个数113 if(_date[i].tot == 1)114 ans += _bit.Sum(index)-_bit.Sum(x);115 116 }117 118 return ans;119 }120 int main()121 {122 // freopen("C:/Users/hyacinthLJP/Desktop/stdin/contest","r",stdin);123 scanf("%d",&n);124 for(int i=1;i <= n;++i)125 {126 int a,b;127 scanf("%d%d",&a,&b);128 int x,y;129 x=(!f.count(a) ? a:f[a]);130 y=(!f.count(b) ? b:f[b]);131 132 f[a]=y;133 f[b]=x;134 }135 printf("%I64d\n",Solve());136 137 return 0;138 }

View Code

转载于:https://www.cnblogs.com/violet-acmer/p/10502978.html

你可能感兴趣的文章