# [洛谷春令营 省选第一次模拟T2] 最长不下降子序列【二分+归并排序】

• 2018-02-15
• 0
• 0

```5
3 2 1 5 4```

```2
1 3
4 5```

n≤100

n≤1000

0≤序列中的数字≤5

## Solution:

# 我的 Code 竟然跑了 rank 1 !!! #

• => 0 0 0 0 1 1 1 1 1 1|0 0 0 0 0 0 1 1 1 1
• => 0 0 0 0[1 1 1 1 1 1 0 0 0 0 0 0]1 1 1 1
• => 0 0 0 0[0 0 0 0 0 0 1 1 1 1 1 1]1 1 1 1
• => 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1

## Code: O(nlog2n) [3402K, 40MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

inline void getint(int &num){
char ch;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int n, a[32005];
int ansl[4000000], ansr[4000000], ans = 0;

inline void Merge_Sort(int a[], int l, int r, int key){
if(l >= r) return;
int mid = l + r >> 1;
Merge_Sort(a, l, mid, key);
Merge_Sort(a, mid + 1, r, key);

int revl, revr;
for(revl = l; a[revl] <= key && revl <= mid; revl++);
for(revr = mid + 1; a[revr] <= key && revr <= r; revr++);
if(revl > mid || --revr <= mid) return;
ansl[++ans] = revl, ansr[ans] = revr;
for(; revl < revr; revl++, revr--) swap(a[revl], a[revr]);
}

inline void solve(int a[], int l, int r, int vl, int vr){
if(l >= r || vl >= vr) return;
int key = vl + vr >> 1;
Merge_Sort(a, l, r, key);
int mid = lower_bound(a + l, a + r + 1, key + 1) - a;  // Find the first larger one
solve(a, l, mid - 1, vl, key);
solve(a, mid, r, key + 1, vr);
}

int main(){
getint(n);
for(register int i = 1; i <= n; i++) getint(a[i]);
solve(a, 1, n, -1, 32000);
printf("%d\n", ans);
for(register int i = 1; i <= ans; i++)
printf("%d %d\n", ansl[i], ansr[i]);
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai