程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> acdreamoj1108（The kth number）

acdreamoj1108（The kth number）

編輯：C++入門知識

題意:n個數的數列，m次查詢某個區間出現次數第k多的數出現的次數。n，m<=100000

解法：這個因為是離線的所以可以先統一處理，然後再輸出。可以維護一個left和right指針，pre，pre[i]表示此時區間內出現次數大於等於i的數的種類。為了減少復雜度，關鍵是left和right的移動方式，即查詢區間如何排序，如果緊靠區間左端點排序，那麼右端點每次一定最大回是n，如果按照右端點排序，左端點每次一定最大是n。這裡有個很好的處理辦法，就是模糊排序，先左端點非嚴格排序，即除以sqrt(n)再排序，這樣復雜度最大是n*sqrt(n)

代碼：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, /STACK:102400000,102400000)
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
//freopen (in.txt , r , stdin);
using namespace std;

#define eps 1e-8
#define zero(_) (abs(_)<=eps)
const double pi=acos(-1.0);
typedef long long LL;
const int Max=100010;
const int INF=1e9+7;

int num[Max];
int help[Max];
int r[Max];
int l[Max];
int k[Max];
int pre[Max];
int cnt[Max];
int tool;
bool cmp(int i,int j)
{
    if(l[i]/tool==l[j]/tool&&r[i]!=r[j])
        return r[i]=t)
        l=middle+1;
        else
            r=middle-1;
    }
    return l-1;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        scanf(%d%d,&n,&m);
        tool=sqrt(n);
        for(int i=0; i