近乎一樣的代碼，為什么一份AC一份RE？

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=100001;

struct Node{

    int ls,rs;

    int cnt;

}tr[maxn*20];

int cur,rt[maxn];

void init(){

    cur=0;

}

inline void push_up(int o){

    tr[o].cnt=tr[tr[o].ls].cnt+tr[tr[o].rs].cnt;

}

int build(int l,int r){

    int k=cur++;

    if (l==r) {

        tr[k].cnt=0;

        return k;

    }

    int mid=(l+r)>>1;

    tr[k].ls=build(l,mid);

    tr[k].rs=build(mid+1,r);

    push_up(k);

    return k;

}

int update(int o,int l,int r,int pos,int val){

    int k=cur++;

    tr[k]=tr[o];

    if (l==pos&&r==pos){

        tr[k].cnt+=val;

        return k;

    }

    int mid=(l+r)>>1;

    if (pos<=mid) tr[k].ls=update(tr[o].ls,l,mid,pos,val);

    else tr[k].rs=update(tr[o].rs,mid+1,r,pos,val);

    push_up(k);

    return k;

}

int query(int l,int r,int o,int v,int kth){

    if (l==r) return l;

    int mid=(l+r)>>1;

    int res=tr[tr[v].ls].cnt-tr[tr[o].ls].cnt;

    if (kth<=res) return query(l,mid,tr[o].ls,tr[v].ls,kth);

    else return query(mid+1,r,tr[o].rs,tr[v].rs,kth-res);

}

int b[maxn];

int sortb[maxn];

int main()

{

    int n,m;

    int T;

    //scanf("%d",&T);

    //while (T--){

    while (~scanf("%d%d",&n,&m)){

        init();

        for (int i=1;i<=n;i++){

            scanf("%d",&b[i]);

            sortb[i]=b[i];

        }

        sort(sortb+1,sortb+1+n);

        int cnt=1;

        for (int i=2;i<=n;i++){

            if (sortb[i]!=sortb[cnt]){

                sortb[++cnt]=sortb[i];

            }

        }

        rt[0]=build(1,cnt);

        for (int i=1;i<=n;i++){

            int p=lower_bound(sortb+1,sortb+cnt+1,b[i])-sortb;

            rt[i]=update(rt[i-1],1,cnt,p,1);

        }

        for (int i=0;i<m;i++){

            int a,b,k;

            scanf("%d%d%d",&a,&b,&k);

            int idx=query(1,cnt,rt[a-1],rt[b],k);

            printf("%d\n",sortb[idx]);

        }

    }

    return 0;

}

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

#include <iostream>

using namespace std;

const int MAXN = 100001;

struct Node{

    int l,r;

    int cnt;

}tree[20*MAXN];

int cur;    //記錄節點的個數

int root[MAXN]; //保存每一次更新的位置

int a[MAXN],b[MAXN];

void init(){

    cur=0;

}

void PushUp(int node){

    tree[node].cnt=tree[tree[node].l].cnt+tree[tree[node].r].cnt;

}

int build(int l,int r){

    int k=cur++;

    if (l==r){

        tree[k].cnt=0;

        return k;

    }

    int mid=(l+r)/2;

    tree[k].l=build(l,mid);

    tree[k].r=build(mid+1,r);

    PushUp(k);

    return k;

}

int update(int node,int l,int r,int x,int v){

    int k=cur++;

    tree[k]=tree[node];

    if (l==x && r==x){

        tree[k].cnt+=v;

        return k;

    }

    int mid=(l+r)/2;

    if (mid>=x)

        tree[k].l=update(tree[node].l,l,mid,x,v);

    else

        tree[k].r=update(tree[node].r,mid+1,r,x,v);

    PushUp(k);

    return k;

}

int query(int node1,int node2,int l,int r,int k){   //node1表示前一個版本，node2表示后一個版本

    if (l==r)

        return l;

    int mid=(l+r)/2;

    int res=tree[tree[node2].l].cnt-tree[tree[node1].l].cnt;

    if (res>=k)

        return query(tree[node1].l,tree[node2].l,l,mid,k);

    return query(tree[node1].r,tree[node2].r,mid+1,r,k-res);

}

int main(){

    int n,m;

    while (~scanf("%d%d",&n,&m)){

        init();

        for (int i=1;i<=n;i++){

            scanf("%d",&a[i]);

            b[i]=a[i];

        }

        sort(b+1,b+n+1);

        int tmp=unique(b+1,b+n+1)-b;

        root[0]=build(1,tmp);

        for (int i=1;i<=n;i++){

            int temp=lower_bound(b+1,b+tmp+1,a[i])-b;

            root[i]=update(root[i-1],1,tmp,temp,1);

        }

        for (int i=0;i<m;i++){

            int l,r,k;

            scanf("%d%d%d",&l,&r,&k);

            int temp=query(root[l-1],root[r],1,tmp,k);

            printf("%d\n",b[temp]);

        }

    }



    return 0;

}

uj5u.com熱心網友回復：

uj5u.com熱心網友回復：

uj5u.com熱心網友回復：

標籤：基礎類

上一篇：WM_SIZE中加入MessageBox時，為什么會先執行WM_PAINT里的內容，再回來執行MessageBox，為什么會發送WM_PAINT?

下一篇：神奇的bug