procedure bubble_sort(n:longint);
var
i,j,x:longint;
begin
for i:=0 to n-1 do
for j:=0 to n-1 do
if a[j]>a[j+1] then
begin
x:=a[j];
a[j]:=a[j+1];
a[j+1]:=x;
end;
end;

一句**‘还有边界问题需要判断。’**背后蕴藏多少悲伤的故事

看到题解我想说一句：我想简单了

从小到大或者是从大到小没限制么？

我严肃地警告抄代码的人，你这是玷污我的代码！我的代码是让那些有需要的人看的，我没有闭源的习惯，但我也不希望被赤裸裸地抄袭。

这道题是这样的。
首先有一个结论是冒泡排序的交换次数等于该序列的逆序对数，不清楚的可以参考NOIP13火柴排队。

然后我们把序列A中的一个点视作坐标系中的点X(i, A[i])，我们发现，X左上方的点和X右下方的点是X贡献的逆序对。
我们还可以发现，交换两个点的时候（其中一个点在另一个点左上方时），改变的逆序对数就是这两个点构成的矩形中的点个数*2+1。
因此问题转化成，平面上有N个点，寻找一个两个点使得一个点A在另一个点B左上方且构成的矩形中包含最多的点。
首先，A的左上方不会有点，B的右下方不会有点。
我们把左上方没有点的点称为A类点，右下方没有点的点称为B类点，其他点称为C类点。
我们用扫描线+线段树。
当我们加入一个C类点的时候，会对纵坐标大于它的A类点的答案产生1的贡献，那么用线段树加进去。
当我们加入一个B类点的时候，需要弹出纵坐标小于它的C类点，需要在线段树中删除。
再询问即可。
大概思路就是这样……还有边界问题需要判断。
具体可以参见标程。

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

typedef long long ll;

int segt_max[1000010], segt_dif[1000010];

int segt_add(int a, int b, int v, int k, int l, int r) {
if (r <= a || b <= l) return segt_max[k];
if (a <= l && r <= b) {
segt_dif[k] += v;
return segt_max[k] += v;
}
else {
return segt_max[k] = segt_dif[k] + max(
segt_add(a, b, v, k * 2 + 1, l, (l + r) / 2),
segt_add(a, b, v, k * 2 + 2, (l + r) / 2, r));
}
}

ll merge_count(vector<int> &a) {
int n = a.size();
if (n <= 1) return 0;
vector<int> b(a.begin(), a.begin() + n / 2);
vector<int> c(a.begin() + n / 2, a.end());
ll res = 0;
res += merge_count(b);
res += merge_count(c);
for (int ai = 0, bi = 0, ci = 0; ai < n; ++ai) {
if (ci == (int)c.size() || (bi < (int)b.size() && b[bi] <= c[ci])) {
a[ai] = b[bi++];
} else {
a[ai] = c[ci++];
res += n / 2 - bi;
}
}
return res;
}

int N, A[1000010];
int Yu[1000010];

vector<int> Ux, Uy, L;
bool usd[1000010];

pair<int, int> get_u_range(int i) {
return mp(upper_bound(all(Uy), A[i]) - Uy.begin(),
upper_bound(all(Ux), i) - Ux.begin());
}

