【BZOJ 3110】【ZJOI 2013】K大數查詢

2019-11-11 04:17:33

字體：大中小

來源：轉載

供稿：網友

BZOJ 3110 / ZJOI 2013

題意

有n個位置和m個操作，操作分兩種：輸入1 a b c：在a到b的所有位置加入一個數c；輸入2 a b c：詢問a到b每個位置上所有的數中的第c大數。注意每個位置可以有多個數。

樣例輸入

2 5 1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3

樣例輸出

1 2 1

SOL

首先是離散化，注意本題原始數據并沒有負數并且c的范圍很小（并非如題所說maxlongint）所以不用離散直接做就行，但是bzoj上加強了數據，需要離散化，并且有可能爆int。（極限情況每次在1到50000插入同一個數就會有2500000000個數）為了方便起見，我們對每個數取相反數并加上n，這樣就是求k小數了。這道題目有很多的做法，這里介紹一種樹套樹的方法，外層是數值線段樹，內層是區間線段樹。對于外層的數值線段樹，每個節點維護的是值為[l,r]的情況，而每個節點中的區間線段樹維護的是這些值在[1,n]區間中的分布情況。

時間復雜度分析

插入操作：每次修改外層數值線段樹上的log(n)個點，每個點中的線段樹就是用傳統線段樹的方法（區間合并+lazy-tag標記），平攤也是log(n)，所以每次插入操作時間復雜度為lognlogn。查詢操作：計算外層線段樹上左孩子代表的滿足條件的節點個數，也就是說計算對于左孩子所代表的線段樹中滿足要求區間的數的個數。如果大于c則說明在左子樹，反之則在右子樹。一共操作log(n)次，每次計算就是傳統線段樹的區間合并，平攤為log(n)，所以每次查詢操作時間復雜度也為lognlogn。

空間復雜度分析

有了主席樹的經驗，我們可以動態開節點。每次修改外層線段樹上的log(n)個點，每個點新開log(n)個點，所以空間復雜度為nlognlogn，和單點修改的主席樹一樣，不過這題顯然沒有惡心地去卡空間。

具體實現

更新

void update(int rt,int l,int r)//外層數值線段樹更新 { deep(root[rt],1,n); if (l == r) return; int mid = (l + r) >> 1; if (c <= mid) update(rt<<1,l,mid); else update(rt<<1|1,mid+1,r);}

不斷在線段樹上向下搜索，將符合條件的節點全部搜一遍。這里的deep函數表示在rt這個線段樹中修改，寫法如下：

void deep(int &rt,int l,int r)//內層區間線段樹更新{ if (rt == 0) rt = ++ tot; if (L <= l && r <= R) {tag[rt]++; sum[rt] += r - l + 1; return;} int mid = (l + r) >> 1; if (L <= mid) deep(ls[rt],l,mid); if (mid < R) deep(rs[rt],mid+1,r); sum[rt] = sum[ls[rt]] + sum[rs[rt]] + tag[rt] * (r - l + 1);}

這里用到了和主席樹一樣的寫法：地址回傳。然后就是和傳統線段樹一樣的區間和并和lazy-tag標記，這里的參數簡單到都不用另開一個pushdown函數下傳標記。

查詢

int query(int rt,int l,int r)//外層線段樹查詢 { if (l == r) return l; int mid = (l + r) >> 1; int cnt = Sum(root[rt<<1],1,n); if (c <= cnt) return query(rt<<1,l,mid); c = c - cnt; return query(rt<<1|1,mid+1,r); }

查詢同樣也是分為兩步，Sum函數求得就是左孩子代表的線段樹中滿足區間要求的數的個數，寫法如下：

int Sum(int rt,int l,int r)//內層線段樹計數 { if (rt == 0) return 0; if (L <= l && r <= R) return sum[rt]; int mid = (l + r) >> 1; int cnt = 0; if (L <= mid) cnt += Sum(ls[rt],l,mid); if (mid < R) cnt += Sum(rs[rt],mid+1,r); return cnt + tag[rt] * (min(R,r) - max(L,l) + 1);}