[原创]华中农业大学第五届程序设计大赛 G Sequence Number [树上二分]【数据结构】

2017-05-26 21:50:28 Tabris_ 阅读数：401

博客爬取于2020-06-14 22:40:32
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72773915

题目链接:http://acm.hzau.edu.cn/problem.php?id=1205
————————————————————————————————————————————
1205: Sequence Number
Time Limit: 1 Sec Memory Limit: 1280 MB
Submit: 934 Solved: 242
[Submit][Status][Web Board]
Description
In Linear algebra, we have learned the definition of inversion number:

Assuming A is a ordered set with n numbers ( n > 1 ) which are different from each other. If exist positive integers i , j, ( 1 ≤ i ＜ j ≤ n and A[i] ＞ A[j]), < A[i], A[j]> is regarded as one of A’s inversions. The number of inversions is regarded as inversion number. Such as, inversions of array <2,3,8,6,1> are <2,1>, <3,1>, <8,1>, <8,6>, <6,1>,and the inversion number is 5.

Similarly, we define a new notion —— sequence number, If exist positive integers i, j, ( 1 ≤ i ≤ j ≤ n and A[i] <= A[j], < A[i], A[j]> is regarded as one of A’s sequence pair. The number of sequence pairs is regarded as sequence number. Define j – i as the length of the sequence pair.

Now, we wonder that the largest length S of all sequence pairs for a given array A.

Input
There are multiply test cases.

In each case, the first line is a number N(1<=N<=50000 ), indicates the size of the array, the 2th ~n+1th line are one number per line, indicates the element Ai （1<=Ai<=10^9） of the array.

Output
Output the answer S in one line for each case.

Sample Input
5
2 3 8 6 1
Sample Output
3

——————————————————————————————————————
题目大意：
就是给你一个序列，然你求(1≤i≤j≤n and Ai≤Aj）( 1 ≤ i ≤ j ≤ n\ and \ A_i ≤ A_j）下j−ij-i的最大值

解题思路:

首先记录每个数的索引,

然后按数值大小升序排序

然后遍历每次将索引更新到树上,并查找索引在他之前最小的那个位置是多少.

维护最大值就好了

复杂度O(nlog⁡n)O(n\log n)

听说用单调栈降到O(n)O(n)

附本题代码
————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N   = 5e4+7;
const int INF = (~(1<<31));

int read(){
    int x=0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9') ch = getchar();
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch = getchar();}
    return x*f;
}
/*******************************************/

int n;
struct node {
    int v,id;
}a[N];

bool cmp(node A,node B){
    return A.v<B.v;
}

int sum[N<<2];

void build(int rt,int l,int r){
    sum[rt]=0;
    if(r==l) return;
    int m = r+l >> 1;
    build(rt<<1,l,m);
    build(rt<<1|1,m+1,r);
}

void pushup(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void update(int rt,int l,int r,int pos,int v){
    if(l==r) {sum[rt]=1;return;}
    int m = r+l >> 1;
    if(pos<=m) update(rt<<1,l,m,pos,v);
    else       update(rt<<1|1,m+1,r,pos,v);
    pushup(rt);
}

int query(int rt,int l,int r,int n){
    if(r==l) return l;
    int m = r+l >> 1;
    if(sum[rt<<1]>=n) return query(rt<<1,l,m,n);
    else              return query(rt<<1|1,m+1,r,n-=sum[rt<<1]);
}

int main(){
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)     scanf("%d",&a[i].v),a[i].id=i;
        build(1,1,n);
        sort(a+1,a+n+1,cmp);

        int mx = -1;
        for(int i=1;i<=n;i++){
           // printf("%d-%d=%d\n",a[i].id,query(1,1,n,1),a[i].id-query(1,1,n,1));
            mx = max(mx,a[i].id-query(1,1,n,1));
            update(1,1,n,a[i].id,1);
        }
        printf("%d\n",mx);

    }
    return 0;
}