ll solve() {
vector<int> a(A, A + N);
ll org = merge_count(a), ans = org + 1;
rep (i, N - 1) {
if (a[i] == a[i + 1]) {
--ans;
break;
}
}

for (int i = 0; i < N; ++i) {
if (Ux.empty() || A[Ux.back()] < A[i]) {
usd[i] = true;
Ux.pb(i);
Uy.pb(A[i]);
}
}
for (int i = N - 1; i >= 0; --i) {
if ((L.empty() || A[L.back()] > A[i]) && !usd[i]) {
L.pb(i);
usd[i] = true;
}
}
reverse(all(L));

vector<int> Mx, My;
rep (i, N) if (!usd[i]) Mx.pb(i);
{
vector<pair<int, int> > tmp;
rep (i, Mx.size()) tmp.pb(mp(A[Mx[i]], Mx[i]));
sort(all(tmp));
rep (i, tmp.size()) My.pb(tmp[i].second);
}
int Un = Ux.size(), Ln = L.size(), Mn = Mx.size();

memset(segt_max, 0, sizeof(segt_max));
memset(segt_dif, 0, sizeof(segt_dif));

int mxi = 0, myi = 0;
rep (li, Ln) {
int l = L[li];

for (; mxi < Mn && Mx[mxi] < l; ++mxi) { // In
pair<int, int> ur = get_u_range(Mx[mxi]);
segt_add(ur.first, ur.second, +1, 0, 0, Un);
if (ur.first - 1 >= 0 && A[Ux[ur.first - 1]] == A[Mx[mxi]]) --ur.first;
segt_add(ur.first, ur.second, +1, 0, 0, Un);
}
for (; myi < Mn && A[My[myi]] < A[l]; ++myi) { // Out
pair<int, int> ur = get_u_range(My[myi]);
segt_add(ur.first, ur.second, -1, 0, 0, Un);
if (ur.first - 1 >= 0 && A[Ux[ur.first - 1]] == A[My[myi]]) --ur.first;
segt_add(ur.first, ur.second, -1, 0, 0, Un);
}
for (int k = 0; myi + k < Mn && A[My[myi + k]] == A[l]; ++k) { // Border
pair<int, int> ur = get_u_range(My[myi + k]);
if (ur.first - 1 >= 0 && A[Ux[ur.first - 1]] == A[My[myi]]) --ur.first;
segt_add(ur.first, ur.second, -1, 0, 0, Un);
}

pair<int, int> ur = get_u_range(l);
if (ur.first < ur.second) {
int tmp = segt_max[0];
ans = min(ans, org - tmp - 1);
}
for (; myi < Mn && A[My[myi]] == A[l]; ++myi) { // Out
pair<int, int> ur = get_u_range(My[myi]);
segt_add(ur.first, ur.second, -1, 0, 0, Un);
}
}

return ans;
}

int main() {
scanf("%d", &N);
rep (i, N) scanf("%d", &A[i]);

vector<int> nums(A, A + N);
sort(all(nums));
nums.erase(unique(all(nums)), nums.end());
rep (i, N) A[i] = lower_bound(all(nums), A[i]) - nums.begin();

printf("%lld\n", solve());
return 0;
}

/* Template the Final Chapter Light --- Fimbulvetr version 0.1 /
/ In this blizzard, I will find peace. */
# define LOCAL
# include <cstring>
# include <cstdio>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <stack>
# include <map>
# include <queue>
# include <ctime>
using namespace std;
# define REP( i, n ) for ( int i = 1; i <= n; i ++ )
# define REP_0( i, n ) for ( int i = 0; i < n; i ++ )
# define REP_0N( i, n ) for ( int i = 0; i <= n; i ++ )
# define REP_S( i, ss ) for ( char *i = ss; *i; i ++ )
# define REP_G( i, u ) for ( int i = pos[ u ]; i; i = g[ i ].frt )
# define FOR( i, a, b ) for ( int i = a; i <= b; i ++ )
# define DWN( i, a, b ) for ( int i = b; i >= a; i -- )
# define RST( a ) memset ( a, 0, sizeof ( a ) )
# define CLR( a, x ) memset ( a, x, sizeof ( a ) )
# define CPY( a, b ) memcpy ( a, b, sizeof ( a ) )
typedef long long LL;
const int inf = 1 << 30;
typedef double DB;

