有做過第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)); } }
沒有留言:
張貼留言