NC50446 [与众不同] 题解

题意简化：

给定一个长度为的序列，m个询问,每次询问一个区间内最长的没有重复数字的子序列,以及 <=
样例:

9 2
2 5 4 1 2 3 6 2 4
0 8
2 6

output:

6
5

思路一:

简单暴力，枚举区间内的子序列，然后O扫一遍，总的时间复杂度是O

思路二:

借助线段树，枚举子区间，判断,总的时间复杂度是:O

显然上面两个都是错误的，但是第二个貌似时间上更优秀......
继续想!

思路三:

二分最长的长度，对于判断，每一次枚举左端点，那么右端点便是固定的，然后借助线段树O

上面这个解法已经比思路一和二优秀很多了。但是还是过不掉这道题，怎么办?

继续思考。

思路四：

记录每一个元素的前一个与它相同的元素的位置是哪一个。

我们发现，对于一个左端点来说，其最长的，没有重复数字的子序列的长度是固定的。

固定左端点后，我们总是希望不停的往右边挪动右端点以求能够有一个最长的子序列。

实际上，我们对于每一个左端点，不停移动右端点(这个右端点只会增加而不会减小，你不妨手玩几组，想一想，为什么)，总的时间复杂度O()，可行，动手写代码。

对于每一个点，当它为左端点时不妨设其最长没有重复元素的子段的右端点为:

同时，我们观察到，得到的序列是单调不降的，于是就方便处理，用二分.

对于一个查询怎么办?
区间 之间的任意一个点作为左端点

• Case 1 左端点对应的最长的没有重复元素的子序列的右端点大于，

  显然这些左端点只有最左边的那个是"有用"的,同时因为得到的是单调不降的，我们很容易用二分找到这一个最左边的大于的点。

• Case2 左端点对应的最长的没有重复元素的子序列的右端点小于等于的，

  取最大的(预处理出),ST表 线段树维护即可，但是这里显然用ST表更优。

比较上下两种情况即可

总的时间复杂度为:O

Code :

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005 , MAXM = 200005;
int n , m,M ,flag,tot = 1;
int a[MAXN],Last[MAXN],book[MAXN],R[MAXN];
int T[MAXN],Max[MAXN][25];

struct Node {
    int data,id;
} P[MAXN];

void Prepare();
int cmp(Node A, Node B);
int GetMax(int l,int r)
{
    if(l > r)return 0;
    int k = log2(r - l + 1);
    return max(Max[l][k] , Max[r - (1 << k) + 1][k]);
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++)
        cin >> a[i],P[i].id = i , P[i].data = a[i];
    Prepare();//离散化等预处理
    for(int i = 1 ; i <= n ; i ++)
    {
        int S = R[i - 1];
        while(S + 1 <= n)
        {
            if(i <= Last[S + 1] && Last[S + 1] <= S)break;
            S ++;//只增不降
        }
        R[i] = S;
        T[i] = R[i] - i + 1;
        Max[i][0] = T[i];
    }
    for(int j = 1 ; j <= log2(n) ; j ++)
        for(int i = 1 ; i + (1 << j) - 1 <= n ; i ++)
    Max[i][j] = max(Max[i][j - 1] , Max[i + (1 << (j - 1))][j - 1]);
    for(int v = 1 ; v <= m ; v ++)
    {
        int l,r;
        cin >> l >> r;
        l ++ , r ++;
        int S = r,Ans = -1;
        for(int i = log2(r - l + 1) + 1; i >= 0; i --)
        if(S - (1 << i) >= l && R[S - (1 << i)] > r)S = S - (1 << i);//二分我换成了倍增
        Ans = r - S + 1;//Case 1
        Ans = max(Ans,GetMax(l,S - 1));
        cout << Ans << endl;
    }
    return 0;
}

void Prepare()
{
    sort(P + 1 , P + 1 + n , cmp);
    for(int i = 1 , now = 1; i <= n ; i ++)
    {
        if(P[i].data != P[i - 1].data)now ++;
        a[P[i].id] = now;
    }//离散化
    R[0] = 1;
    for(int i = 1 ; i <= n ; i ++)
    {
        Last[i] = book[a[i]];
        book[a[i]] = i;
        M = max(Last[i],M);
    }//找last[i]
    return ;
}

int cmp(Node A , Node B)
{
    return A.data < B.data;
}