hihoCoder1483区间价值(离散化+二分答案+尺取法)

题目3 : 区间价值

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

描述

给定n个数A1...An，小Ho想了解AL..AR中有多少对元素值相同。小Ho把这个数目定义为区间[L,R]的价值，用v[L,R]表示。

例如1 1 1 2 2这五个数所组成的区间的价值为4。

现在小Ho想知道在所有的的v[L,R](1 <= L <= R <= n)中，第k小的值是多少。

输入

第一行一个数T(T<=10)，表示数据组数。

对于每一组数据：

第一行两个数n，k（1<=n<=200,000,1<=k<=n*(n+1)/2）

第二行n个数A1…An(1<=Ai<=1,000,000,000)

输出

一个数表示答案。

样例输入

2
4 7
1 1 2 3
3 6
100 100 100

样例输出

0
3

又是一题二分题，比赛时没做出来。。。。看别人代码懂了。。

思路：问第k小的结果，就二分答案。用双指针（好像专业点的方法叫尺取法）验证答案。

几个点要考虑：

1.k会爆int，答案也会爆int

2.尺取法的算法思路

3.二分别写错了。。。- -反正我经常写错

 
  
   
    
   
   
    
     #include <bits/stdc++.h>
    
   
  
   
    
   
   
    
     const 
     int N = 
     200010;
    
   
  
   
    
   
   
    
     using 
     namespace 
     std;
    
   
  
   
    
   
   
    
     typedef 
     long 
     long ll;
    
   
  
   
    
   
   
     
    
   
  
   
    
   
   
    
     int num[N];
    
   
  
   
    
   
   
    
     int a[N], n;
    
   
  
   
    
   
   
    
     ll k;
    
   
  
   
    
   
   
    
     map<
     int, 
     int>mp;
    
   
  
   
    
   
   
    
     bool judge(ll x)
    
   
  
   
    
   
   
    
     {
    
   
  
   
    
   
   
    
      ll cur = 
     0, rk = 
     0;
    
   
  
   
    
   
   
     
     int l = 
     0;
    
   
  
   
    
   
   
     
     for (
     int i = 
     0; i < n; i++)
    
   
  
   
    
   
   
    
      a[i] = 
     0;
     //统计当前有多少个数
    
   
  
   
    
   
   
     
    
   
  
   
    
   
   
     
     for (
     int i = 
     0; i < n; i++)
    
   
  
   
    
   
   
    
      {
    
   
  
   
    
   
   
    
      cur += a[num[i]];
     //把当前数贡献的价值加进去
    
   
  
   
    
   
   
    
      a[num[i]]++;
    
   
  
   
    
   
   
     
     while (cur > x)
     //要求小于等于k的区间价值个数，值大于x要减去
    
   
  
   
    
   
   
    
      {
    
   
  
   
    
   
   
    
      cur -= --a[num[l++]];
     //把最开始的数价值贡献减去
    
   
  
   
    
   
   
    
      }
    
   
  
   
    
   
   
    
      rk += i - l + 
     1;
     //如果[l, i]区间的价值小于等于x，那么i不动，l增加，
    
   
  
   
    
   
   
     
     //得到的价值只会更小，所以以l开头，i结尾的区间都符合要求
    
   
  
   
    
   
   
    
      }
    
   
  
   
    
   
   
     
     return rk >= k;
     //小于等于当前值的区间数大于等于k，就把答案扩进二分的区间了。
    
   
  
   
    
   
   
    
     }
    
   
  
   
    
   
   
    
     int main()
    
   
  
   
    
   
   
    
     {
    
   
  
   
    
   
   
     
     int T;
    
   
  
   
    
   
   
     
     scanf(
     "%d", &T);
    
   
  
   
    
   
   
     
     while (T--)
    
   
  
   
    
   
   
    
      {
    
   
  
   
    
   
   
     
     int tot = 
     0;
    
   
  
   
    
   
   
    
      mp.clear();
    
   
  
   
    
   
   
     
     scanf(
     "%d%lld", &n, &k);
    
   
  
   
    
   
   
     
     for (
     int i = 
     0; i < n; i++)
    
   
  
   
    
   
   
    
      {
    
   
  
   
    
   
   
     
     scanf(
     "%d", num + i);
    
   
  
   
    
   
   
     
     if (mp.find(num[i]) == mp.end())
    
   
  
   
    
   
   
    
      mp[num[i]] = tot++; 
     //离散化方便后面统计 
    
   
  
   
    
   
   
    
      num[i] = mp[num[i]]; 
    
   
  
   
    
   
   
    
      }
    
   
  
   
    
   
   
    
      ll l = 
     0, r = (ll)n*(n
     -1)/
     2;
    
   
  
   
    
   
   
     
     while (l < r)
    
   
  
   
    
   
   
    
      {
    
   
  
   
    
   
   
    
      ll mid = (l + r)>>
     1;
    
   
  
   
    
   
   
     
     if (judge(mid))
    
   
  
   
    
   
   
    
      r = mid;
     //答案在区间里面，则更小范围的区间是[l, mid]
    
   
  
   
    
   
   
     
     else
    
   
  
   
    
   
   
    
      l = mid + 
     1;
     //答案不在区间在答案在[mid+1, r]区间
    
   
  
   
    
   
   
    
      }
    
   
  
   
    
   
   
     
     printf(
     "%lld\n", l);
    
   
  
   
    
   
   
    
      }
    
   
  
   
    
   
   
     
     return 
     0;
    
   
  
   
    
   
   
    
     }