程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ2104

POJ2104

編輯：關於C++

題目意思很簡單，就是給你一個序列，查詢某區間第K大的數；

方法1：時間復雜度O(N*M)；不支持更新操作，代碼簡單；

利用結構體排序，保留原數據的順序。

#include 
#include 
#include 
#define N 100000
using namespace std;
/*
    這個思路很好；時間復雜度O(n*m)；
    不過還好這個題目給的數據量不大，而且時間限制給了2s，所以可以很輕松的過；
*/
struct NODE
{
    int x,id;
}node[N];
bool cmp(NODE a,NODE b)
{
    return a.x=a&&node[j].id<=b)    k--;
                if(!k)
                {
                    printf(%d
,node[j].x);
                    break;
                }
            }
        }
    }
    return 0;
}

方法2：歸並樹，時間復雜度O(nlogn+mlong^3(n))；利用歸並排序，用線段樹位數數組順序；

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define inf 1<<30
#define s(a) scanf(%d,&a)
#define Clear(a,b) memset(a,b,sizeof(a))
using namespace std;
/*
    O(nlogn+mlog^3(n))
*/
const int N=200005;
int n,m,a,b;
int seg[25][N];
int num[N];
void Merge_Sort(int l,int r,int deep)   //  每一層保留該層已經排好的數據；
{
    int mid=(l+r)>>1;
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(seg[deep+1][i]<=seg[deep+1][j]){
            seg[deep][k++]=seg[deep+1][i++];
        }else{
            seg[deep][k++]=seg[deep+1][j++];
        }
    }
    while(j<=r){
        seg[deep][k++]=seg[deep+1][j++];
    }
    while(i<=mid){
        seg[deep][k++]=seg[deep+1][i++];
    }
}
void Build(int l,int r,int rt,int deep)    //   建樹；deep根節點的深度；
{
    if(l==r){
        seg[deep][l]=num[l];        //  單葉子節點按輸入的順序存數據；
        return;
    }
    int mid=(l+r)>>1;
    Build(l,mid,rt<<1,deep+1);
    Build(mid+1,r,rt<<1|1,deep+1);
    Merge_Sort(l,r,deep);       //  歸並排序；
}
int Query(int v,int deep,int L,int R,int l,int r,int rt)    //  查詢[L,R]區間比v小的數有多少個；
{
    if(r=r){
        return lower_bound(&seg[deep][l],&seg[deep][r]+1,v)-&seg[deep][l];  //  返回第一個大於等於v的下標；
    }
    int mid=(l+r)>>1;
    return Query(v,deep+1,L,R,l,mid,rt<<1)+Query(v,deep+1,L,R,mid+1,r,rt<<1|1);
}
int Solve(int l,int r,int k){       //  二分查找[L,R]，降低時間復雜度；
    int L=1,R=n,mid;
    while(L>1;     //  這裡要特別注意；mid=(L+R+1)>>1;不是mid=(L+R)>>1;
        int cnt=Query(seg[1][mid],1,l,r,1,n,1);     //  返回比v小的個數；
        if(cnt<=k){     //  如果小於等於我們要查找的k，說明seg[1][mid]這個數太小了，網右邊查找；
            L=mid;
        }else{
            R=mid-1;
        }
    }
    return seg[1][L];
}
int main()
{
    while(~scanf(%d%d,&n,&m)){
        for(int i=1;i<=n;i++) s(num[i]);
        Build(1,n,1,1);
        while(m--){
            int l,r,k;
            s(l);s(r);s(k);
            printf(%d
,Solve(l,r,k-1));  //  這裡也值得注意一下，輸入的是k-1,不是k；
        }
    }
    return 0;
}

方法3：劃分樹;好吧，這個思路我還沒有整理好，給這個牛逼算法留一塊空地；^_^....