[POI 21st Stage 1][Persistent Segment Tree] Couriers

原題連結
有做過第k小的同學大概對於持久化權值線段樹稍微有點感受

我們就有如在做第k小一般去維護一棵持久化線段樹，每個線段樹節點維護size域，就是這個值域範圍內共有幾個數字。那麼，對於區間[L,R]的查詢就可以藉由root[R]和root[L-1]的同時走訪去實現。

假設我們要問某個數字是否有嚴格出現超過一半，那麼，只要查看自己左兒子和右兒子哪個的size有嚴格超過一半就好，因為一定只有一個兒子的size會超過一半(除非你寫錯了......)，所以永遠都只有一條路可以走。如果發現不管選哪個都不會超過一半，代表不存在我們要找的數字。

這題還有另外一種相當精妙的作法，可以參考這篇

陣列版code:

#include<cstdio>
using namespace std;
const int maxn=500000+5;
int nodecnt=0,root[maxn],size[maxn*20],lc[maxn*20],rc[maxn*20];
int newnode(int t)
{
    nodecnt++;
    size[nodecnt]=size[t];
    lc[nodecnt]=lc[t];
    rc[nodecnt]=rc[t];
    return nodecnt;
}
void modify(int last,int& now,int L,int R,int mx,int mv)
{
    now=newnode(last);
    if(L==R) {size[now]+=mv;return;}
    int M=L+(R-L)/2;
    if(mx<=M) modify(lc[last],lc[now],L,M,mx,mv);
    else modify(rc[last],rc[now],M+1,R,mx,mv);
    size[now]=size[lc[now]]+size[rc[now]];
}
int query(int tl,int tr,int L,int R,int tar)
{
    if(L==R) return L;
    int M=L+(R-L)/2,lsize=size[lc[tr]]-size[lc[tl]],rsize=size[rc[tr]]-size[rc[tl]];
    if(lsize>=tar) return query(lc[tl],lc[tr],L,M,tar);
    else if(rsize>=tar) return query(rc[tl],rc[tr],M+1,R,tar);
    return 0;
}
int main()
{
    nodecnt=0;
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        modify(root[i-1],root[i],1,maxn,x,1);
    }
    for(int i=0,L,R;i<m;i++)
    {
        scanf("%d%d",&L,&R);
        printf("%d\n",query(root[L-1],root[R],1,maxn,(R-L+1)/2+1));
    }
}

指標版code:

#include<cstdio>
#include<new>
using namespace std;
const int maxn=500000+5;
const int maxnode=10000000+5;
struct Node
{
    static Node mem[maxnode];
    Node *lc,*rc;
    int size;
    void pull() {size=(lc?lc->size:0)+(rc?rc->size:0);}
    Node() {size=0;lc=rc=NULL;}
}*root[maxn],Node::mem[maxnode],*pmem=Node::mem;
void modify(Node* last,Node*& now,int L,int R,int mx,int mv)
{
    if(last) now=new (pmem++) Node(*last);
    else now=new (pmem++) Node();

    if(L==R) {now->size+=mv;return;}
    int M=L+(R-L)/2;
    if(mx<=M) modify(last?last->lc:0,now->lc,L,M,mx,mv);
    else modify(last?last->rc:0,now->rc,M+1,R,mx,mv);
    now->pull();
}
int query(Node* tl,Node* tr,int L,int R,int tar)
{
    if(L==R) return L;
    int lsize=(tr && tr->lc?tr->lc->size:0)-(tl && tl->lc?tl->lc->size:0),
    rsize=(tr && tr->rc?tr->rc->size:0)-(tl && tl->rc?tl->rc->size:0),M=L+(R-L)/2;
    if(lsize>=tar) return query(tl?tl->lc:0,tr?tr->lc:0,L,M,tar);
    else if(rsize>=tar) return query(tl?tl->rc:0,tr?tr->rc:0,M+1,R,tar);
    return 0;
}
int main()
{
    pmem=Node::mem;
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        modify(root[i-1],root[i],1,maxn,x,1);
    }
    for(int i=0,L,R;i<m;i++)
    {
        scanf("%d%d",&L,&R);
        printf("%d\n",query(root[L-1],root[R],1,maxn,(R-L+1)/2+1));
    }
}