程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> ZOJ 2112 Dynamic Rankings（線段樹樹套平衡樹）

ZOJ 2112 Dynamic Rankings（線段樹樹套平衡樹）

編輯：關於C++

題意就是求區間第k大，不過有修改。

其實這題解法挺多，主席樹套BIT的我之後再寫，這次寫了線段樹套平衡樹的2種解法，第一種是按權值建線段樹套treap，treap裡放的是數的位置，這種方法必須要離線，因為需要把修改的值也一起建樹，第二種則是在線的，按區間建線段樹套treap，treap裡放的是數的大小。第一種建樹復雜度是o(log^2n)，詢問復雜度是o(log^2n)。修改復雜度o(log^2n)，第二種則差一些，建樹復雜度是o(log^2n)，詢問復雜度是o(log^3n)，修改復雜度o(log^2n)。

先說第一種，每一個線段樹的節點是那個節點所含treap的根節點，然後查詢的時候，左子樹的含有[L,R]的點如果大於等於k，那麼就到左子樹去查，反之就把K-左子樹[L,R]的點，到右子樹查。一直走到根節點就查到了。修改的時候先刪掉線段樹中原來那個點的值，再插入。

第二種，第二種按照區間建樹，建樹的時候做法基本跟第一種是一樣的。但是要注意有相同數字的問題，導致了treap裡面那個cmp函數有些地方不能用。查詢的時候就有個問題了，肯定是二分最大值也就是10^9，但是有重復值的問題，這樣就導致小於答案的不一定是k-1個，這個問題我是用查詢小於m，以及小於等於m的值來解決的。假設小於m的數有x個，小於等於m的數有y個，x <= k-1 && y>=k

才說明這個值是這個區間裡數且滿足題意。如果不滿足x <= k-1，所以就往小的找，如果不滿足y>=k就往大的找。

按權值建樹：(660ms)

#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#includewww.2cto.com
using namespace std;
#define ll long long
#define ull unsigned long long
#define eps 1e-8
#define NMAX 201000
#define MOD 1000000
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define PI acos(-1)
template
inline void scan_d(T &ret)
{
    char c;
    int flag = 0;
    ret=0;
    while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c == '-')
    {
        flag = 1;
        c = getchar();
    }
    while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
    if(flag) ret = -ret;
}
const int maxn = 60000+10;
const int maxm = 10000+10;
struct Node
{
    Node* ch[2];
    int r,v,s;
    int cmp(int x)
    {
        if(x == v) return -1;
        return x < v ? 0 : 1;
    }
    void maintain()
    {
        s = 1;
        s += ch[0]->s + ch[1]->s;
    }
}treap[maxn*15];
int nodecnt;
Node *null = &treap[0];

void node_init(Node* &o, int v)
{
    o->ch[0] = o->ch[1] = null;
    o->r = rand();
    o->v = v;
    o->s = 1;
}

Node* newnode()
{
    Node *p = &treap[nodecnt++];
    return p;
}

void rotate(Node* &o, int d)
{
    Node *k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;
    o->maintain(); k->maintain(); o = k;
}

void insert(Node* &o, int k)
{
    if(o == null)
    {
        o = newnode();
        node_init(o,k);
    }
    else
    {
        int d = o->cmp(k);//無相同節點可以用
        insert(o->ch[d],k);
        if(o->r < o->ch[d]->r) rotate(o,d^1);
    }
    o->maintain();
}

void remove(Node* &o, int k)
{
    int d = o->cmp(k);
    if(d == -1)
    {
        if(o->ch[0] != null && o->ch[1] != null)
        {
            int d2 = o->ch[0]->r > o->ch[1]->r ? 1 : 0;
            rotate(o,d2);
            remove(o->ch[d2],k);
        }
        else
        {
            if(o->ch[0] != null) o = o->ch[0];
            else o = o->ch[1];
        }
    }
    else remove(o->ch[d],k);
    if(o != null) o->maintain();//別忘了if null
}

int querytree(Node* &o, int l)//>=l有幾個
{
    if(o == null) return 0;
    if(o->v >= l) return o->ch[1]->s+1+querytree(o->ch[0],l);
    return querytree(o->ch[1],l);
}

