[树状数组]休息

本文主要是介绍[树状数组]休息，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

休息的时候，可以放松放松浑身的肌肉，打扫打扫卫生，感觉很舒服。在某一天，某LMZ 开始整理他那书架。已知他的书有n 本，从左到右按顺序排列。他想把书从矮到高排好序，而每一本书都有一个独一无二的高度Hi。他排序的方法是：每一次将所有的书划分为尽量少的连续部分，使得每一部分的书的高度都是单调下降，然后将其中所有不少于2 本书的区间全部翻转。重复执行以上操作，最后使得书的高度全部单调上升。可是毕竟是休息时间，LMZ 不想花太多时间在给书排序这种事上面。因此他划分并翻转完第一次书之后，他想计算，他一共执行了多少次翻转操作才能把所有的书排好序。LMZ 惊奇地发现，第一次排序之前，他第一次划分出来的所有区间的长度都是偶数。

Input
第一行一个正整数n, 为书的总数。

接下来一行n个数，第i个正整数Hi，为第i 本书的高度。

Output
仅一个整数，为LMZ 需要做的翻转操作的次数。

Sample Input
6
5 3 2 1 6 4

Sample Output
3

【样例解释】
第一次划分之后，翻转(5,3,2,1)，（6,4）。之后，书的高度为1 2 3 5 4 6，然后便是翻转（5,4）即可。

Data Constraint
对于10%的数据：n<=50
对于40%的数据：n<=3000
对于100%的数据：1<=n<=100000, 1<=Hi<=n

分析

显然第一次排序以后问题都出在交界处，再观察发现为求逆序对
用树状数组即可

#include <iostream>
#include <cstdio>
#define rep(i,a,b) for (i=a;i<=b;i++)
#define lowbit(x) x&(-x)
typedef long long ll;
using namespace std;
int a[100001],c[100001];
int n,k;void Insert(int x,int k) {for (int i=x;i<=n;i+=lowbit(i)) c[i]+=k;
}int Get_sum(int x) {int ans=0;for (int i=x;i;i-=lowbit(i)) ans+=c[i];return ans;
}int main() {int i,j,l;scanf("%d",&n);rep(i,1,n) scanf("%d",&a[i]);ll ans=0;j=1;rep(i,1,n-1)if (a[i]<a[i+1]) {int p=j;for (l=i;j<l;j++,l--) swap(a[j],a[l]);j=i+1;if (p==i) continue;ans++;}if (j!=n&&a[j]>a[j+1]) {for (l=n;j<l;j++,l--) swap(a[j],a[l]);ans++;}for (i=n;i>=1;i--) {ans+=Get_sum(a[i]);Insert(a[i],1);}printf("%lld",ans);
}

这篇关于[树状数组]休息的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---