# define NS 100100
struct arr { int val, pos; } pre[ NS ], b[ NS ];
int a[ NS ], mx[ NS ], n, tsz, ts;
LL ans;
bool cnt1[ NS ], cnt2[ NS ];
# define u seg[ x ]
# define lc ch[ 0 ]
# define rc ch[ 1 ]
# define ulfc seg[ u.lc ]
# define urtc seg[ u.rc ]
struct segnode { int ch[ 2 ], l, r, mx, den; void Apply ( int val ) { mx += val, den += val; } void Set ( int lf, int rt ) { l = lf, r = rt; } } seg[ NS * 4 ];
void PD ( int x )
{
if ( !u.den ) return ;
if ( u.lc ) ulfc.Apply ( u.den );
if ( u.rc ) urtc.Apply ( u.den );
u.den = 0;
}
void Upd ( int x ) { u.mx = max ( ulfc.mx, urtc.mx ); }
void Build ( int x, int l, int r )
{
u.Set ( l, r );
if ( l == r ) return ;
int mid = ( l + r ) / 2;
Build ( u.lc = ++ tsz, l, mid ), Build ( u.rc = ++ tsz, mid + 1, r );
}
void Add ( int x, int ml, int mr, int val )
{
PD ( x );
if ( ml > mr ) return ;
if ( u.l == ml && u.r == mr ) { u.Apply ( val ); return ; }
int mid = ( u.l + u.r ) / 2;
if ( ml <= mid ) Add ( u.lc, ml, min ( mid, mr ), val );
if ( mr > mid ) Add ( u.rc, max ( mid + 1, ml ), mr, val );
Upd ( x );
}
int Query ( int x, int ql, int qr )
{
PD ( x );
if ( u.l == ql && u.r == qr ) return u.mx;
int mid = ( u.l + u.r ) / 2, ret = - inf;
if ( ql <= mid ) ret = max ( ret, Query ( u.lc, ql, min ( qr, mid ) ) );
if ( qr > mid ) ret = max ( ret, Query ( u.rc, max ( mid + 1, ql ), qr ) );
return ret;
}
void MergeSort ( int l, int r )
{
if ( l == r ) return ;
int mid = ( l + r ) / 2;
MergeSort ( l, mid ), MergeSort ( mid + 1, r );
int right_p = mid, tot_p = 0;
FOR ( left_p, l, mid )
{
while ( right_p < r && pre[ right_p + 1 ].val < pre[ left_p ].val )
b[ ++ tot_p ] = pre[ ++ right_p ], ans += mid - left_p + 1;
b[ ++ tot_p ] = pre[ left_p ];
}
for ( right_p ++; right_p <= r; right_p ++ ) b[ ++ tot_p ] = pre[ right_p ];
FOR ( i, l, r ) pre[ i ] = b[ i - l + 1 ];
}
int main ()
{
scanf ( "%d", &n ), Build ( tsz = 1, 1, n );
REP ( i, n ) scanf ( "%d", &pre[ i ].val ), pre[ i ].pos = i;
MergeSort ( 1, n );
int preCnt = 0; pre[ 0 ].val = - inf;
REP ( i, n )
{
if ( pre[ i ].val != pre[ i - 1 ].val ) preCnt ++;
a[ pre[ i ].pos ] = preCnt;
}
int mn = inf;
DWN ( i, 1, n ) cnt2[ i ] = a[ i ] >= mn, mn = min ( a[ i ], mn );
REP ( i, n ) mx[ i ] = max ( mx[ i - 1 ], a[ i ] ), cnt1[ i ] = mx[ i - 1 ] >= mx[ i ];
int del_p = 0;
REP ( i, n )
{
if ( !cnt1[ i ] ) ;
else if ( !cnt2[ i ] )
{
for ( int j; del_p < n && a[ j = pre[ del_p ].pos ] < a[ i ]; del_p ++ )
if ( cnt1[ j ] && cnt2[ j ] )
Add ( 1, a[ j ] + 1, mx[ j ], -1 ), Add ( 1, a[ j ], mx[ j ], -1 );
int tp = del_p;
for ( int j; del_p < n && a[ j = pre[ del_p ].pos ] == a[ i ]; del_p ++ )
if ( cnt1[ j ] && cnt2[ j ] ) Add ( 1, a[ j ], mx[ j ], -1 );
del_p = tp;
ts = max ( ts, Query ( 1, a[ i ], n ) );
for ( int j; del_p < n && a[ j = pre[ del_p ].pos ] == a[ i ]; del_p ++ )
if ( cnt1[ j ] && cnt2[ j ] ) Add ( 1, a[ j ] + 1, mx[ j ], -1 );
}
else Add ( 1, a[ i ] + 1, mx[ i ], 1 ), Add ( 1, a[ i ], mx[ i ], 1 );
}
if ( ans ) printf ( "%lld\n", ans - ts - 1 );
else printf ( "%d\n", preCnt == n );
return 0;
}

这道题不能用树状数组维护吗?

球题解。。。。

题解要早发