int a[maxn],b[maxn];

Node* T[maxn<<2];

struct Query
{
    char flag;
    int l,r,k;
}que[maxm];

void build(int l, int r, int rt)
{
    T[rt] = null;
    if(l == r) return;
    int mid = (l+r)>>1;
    build(lson);
    build(rson);
}

void insertit(int L, int k, int l, int r, int rt)
{
    insert(T[rt],k);
    if(l == r) return;
    int mid = (l+r)>>1;
    if(L <= mid) insertit(L, k, lson);
    else insertit(L, k, rson);
}

int query(int L, int R, int k, int l, int r, int rt)
{
    if(l == r) return l;
    int mid = (l+r)>>1;
    if(T[rt<<1] != null)
    {
        int num = querytree(T[rt<<1],L)-querytree(T[rt<<1],R+1);
        if(num >= k) return query(L, R, k, lson);
        else return query(L, R, k-num, rson);
    }
    else return query(L, R, k, rson);
}

void removeit(int L, int k, int l, int r, int rt)
{
    remove(T[rt], k);
    if(l == r) return;
    int mid = (l+r)>>1;
    if(L <= mid) removeit(L, k, lson);
    else removeit(L, k, rson);
}

void dfs(Node* &o)
{
    if(o == null) return;
    dfs(o->ch[0]);
    printf("%d ",o->v);
    dfs(o->ch[1]);
}

int main()
{
#ifdef GLQ
    freopen("input.txt","r",stdin);
//    freopen("o.txt","w",stdout);
#endif
    srand(time(NULL));
    null->s = 0;
    int n,m,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        nodecnt = 1;
        int cnt = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            b[cnt++] = a[i];
        }
        for(int i = 0; i < m; i++)
        {
            char tmp[5];
            int l,r,k;
            scanf("%s",tmp);
            if(tmp[0] == 'Q')
            {
                que[i].flag = tmp[0];
                scanf("%d%d%d",&que[i].l,&que[i].r,&que[i].k);
            }
            else
            {
                que[i].flag = tmp[0];
                scanf("%d%d",&que[i].l,&que[i].k);
                b[cnt++] = que[i].k;
            }
        }
        sort(b,b+cnt);
        int nct = unique(b,b+cnt)-b;
        build(1,nct,1);
        for(int i = 1; i <= n; i++)
        {
            int tmp = lower_bound(b,b+nct,a[i])-b+1;

            insertit(tmp,i,1,nct,1);
        }
        for(int i = 0; i < m; i++)
        {
            if(que[i].flag == 'Q')
                printf("%d\n",b[query(que[i].l,que[i].r,que[i].k,1,nct,1)-1]);
            else
            {
                int pos1 = lower_bound(b,b+nct,a[que[i].l])-b+1,pos2 = lower_bound(b,b+nct,que[i].k)-b+1;
                removeit(pos1,que[i].l,1,nct,1);
                insertit(pos2,que[i].l,1,nct,1);
                a[que[i].l] = que[i].k;
            }
        }
    }
    return 0;
}

按區間建樹(1.9s)

#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define ull unsigned long long
#define eps 1e-8
#define NMAX 201000
#define MOD 1000000
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define PI acos(-1)
template
inline void scan_d(T &ret)
{
    char c;
    int flag = 0;
    ret=0;
    while(((c=getchar())<'0'||c>'9')&&c!='-');
    if(c == '-')
    {
        flag = 1;
        c = getchar();
    }
    while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
    if(flag) ret = -ret;
}
const int maxn = 50000+10;
const int maxm = 10000+10;
struct Node
{
    Node* ch[2];
    int r,v,s;
    int cmp(int x)
    {
        if(x == v) return -1;
        return x < v ? 0 : 1;
    }
    void maintain()
    {
        s = ch[0]->s+ch[1]->s+1;
    }
}treap[maxn*18];
int nodecnt;
Node* null = &treap[0];

Node* newnode()
{
    Node* p = &treap[nodecnt++];
    return p;
}

