Codeforces 616D Longest k-Good Segment【尺取法】

D. Longest k-Good Segment time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

The array a with n integers is given. Let's call the sequence of one or more consecutive elements in a segment. Also let's call the segment k-good if it contains no more than k different values.

Find any longest k-good segment.

As the input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input

The first line contains two integers n, k (1 ≤ k ≤ n ≤ 5·10⁵) — the number of elements in a and the parameter k.

The second line contains n integers a_i (0 ≤ a_i ≤ 10⁶) — the elements of the array a.

Output

Print two integers l, r (1 ≤ l ≤ r ≤ n) — the index of the left and the index of the right ends of some k-good longest segment. If there are several longest segments you can print any of them. The elements in a are numbered from 1 to n from left to right.

Examples Input 5 5 1 2 3 4 5 Output 1 5 Input 9 3 6 5 1 2 3 2 1 4 5 Output 3 7 Input 3 1 1 2 3 Output 1 1

题目大意：

给你长度为N的一个序列，让你找到一个最长的连续子序列，使得其中元素的种类数不超过K个。

思路：

很裸的尺取法的问题啊。

我萌维护一个窗口，使得窗口一直保证是一个连续合法子序列，过程维护一个最长就行啊。

Ac代码：

#include<stdio.h> #include<string.h> #include<map> using namespace std; int a[505000]; int main() { int n,k; while(~scanf("%d%d",&n,&k)) { for(int i=0;i<n;i++)scanf("%d",&a[i]); int sum=0; int l=0; int r=0; int L,R; int output=0; map<int ,int >s; while(r<n) { s[a[r]]++; if(s[a[r]]==1)sum++; if(sum<=k) { if(r-l+1>output) { L=l,R=r; output=r-l+1; } } if(sum==k) { while(r+1<n) { if(s[a[r+1]]==0)break; else s[a[r+1]]++,r++; if(r-l+1>output) { L=l,R=r; output=r-l+1; } } while(l<=r&&sum==k) { s[a[l]]--; if(s[a[l]]==0)sum--; l++; } } r++; } printf("%d %d\n",L+1,R+1); // printf("%d\n",output); } }