POJ2104 k-th number

2019-11-08 18:22:42

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

題意：

詢問區(qū)間[L,R]間的第k大數(shù)

解：

主席樹

主席樹的大致思路是先將所有值離散化到[1,n]

然后對于每一個位置i建立一棵權(quán)值線段樹

維護位置[1,i]中的數(shù)字出現(xiàn)情況（例如:權(quán)值在[1,mid]范圍內(nèi)的數(shù)有x個）

但是這樣空間開銷太大，所以我們考慮每一棵線段樹每次建樹時相對于前面只改變了logn個點，其他點均未改變，所以我們可以直接連上這些未改變的點，新建改變后的結(jié)點，這樣，空間復(fù)雜度從n^2降為nlogn。

對于查詢區(qū)間[L,R],考察它的數(shù)字出現(xiàn)情況，發(fā)現(xiàn)其實就是[1,R]的數(shù)字出現(xiàn)情況-[1,L-1]的數(shù)字出現(xiàn)情況。在查詢過程中若[1,R]-[1,L-1]在[l,mid]（注意：mid不是(L+R)>>1而是當(dāng)前走到的權(quán)值范圍的中間）區(qū)間內(nèi)的數(shù)字出現(xiàn)次數(shù)小于k，那么遞歸下去，否則查詢[mid+1,r]的排名為k-([1,R]-[1,L-1])的數(shù)字。

代碼：

#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#define For(i,j,k) for(int i=(j);i<=(int)k;i++)#define Forr(i,j,k) for(int i=(j);i>=(int)k;i--)#define Set(a,b) memset(a,b,sizeof a))#define Rep(i,u) for(int i=Begin[u],v=to[i];i;i=Next[i],v=to[i])#define L(i) (T[i].s[0])#define R(i) (T[i].s[1])#define S(i) (T[i].sum)using namespace std;const int N=100010;inline void read(int &x){ x=0;char c=getchar();int f(0); while(c<'0'||c>'9')f|=(c=='-'),c=getchar(); while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar(); x=f?-x:x;}struct A{ int id,x; bool Operator <(const A b)const { return x<b.x; }};struct node{ int s[2],sum;};struct cht{ node T[N*20]; int rt[N],rk[N],cnt,n; A a[N]; #define mid (l+r>>1) inline void init(int num){ cnt=0,n=num; For(i,1,n)read(a[i].x),a[i].id=i; sort(a+1,a+n+1); For(i,1,n)rk[a[i].id]=i; For(i,1,n)insert(rk[i],rt[i]=rt[i-1],1,n); } inline void insert(int val,int &x,int l,int r){ T[++cnt]=T[x],x=cnt,++S(x); if(l==r)return ; if(val<=mid)insert(val,L(x),l,mid); else insert(val,R(x),mid+1,r); } inline int query(int l,int r,int k){ return a[query(rt[l-1],rt[r],1,n,k)].x; } inline int query(int u,int v,int l,int r,int k){ int sum=S(L(v))-S(L(u)); if(l==r)return l; if(k<=sum)return query(L(u),L(v),l,mid,k); else return query(R(u),R(v),mid+1,r,k-sum); }}t;int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF){ t.init(n); while(m--){ int u,v,k; read(u),read(v),read(k);