void nodeinit(Node* &o, int v)
{
    o->r = rand();
    o->s = 1;
    o->v = v;
    o->ch[0] = o->ch[1] = null;
}

void rotate(Node* &o, int d)
{
    Node* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;
    o->maintain(); k->maintain(); o = k;
}

void insert(Node* &o, int v)
{
    if(o == null)
    {
        o = newnode();
        nodeinit(o,v);
        return;
    }
    int d = v < o->v ? 0 : 1;//有重復值
    insert(o->ch[d],v);
    if(o->ch[d]->r > o->r) rotate(o,d^1);
    o->maintain();
}

void remove(Node* &o, int v)
{
    int d = o->cmp(v);
    if(d == -1)
    {
        if(o->ch[0] != null && o->ch[1] != null)
        {
            int d2 = o->ch[0]->r > o->ch[1]->r ? 1 : 0;
            rotate(o,d2);
            remove(o->ch[d2],v);
        }
        else
        {
            if(o->ch[0] != null) o = o->ch[0];
            else o = o->ch[1];
        }
    }
    else remove(o->ch[d],v);
    if(o != null) o->maintain();
}

int query1(Node* &o, int k)//v < k) return o->ch[0]->s+1+query1(o->ch[1],k);
    return query1(o->ch[0],k);
}

int query2(Node* &o, int k)//<=k有幾個
{
    if(o == null) return 0;
    if(o->v <= k) return o->ch[0]->s+1+query2(o->ch[1],k);
    return query2(o->ch[0],k);
}

Node* T[maxn<<2];
int a[maxn],n;

void build(int l, int r, int rt)
{
    T[rt] = null;
    if(l == r) return;
    int mid = (l+r)>>1;
    build(lson);
    build(rson);
}

void insertit(int L, int k, int l, int r, int rt)
{
    insert(T[rt],k);
    if(l == r) return;
    int mid = (l+r)>>1;
    if(L <= mid) insertit(L, k, lson);
    else insertit(L, k, rson);
}

int querytree(int L, int R, int k, int flag, int l, int r, int rt)
{
    if(L <= l && R >= r)
    {
        if(flag == 1) return query1(T[rt],k);
        else return query2(T[rt],k);
    }
    int mid = (l+r)>>1,ans = 0;
    if(L <= mid) ans += querytree(L,R,k,flag,lson);
    if(R > mid) ans += querytree(L,R,k,flag,rson);
    return ans;
}

int query(int L, int R, int k)
{
    int x = 0,y = 1000000000;
    while(x <= y)
    {
        int m = (x+y) >> 1;
        int p1 = querytree(L,R,m,1,1,n,1),p2 = querytree(L,R,m,2,1,n,1);
        if(p1 <= k-1)
        {
            if(p2 >= k) return m;
            else x = m+1;
        }
        else y = m-1;
    }
}

void removeit(int L, int k, int l, int r, int rt)
{
    remove(T[rt],k);
    if(l == r) return;
    int mid = (l+r) >> 1;
    if(L <= mid) removeit(L,k,lson);
    else removeit(L,k,rson);
}

int main()
{
#ifdef GLQ
    freopen("input.txt","r",stdin);
//    freopen("o.txt","w",stdout);
#endif
    srand(time(NULL));
    null->s = 0;
    int t,m;
    scanf("%d",&t);
    while(t--)
    {
        nodecnt = 1;
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
//            scan_d(a[i]);
        build(1,n,1);
        for(int i = 1; i <= n; i++)
            insertit(i,a[i],1,n,1);
        while(m--)
        {
            char tmp[2];
            scanf("%s",tmp);
            if(tmp[0] == 'Q')
            {
                int l,r,k;
                scanf("%d%d%d",&l,&r,&k);
//                scan_d(l); scan_d(r); scan_d(k);
                printf("%d\n",query(l,r,k));
            }
            else
            {
                int pos,k;
                scanf("%d%d",&pos,&k);
//                scan_d(pos); scan_d(k);
                removeit(pos,a[pos],1,n,1);
                insertit(pos,k,1,n,1);
                a[pos] = k;
            }
        }
    }
    return 0;
}