D 温澈滢的狗狗

其他题目题解点击此处，持续更新……

思路

这个题目看了我好久，，（主要是太菜了）
做题的时候想到了用二分，但是不知道怎么去定义它的性质。
两两不同颜色的狗之间会产生亲密度，对每一对有亲密度的狗按照关键词进行排序，求第k对狗的下标。
如果模拟的话肯定会超时，所以要往快速找到第k对狗的方向想，会想到使用二分思想。
想到用二分思想就要想能不能找到一个能够二分的条件。
第一关键词是按照亲密度去的，所以想想能不能以亲密度去划分。
我们假设第k对的亲密度为x，那么就说明 的部分是不需要的，所以就有明显的二分性。

知道了以亲密度作为判断条件，那么接下来的步骤就是完善细节，计算每个亲密度的个数。
只有颜色不同才会有亲密度，直接求有点麻烦，时间复杂度也会比较高，直接求不行，那么就试试间接的求法：

设x为亲密度，我们将同色点都放到同一个下标的数组中。
总点对数 ：
我们知道亲密度了，（亲密度是下标距离）那么从下标1开始到(n - x) 分别做区间，每个区间都可以取x个数与区间第一个点形成对，有（n - x ）个区间，所以就为, 后部分区间不能延长了，到达总下标的末端了，所以可取值分别为,等差数列求和就得出了 。
同色点数利用双指针求解即可（这个不知道怎么用讲，看代码吧。）

二分具体条件出来了，那么就可以求出来最大亲密度为 总对数小于 的 值。
所以第k对狗的亲密度为。
亲密度知道了，直接for循环找即可。

AC代码

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

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % MOD
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 100000 + 10;
int c[N], n;
ll k;
vi same[N];

ll cal(ll x)
{
    ll tot = (n - x) * x + x * (x - 1) / 2;
    _rep(i, 1, n)
    {
        int r = 0, sz = same[i].size();
        _for (j, 0, sz)
        {
            while (r < sz && same[i][r] - same[i][j] <= x) ++r;
            tot -= r - j - 1;
        }
    }
    return tot;
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    cin >> n >> k;
    _rep(i, 1, n)
    {
        cin >> c[i];
        same[c[i]].push_back(i);
    }

    if (cal(n) < k) return puts("-1"), 0;

    int l = 0, r = n;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (cal(mid) < k) l = mid;
        else r = mid - 1;
    }

    int dist = l + 1;
    ll cnt = cal(l);
    _rep(i, 1, n - dist) if (c[i] != c[i + dist])
    {
        cnt++;
        if (cnt == k)
        {
            cout << i << " " << i + dist << endl;
            break;
        }
    }

    return 0;
}