牛课2020夏季赛第六场K题

非常精彩的一道题，记录一下

题目大意是这样：形如1 2 3或者3 1 2这样的1-n每个数字都出现一次的数列称作一个全排列。由若干个全排列组成的数列，如1 2 3 1 3 2 3 1 2，称作一个k-bag。k-bag的一个连续的子数列称为part-k-bag。给你一个数列，给定k，问它有没有可能是一个part-k-bag?

首先数列里任何数都不能>k。然后很容易想到，对任意pn1=s,pn2=s,显然pn1与pn2不能在一组内。由此可见n1与n2之间(包括n1与n2)一定存在m与m+1，使得pm与pm+1不在一组内。显然，pm-k与pm-k+1也不在一组内，pm+k与pm+k-1也不在一组内。因此，我们找出所有相连的相同的数，如果它们的距离小于k,这说明这两个数之间一定有分隔。用这种方法可以缩小分隔的范围。

随后，问题可以转化为给定若干的区间，问是否有值在所有的区间内。要注意的是给定的区间可以是[4,2]，也就是[4,k]∪[0,2]。通过一点手段可以在O(n)的时间内找出是否存在值。
就是这个手段卡了我四个小时。最后我把一个[0,k]分成了两个部分。无论你给出的是什么区间，缩小范围之后，它总是能用两个连续的区间表示。注意一下缩小范围的方法即可。

#include<stdio.h>
#include<iostream>
#include<algorithm>

using namespace std;

long long p[500002]={0},q[500002]={0},le[500002]={0},ri[500002]={0};

int main()
{
    long long t,n,k,add,lp,rp,temp,flag,x;
    long long l1,l2,r1,r2;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        flag=0,x=0,lp=0,rp=0,temp=0;
        l1=-1,l2=-1;
        if(k<n)
            r1=k-1,r2=k-1;
        else
            r1=n-1,r2=n-1;

        for(add=0;add<n;add++)
        {
            scanf("%lld",&p[add]);
            if(p[add]>k)
                flag=1;
            p[add]=p[add]*10000000+add;
        }
        if(flag)
        {
            cout<<"NO"<<endl;
            continue;
        }

        sort(p,p+n);

        for(add=0;add<n;add++)
        {
            q[add]=p[add]%10000000;
            p[add]=p[add]/10000000;
        }

        for(add=1;add<n;add++)
            if(p[add]==p[add-1])
                if(q[add]-q[add-1]<k)
                {
                    le[x]=q[add-1]%k;
                    ri[x]=q[add]%k;
                    x++;
                }

        for(add=0;add<x;add++)
        {
            if(le[add]>ri[add])
            {
                if(ri[add]<r1)
                {
                    if(le[add]<l1);
                    else if(le[add]<r1)
                        l1=le[add];
                    else
                        r1=ri[add];
                }
                if(le[add]>l2)
                {
                    if(ri[add]>r2);
                    else if(ri[add]>l2)
                        r2=ri[add];
                    else
                        l2=le[add];
                }
            }
            else
            {
                if(l1<le[add]) l1=le[add];
                if(l2<le[add]) l2=le[add];
                if(r1>ri[add]) r1=ri[add];
                if(r2>ri[add]) r2=ri[add];
            }
        }        


        if(l1>=r1&&l2>=r2)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }


    return 0;
}