[Solution][RMQ]JDFZOJ2471 与众不同

【题目】

戳这里

【思路】

蒟蒻又被虐了。。。看了论文才恍然大悟。。。这个模型确实有一定的借鉴价值。

问题是给定一个数字序列,有多组询问,对于每一组询问,给出一段区间,求出区间内数字两两不相同的连续序列最长长度。

我们可以在的时间内求出以每一个位置为结尾的最长不重复序列的左端位置,记作.

设每个数的上一次出现位置为,显然有

与此同时,我们也就计算出了以每一个位置为结尾的最长不重复序列的长度。

现在考虑一段询问区间。首先注意到数组的值是单调不降的,这是显然的。于是我们在区间内二分找到第一个的位置,显然这个区间的答案可以由两部分取最大值:第一部分是,长度为(以ins-1结尾的最长不重复序列截取至L);另一部分是(以ins~R结尾的最长不重复序列均包含在区间内,从中取最大长度).

再加上一些细节就可以过了。

【代码】

#include<cstdio>
#include<cstring>
#include<cctype>
#define N (200010)
inline char getc()
{
    static const int L = 1 << 15;
    static char buf[L] , *S = buf , *T = buf;
    if (S == T)
    {
        T = (S = buf) + fread(buf , 1 , L , stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
inline int getint()
{
    static char c;
    while(!isdigit(c = getc()) && c != '-');
    bool sign = (c == '-');
    int tmp = sign ? 0 : c - '0';
    while(isdigit(c = getc()))
        tmp = (tmp << 1) + (tmp << 3) + c - '0';
    return sign ? -tmp : tmp;
}
inline void swap(int &x , int &y)
{
    int tmp = x;
    x = y;
    y = tmp;
}
inline int _max(int a , int b)
{
    return a > b ? a : b;
}
int col[N] , lastins[2000010] , getmax[N][30] , maxlen[N] , furleft[N];
inline int ret(int a , int b)
{
    register int j;
    for(j = 0 ; a + (1 << j) - 1 <= b ; ++j);
    return _max(getmax[a][j - 1] , getmax[b - (1 << (j - 1)) + 1][j - 1]);
}
int main()
{
    int n , ask;
    n = getint();
    ask = getint();
    register int i , j;
    for(i = 1 ; i <= n ; ++i)
        col[i] = getint() , col[i] += 1000000;
    for(i = 1 ; i <= n ; ++i)
    {
        furleft[i] = _max(furleft[i - 1] , lastins[col[i]] + 1);
        maxlen[i] = i - furleft[i] + 1;
        lastins[col[i]] = i;
    }
    for(i = 1 ; i <= n ; ++i)
        getmax[i][0] = maxlen[i];
    for(j = 1 ; (1 << j) <= n ; ++j)
        for(i = 1 ; i + (1 << j) - 1 <= n ; ++i)
            getmax[i][j] = _max(getmax[i][j - 1] , getmax[i + (1 << (j - 1))][j - 1]);
    int a , b , L , R , mid;
    while(ask--)
    {
        a = getint();
        b = getint();
        ++a , ++b;
        if (a > b)
            swap(a , b);
        int ins;
        if (furleft[a] == a)
            ins = a;
        else if (furleft[b] < a)
            ins = b + 1;
        else
        {
            L = a , R = b;
            while(L < R)
            {
                mid = (L + R) >> 1;
                if (furleft[mid] >= a)
                    R = mid;
                else
                    L = mid + 1;
            }
            ins = L;
        }
        int ans = 0;
        if (ins > a)
            ans = _max(ans , ins - a);
        if (ins <= b)
            ans = _max(ans , ret(ins , b));
        printf("%d\n" , ans);
    }
    return 0;
}
comments powered by Disqus