ZOJ - 2112 Dynamic Rankings（BIT套主席树）

纠结了好久的一道题，以前是用线段树套平衡树二分做的，感觉时间复杂度和分块差不多了。。。

终于用BIT套函数式线段树了过了，120ms就是快，此题主要是卡内存。

假设离散后有ns个不同的值，递归层数是log2(ns)左右，nlog(ns)，主席树是前缀区间，BIT保存修改的值是mlog2(ns)log2(ns)。

虽然这个算出来还是会爆，但是实际上会有一些结点复用，具体设置多少请相信玄学。（2e6左右）

ZOJ的Node*计算内存似乎有问题，必须用int

/*********************************************************

*            ------------------                          *

*   author AbyssFish                                     *

**********************************************************/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

#include<cmath>

using namespace std;

//#pragma pack(4)

const int MAX_N = 5e4+;

const int MAX_M = 1e4+;

const int MAX_NM = MAX_N+MAX_M;

const int MAX_D = ;

const int MAX_ND = 0xac*MAX_M+0x42fed;//MAX_D*MAX_N+MAX_M*MAX_D*MAX_D;

int b[MAX_NM];

int mp_a[MAX_NM];

int ns, n_;

int N, M;

struct Cmd

{

    int i, j, k;

}qus[MAX_M];

struct Node

{

    int lc, rc;

    int s;

}p[MAX_ND];

int root[MAX_N];

int cnt;

#define lsn p[o].lc,l,md

#define rsn p[o].rc,md+1,r

void build(int x,int &o,int l = , int r = ns)

{

    p[++cnt] = p[o];

    o = cnt;

    p[o].s++;

    if(r > l){

        int md = (l+r)>>;

        if(x <= md) build(x,lsn);

        else build(x,rsn);

    }

}

int BIT[MAX_N];

void inst(int x, int d, int &o, int l = , int r = ns)

{

    if(o == ){

        p[++cnt] = p[o];

        o = cnt;

    }

    p[o].s += d;

    if(l < r){

        int md = (l+r)>>;

        if(x<=md) inst(x,d,lsn);

        else inst(x,d,rsn);

    }

}

#define lowbit(x) ((x)&(-x))

void modify_bit(int pos, int x, int d)

{

    while(pos <= N){

        inst(x,d,BIT[pos]);

        pos += lowbit(pos);

    }

}

typedef vector<int> Prefix;

void prefix_bit(int pos, Prefix &res)

{

    res.clear();

    while(pos > ){

        res.push_back(BIT[pos]);

        pos -= lowbit(pos);

    }

}

inline int cal_lft(Prefix &pfx)

{

    int re = ;

    for(int i = pfx.size()-; i >= ; i--){

        re += p[p[pfx[i]].lc].s;

    }

    return re;

}

#define dump(pfx,ch)\

for(i = pfx.size()-; i >= ; i--){\

    pfx[i] = p[pfx[i]].ch;\

}

Prefix X, Y;

int qkth(int k,int l = , int r = ns)

{

    if(l == r) return mp_a[l];

    else {

        int l_cnt = cal_lft(Y)-cal_lft(X);

        int md = (l+r)>>, i;

        if(k <= l_cnt){

            dump(X,lc)

            dump(Y,lc)

            return qkth(k,l,md);

        }

        else {

            dump(X,rc)

            dump(Y,rc)

            return qkth(k-l_cnt,md+,r);

        }

    }

}

void solve()

{

    cnt = ;

    memset(BIT+,,sizeof(int)*N);

    int i;

    for(i = ; i <= N; i++){

        root[i] = root[i-];

        build(b[i], root[i]);

    }

    for(i = ; i < M; i++){

        if(qus[i].j < ){

            int pos = qus[i].i;

            modify_bit(pos,b[pos],-);

            modify_bit(pos,b[pos] = b[qus[i].k],);

        }

        else {

            int L = qus[i].i-, R = qus[i].j;

            prefix_bit(L,X);

            prefix_bit(R,Y);

            X.push_back(root[L]);

            Y.push_back(root[R]);

            printf("%d\n",qkth(qus[i].k));

        }

    }

}

int * const a = (int *)(p+);

int * const r = a + MAX_NM;

void init()

{

    scanf("%d%d",&N,&M);

    for(int i = ; i <= N; i++){

        scanf("%d",a+i);

        r[i] = i;

    }

    n_ = N;

    char ch[];

    for(int i = ; i < M; i++){

        scanf("%s",ch);

        if(*ch == 'Q') {

            scanf("%d%d%d",&qus[i].i,&qus[i].j,&qus[i].k);

        }

        else {

            qus[i].k = ++n_;

            r[n_] = n_;

            scanf("%d%d",&qus[i].i,a+n_);

            qus[i].j = -;

        }

    }

    sort(r+,r+n_+,[](int i,int j){ return a[i]<a[j]; });

    mp_a[b[r[]] = ns = ] = a[r[]];

    for(int i = ; i <= n_; i++) {

        int k = r[i];

        if(a[k] != a[r[i-]]){

            mp_a[b[k] = ++ns] = a[k];

        }

        else {

            b[k] = ns;

        }

    }

}

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    //cout<<ceil(log2(MAX_N+MAX_M))+1;

    //cout<<sizeof(Node*)<<endl;

    //cout<<MAX_ND<<endl;

   // cout<<MAX_ND*sizeof(Node)+(MAX_NM)*16+MAX_M*12+MAX_N*8;

   // cout<<sizeof(a)+sizeof(root)+sizeof(meo)+sizeof(qus)+sizeof(BIT)<<endl;//sizeof(b)+sizeof(mp_a)+sizeof(r)

    p[] = {,,};

    X.reserve(MAX_D+);

    Y.reserve(MAX_D+);

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

    while(T--){

        init();

        solve();

    }

    return ;

}

巴特西

ZOJ - 2112 Dynamic Rankings（BIT套主席树）

最新文章

热门文章