(POJ) K-th Number [靜態第K大] [整體二分]

http://poj.org/problem?id=2104

法一：可持久化線段樹 + 二分搜

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 1e5 + 6;
const int MAX_P = 22*MAX_N;
const int INF = 1e9 + 7;

struct Node {
    static Node mem[MAX_P];
    Node *lc,*rc;
    int val;
    Node() {
        lc=rc=NULL;
        val=0;
    }
    void pull() {
        val = lc->val + rc->val;
    }
} Node::mem[MAX_P],*ptr=Node::mem;

Node *getNode(Node* node) {
    Node* tmp=new(ptr++)Node();
    tmp->val = node->val;
    tmp->lc = node->lc;
    tmp->rc=node->rc;
    return tmp;
}

Node* Build(int L,int R) {
    Node* node = new (ptr++)Node();
    if (L==R) {
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    return node;
}

void modify(Node* pre,Node* now,int L,int R,int pos,int val) {
    if (L==R) {
        now->val += val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos<=mid) {
        now->lc = getNode(pre->lc);
        modify(pre->lc,now->lc,L,mid,pos,val);
    }
    else {
        now->rc = getNode(pre->rc);
        modify(pre->rc,now->rc,mid+1,R,pos,val);
    }
    now->pull();
}

int query(Node* node,int L,int R,int l,int r) {
    if (l>R || L>r) return 0;
    else if (l<=L && R<=r) return node->val;
    int mid=(L+R)>>1;
    return query(node->lc,L,mid,l,r) + query(node->rc,mid+1,R,l,r);
}

int a[MAX_N];
Node *root[MAX_N];

int main () {
    
        int n,q;
        scanf("%d %d",&n,&q);
        vector<int> v;
        v.push_back(-INF);
        for (int i=1;n>=i;i++) {
            scanf("%d",&a[i]);
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        v.resize(unique(v.begin(),v.end()) - v.begin());
        int m=v.size()-1;
        root[0] = Build(1,n);
        for (int i=1;n>=i;i++) {
            a[i] = lower_bound(v.begin(),v.end(),a[i]) - v.begin();
            root[i] = getNode(root[i-1]);
            modify(root[i-1],root[i],1,m,a[i],1);
        }
        while (q--) {
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            x--;
            int L=0,R=m+1;
            while (R-L > 1) {
                int mid=(L+R)>>1;
                if (query(root[y],1,m,1,mid) - query(root[x],1,m,1,mid) < z) L=mid;
                else R=mid;
            }
            printf("%d\n",v[R]);
        }
        ptr = Node::mem;
    
}

法二：可持久化線段樹

延續上一種作法，發現，可以一次遞迴兩顆線段樹，不用再特別寫二分搜XD

code provided by boook

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define REP(i,j,k)     for(int i = j ; i < k ; ++i)
#define RREP(i,j,k)    for(int i = j ; i >=k ; --i)
#define A    first
#define B    second
#define mp   make_pair
#define pb   push_back
#define PII pair<int , int>
#define MEM(i,j)   memset(i , j , sizeof i)
#define ALL(i)     i.begin() , i.end()
#define DBGG(i,j)     cout << i << " " << j << endl
#define DB4(i,j,k,l)  cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie() , cout.sync_with_stdio(0)
#define endl "\n"
///------------------------------------------------------------
#define MAX 100900
#define INF 0x3f3f3f3f
#define mid ((l + r) >> 1)
 
int sum[MAX * 20] , ls[MAX * 20] , rs[MAX * 20] , root[MAX * 20] , po = 2;
int n , m , x[MAX];
void Copy(int now , int dot){
    sum[now] = sum[dot];
    ls[now] = ls[dot];
    rs[now] = rs[dot];
}
int update(int dot , int l , int r , int val){
    int now = po ++;
    Copy(now , dot);
    if(l == val && r == val) return sum[now] ++ , now;
    else {
        if(val <= mid + 0) ls[now] = update(ls[now] , l , mid + 0 , val);
        if(mid + 1 <= val) rs[now] = update(rs[now] , mid + 1 , r , val);
        sum[now] = sum[ls[now]] + sum[rs[now]];
        return now;
    }
}
int query(int r1 , int r2 , int l , int r , int k){
    if(l == r) return l;
    else{
        int lsum = sum[ls[r2]] - sum[ls[r1]];
        if(k <= lsum) return query(ls[r1] , ls[r2] , l , mid + 0 , k);
        else          return query(rs[r1] , rs[r2] , mid + 1 , r , k - lsum);
    }
}
int main(){
    IOS;
    while(cin >> n >> m){
        vector<int> uni;
        REP(i , 1 , n + 1) cin >> x[i];
        REP(i , 1 , n + 1) uni.pb(x[i]);
        sort(ALL(uni));
        uni.resize(unique(ALL(uni)) - uni.begin());
        REP(i , 1 , n + 1) x[i] = lower_bound(ALL(uni) , x[i]) - uni.begin();
        root[0] = 1 , po = 2;
        REP(i , 1 , n + 1){
            root[i] = update(root[i - 1] , 0 , n , x[i]);
        }
        REP(i , 1 , m + 1){
            int l , r , k;
            cin >> l >> r >> k;
            cout << uni[query(root[l - 1] , root[r] , 0 , n , k)] << endl;
        }
    }
    return 0;
}

法三：整體二分( N (lg N)^2 版本 )

模板略~

const int N = 1e5 + 6;

struct BIT {
    int n;
    int a[N];
    void init(int n) {
        this->n = n;
        MEM0(a);
    }
    void add(int pos,int val) {
        for (int i=pos;n>=i;i+=i&(-i)) {
            a[i] += val;
        }
    }
    int qry(int pos) {
        int ret=0;
        for (int i=pos;i>=1;i-=i&(-i)) {
            ret += a[i];
        }
        return ret;
    }
    int query(int L,int R) {
        return qry(R) - qry(L-1);
    }
} bit;

int n,q;

vector<int> v;
int ans[N];
int a[N];

int qL[N],qR[N],qK[N];
vint pos[N];

void do_things(int L,int mid) {
    for (int i=L;mid>=i;i++) {
        for (int j=0;SZ(pos[i])>j;j++) {
            int p=pos[i][j];
            bit.add(p,1);
        }
    }
}

void undo_things(int L,int mid) {
    for (int i=L;mid>=i;i++) {
        for (int j=0;SZ(pos[i])>j;j++) {
            int p=pos[i][j];
            bit.add(p,-1);
        }
    }
}

void split(int mid,vint &queries,vint &ok,vint &notok) {
    for (int i=0;SZ(queries)>i;i++) {
        int qid=queries[i];
        if (bit.query(qL[qid],qR[qid]) >= qK[qid]) {
            ok.PB(qid);
        }
        else {
            notok.PB(qid);
        }
    }
    vector<int> ().swap(queries);
}

void totBS(int L,int R,vint queries) {
    //cout<<"l = "<<L<<" , r = "<<R<<endl;
    if (L==R) {
        do_things(L,L);
        for (int i=0;SZ(queries)>i;i++) {
            int qid=queries[i];
            ans[qid] = L;
        }
        return;
    }
    int mid=(L+R)>>1;
    do_things(L,mid);
    vint ok,notok;
    split(mid,queries,ok,notok);
    undo_things(L,mid);
    totBS(L,mid,ok);
    totBS(mid+1,R,notok);
}

int main () {
    srand(time(NULL));
    Sii(n,q);
    REP1(i,n) {
        Si(a[i]);
        v.PB(a[i]);
    }
    sort(ALL(v));
    v.resize(unique(ALL(v))-v.begin());
    bit.init(SZ(v));
    REP1(i,n) {
        a[i] = lower_bound(ALL(v),a[i])-v.begin()+1;
        pos[ a[i] ].PB(i);
    }
    vint Q;
    REP1(i,q) {
        Siii(qL[i],qR[i],qK[i]);
        Q.PB(i);
    }
    MEM1(ans);
    totBS(1,SZ(v),Q);
    REP1(i,q) {
        Pi(v[ans[i]-1]);
    }
}

法四：整體二分 (用特殊技巧壓到 N lg N)

這份可能是因為vector用太多吧，跑起來比方法三的時間要多一倍><

模板略~

const int N = 1e5 + 6;

int a[N];
int qL[N],qR[N],qK[N];
int ans[N];

#define vpii vector<pii>

//( val_L , i )

LL sum[N];

void totBS(int L,int R,vint e,vpii vqL,vpii vqR) {
    //cout<<"L = "<<L<<" , R = "<<R<<" ,sze = "<<SZ(e)<<" , szvqL = "<<SZ(vqL)<<endl;
    if (L==R) {
        for (int i=0;SZ(vqL)>i;i++) {
            pii p=vqL[i];
            ans[p.S] = L;
        }
        return;
    }
    vint re,le;
    vpii rvqL,lvqL;
    vpii rvqR,lvqR;
    int mid = (L+R)>>1;
    int vqLid=0,vqRid = 0;
    int cnt=0;
    for (int i=0;SZ(e)>i;i++) {
        int ee=e[i];
        if (a[ee] <= mid) {
            le.PB(ee);
            while (vqLid < SZ(vqL) && qL[ vqL[vqLid].S ] <= ee) sum[ vqL[vqLid++].S ] -= cnt;
            while (vqRid < SZ(vqR) && qR[ vqR[vqRid].S ] <  ee) sum[ vqR[vqRid++].S ] += cnt;
            cnt++;
        }
        else {
            re.PB(ee);
        }
    }
    while (vqLid < SZ(vqL)) sum[ vqL[vqLid++].S ] -= cnt;
    while (vqRid < SZ(vqR)) sum[ vqR[vqRid++].S ] += cnt;
    for (int i=0;SZ(vqL) > i;i++) {
        pii ii=vqL[i];
        if (qK[ii.S] <= sum[ii.S]) {
            lvqL.PB(ii);
        }
        else {
            rvqL.PB(ii);
        }
    }
    for (int i=0;SZ(vqR) > i;i++) {
        pii ii=vqR[i];
        if (qK[ii.S] <= sum[ii.S]) {
            lvqR.PB(ii);
        }
        else {
            rvqR.PB(ii);
            qK[ii.S] -= sum[ii.S];
        }
        sum[ii.S] = 0;
    }
    vint ().swap(e);
    vpii ().swap(vqL);
    vpii ().swap(vqR);
    totBS(L,mid+0,le,lvqL,lvqR);
    totBS(mid+1,R,re,rvqL,rvqR);
}

int main () {
    srand(time(NULL));
    int n,m;
    Sii(n,m);
    vint v;
    REP1(i,n)
    {
        Si(a[i]);
        v.PB(a[i]);
    }
    sort(ALL(v));
    v.resize(unique(ALL(v))-v.begin());
    vint e;
    REP1(i,n)
    {
        a[i] = lower_bound(ALL(v),a[i])-v.begin();
        e.PB(i);
    }
    vpii vqL,vqR;
    REP1(i,m)
    {
        Siii(qL[i],qR[i],qK[i]);
        vqL.PB(MP(qL[i],i));
        vqR.PB(MP(qR[i],i));
    }
    sort(ALL(vqL));
    sort(ALL(vqR));
    totBS(0,SZ(v)-1,e,vqL,vqR);
    REP1(i,m)
    {
        Pi(v[ans[i]]);
    }
}