有n個(gè)位置和m個(gè)操作，操作分兩種： 輸入1 a b c：在a到b的所有位置加入一個(gè)數(shù)c； 輸入2 a b c：詢問a到b每個(gè)位置上所有的數(shù)中的第c大數(shù)。 注意每個(gè)位置可以有多個(gè)數(shù)。
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
首先是離散化，注意本題原始數(shù)據(jù)并沒有負(fù)數(shù)并且c的范圍很小（并非如題所說maxlongint）所以不用離散直接做就行，但是bzoj上加強(qiáng)了數(shù)據(jù)，需要離散化，并且有可能爆int。（極限情況每次在1到50000插入同一個(gè)數(shù)就會有2500000000個(gè)數(shù)） 為了方便起見，我們對每個(gè)數(shù)取相反數(shù)并加上n，這樣就是求k小數(shù)了。 這道題目有很多的做法，這里介紹一種樹套樹的方法，外層是數(shù)值線段樹，內(nèi)層是區(qū)間線段樹。 對于外層的數(shù)值線段樹，每個(gè)節(jié)點(diǎn)維護(hù)的是值為[l,r]的情況，而每個(gè)節(jié)點(diǎn)中的區(qū)間線段樹維護(hù)的是這些值在[1,n]區(qū)間中的分布情況。
插入操作：每次修改外層數(shù)值線段樹上的log(n)個(gè)點(diǎn)，每個(gè)點(diǎn)中的線段樹就是用傳統(tǒng)線段樹的方法（區(qū)間合并+lazy-tag標(biāo)記），平攤也是log(n)，所以每次插入操作時(shí)間復(fù)雜度為lognlogn。 查詢操作：計(jì)算外層線段樹上左孩子代表的滿足條件的節(jié)點(diǎn)個(gè)數(shù)，也就是說計(jì)算對于左孩子所代表的線段樹中滿足要求區(qū)間的數(shù)的個(gè)數(shù)。如果大于c則說明在左子樹，反之則在右子樹。一共操作log(n)次，每次計(jì)算就是傳統(tǒng)線段樹的區(qū)間合并，平攤為log(n)，所以每次查詢操作時(shí)間復(fù)雜度也為lognlogn。
有了主席樹的經(jīng)驗(yàn)，我們可以動態(tài)開節(jié)點(diǎn)。每次修改外層線段樹上的log(n)個(gè)點(diǎn)，每個(gè)點(diǎn)新開log(n)個(gè)點(diǎn)，所以空間復(fù)雜度為nlognlogn，和單點(diǎn)修改的主席樹一樣，不過這題顯然沒有惡心地去卡空間。
不斷在線段樹上向下搜索，將符合條件的節(jié)點(diǎn)全部搜一遍。這里的deep函數(shù)表示在rt這個(gè)線段樹中修改，寫法如下：
void deep(int &rt,int l,int r)//內(nèi)層區(qū)間線段樹更新{ 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);}這里用到了和主席樹一樣的寫法：地址回傳。然后就是和傳統(tǒng)線段樹一樣的區(qū)間和并和lazy-tag標(biāo)記，這里的參數(shù)簡單到都不用另開一個(gè)pushdown函數(shù)下傳標(biāo)記。
查詢同樣也是分為兩步，Sum函數(shù)求得就是左孩子代表的線段樹中滿足區(qū)間要求的數(shù)的個(gè)數(shù)，寫法如下：
int Sum(int rt,int l,int r)//內(nèi)層線段樹計(jì)數(shù) { 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);}新聞熱點(diǎn)
疑難解答
