BZOJ 3110 / ZJOI 2013
題意
有n個(gè)位置和m個(gè)操作，操作分兩種： 輸入1 a b c：在a到b的所有位置加入一個(gè)數(shù)c； 輸入2 a b c：詢問(wèn)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
SOL
首先是離散化，注意本題原始數(shù)據(jù)并沒(méi)有負(fù)數(shù)并且c的范圍很小（并非如題所說(shuō)maxlongint）所以不用離散直接做就行，但是bzoj上加強(qiáng)了數(shù)據(jù)，需要離散化，并且有可能爆int。（極限情況每次在1到50000插入同一個(gè)數(shù)就會(huì)有2500000000個(gè)數(shù)） 為了方便起見(jiàn)，我們對(duì)每個(gè)數(shù)取相反數(shù)并加上n，這樣就是求k小數(shù)了。 這道題目有很多的做法，這里介紹一種樹(shù)套樹(shù)的方法，外層是數(shù)值線段樹(shù)，內(nèi)層是區(qū)間線段樹(shù)。 對(duì)于外層的數(shù)值線段樹(shù)，每個(gè)節(jié)點(diǎn)維護(hù)的是值為[l,r]的情況，而每個(gè)節(jié)點(diǎn)中的區(qū)間線段樹(shù)維護(hù)的是這些值在[1,n]區(qū)間中的分布情況。
時(shí)間復(fù)雜度分析
插入操作：每次修改外層數(shù)值線段樹(shù)上的log(n)個(gè)點(diǎn)，每個(gè)點(diǎn)中的線段樹(shù)就是用傳統(tǒng)線段樹(shù)的方法（區(qū)間合并+lazy-tag標(biāo)記），平攤也是log(n)，所以每次插入操作時(shí)間復(fù)雜度為lognlogn。 查詢操作：計(jì)算外層線段樹(shù)上左孩子代表的滿足條件的節(jié)點(diǎn)個(gè)數(shù)，也就是說(shuō)計(jì)算對(duì)于左孩子所代表的線段樹(shù)中滿足要求區(qū)間的數(shù)的個(gè)數(shù)。如果大于c則說(shuō)明在左子樹(shù)，反之則在右子樹(shù)。一共操作log(n)次，每次計(jì)算就是傳統(tǒng)線段樹(shù)的區(qū)間合并，平攤為log(n)，所以每次查詢操作時(shí)間復(fù)雜度也為lognlogn。
空間復(fù)雜度分析
有了主席樹(shù)的經(jīng)驗(yàn)，我們可以動(dòng)態(tài)開(kāi)節(jié)點(diǎn)。每次修改外層線段樹(shù)上的log(n)個(gè)點(diǎn)，每個(gè)點(diǎn)新開(kāi)log(n)個(gè)點(diǎn)，所以空間復(fù)雜度為nlognlogn，和單點(diǎn)修改的主席樹(shù)一樣，不過(guò)這題顯然沒(méi)有惡心地去卡空間。
具體實(shí)現(xiàn)
更新
void update(int rt,int l,int r)//外層數(shù)值線段樹(shù)更新 { 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);}不斷在線段樹(shù)上向下搜索，將符合條件的節(jié)點(diǎn)全部搜一遍。這里的deep函數(shù)表示在rt這個(gè)線段樹(shù)中修改，寫法如下：
void deep(int &rt,int l,int r)//內(nèi)層區(qū)間線段樹(shù)更新{ 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);}這里用到了和主席樹(shù)一樣的寫法：地址回傳。然后就是和傳統(tǒng)線段樹(shù)一樣的區(qū)間和并和lazy-tag標(biāo)記，這里的參數(shù)簡(jiǎn)單到都不用另開(kāi)一個(gè)pushdown函數(shù)下傳標(biāo)記。
查詢
int query(int rt,int l,int r)//外層線段樹(shù)查詢 { 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函數(shù)求得就是左孩子代表的線段樹(shù)中滿足區(qū)間要求的數(shù)的個(gè)數(shù)，寫法如下：
int Sum(int rt,int l,int r)//內(nèi)層線段樹(shù)計(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);}完整代碼
#include<cmath>#include<cstdio>#include<vector>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 1000000000#define mod 1000000007#define N 51000using namespace std;int n,m,op,L,R,c,tot;int sum[N*400],tag[N*400],ls[N*400],rs[N*400],root[N*4];void deep(int &rt,int l,int r)//內(nèi)層區(qū)間線段樹(shù)更新{ 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);}void update(int rt,int l,int r)//外層數(shù)值線段樹(shù)更新 { 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);}int Sum(int rt,int l,int r)//內(nèi)層線段樹(shù)計(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);}int query(int rt,int l,int r)//外層線段樹(shù)查詢 { 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); }int main(){ scanf("%d%d",&n,&m); while (m--) { scanf("%d%d%d%d",&op,&L,&R,&c); if (op == 1) {c = n - c + 1; update(1,1,n);} else 加上離散化的代碼#include<cmath>#include<cstdio>#include<vector>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define inf 1000000000#define mod 1000000007#define N 51000#define lll long longusing namespace std;int i,n,m,op[N],L[N],R[N],tot,LL,RR,t;lll cc,b[N],c[N];int ls[N*400],rs[N*400],root[N*4];lll sum[N*400],tag[N*400];void deep(int &rt,int l,int r)//內(nèi)層區(qū)間線段樹(shù)更新{ if (rt == 0) rt = ++ tot; if (LL <= l && r <= RR) {tag[rt]++; sum[rt] += r - l + 1; return;} int mid = (l + r) >> 1; if (LL <= mid) deep(ls[rt],l,mid); if (mid < RR) deep(rs[rt],mid+1,r); sum[rt] = sum[ls[rt]] + sum[rs[rt]] + tag[rt] * (r - l + 1);}void update(int rt,int l,int r)//外層數(shù)值線段樹(shù)更新 { deep(root[rt],1,n); if (l == r) return; int mid = (l + r) >> 1; if (cc <= mid) update(rt<<1,l,mid); else update(rt<<1|1,mid+1,r);}lll Sum(int rt,int l,int r)//內(nèi)層線段樹(shù)計(jì)數(shù) { if (rt == 0) return 0; if (LL <= l && r <= RR) return sum[rt]; int mid = (l + r) >> 1; int cnt = 0; if (LL <= mid) cnt += Sum(ls[rt],l,mid); if (mid < RR) cnt += Sum(rs[rt],mid+1,r); return cnt + tag[rt] * (min(RR,r) - max(LL,l) + 1);}int query(int rt,int l,int r)//外層線段樹(shù)查詢 { if (l == r) return l; int mid = (l + r) >> 1; lll cnt = Sum(root[rt<<1],1,n); if (cc <= cnt) return query(rt<<1,l,mid); cc = cc - cnt; return query(rt<<1|1,mid+1,r); }int find(lll x){return lower_bound(b+1,b+t+1,x)-b;}int main(){ scanf("%d%d",&n,&m); for (i = 1;i <= m; i++) scanf("%d%d%d%lld",&op[i],&L[i],&R[i],&c[i]); for (i = 1;i <= m; i++) if (op[i] == 1) b[++t] = c[i]; sort(b+1,b+t+1); t = unique(b+1,b+t+1) - (b+1); for (i = 1;i <= m; i++) { LL = L[i]; RR = R[i]; cc = c[i]; if (op[i] == 1) {cc = n - find(cc) + 1; update(1,1,n);} else printf("%d/n",b[n - query(1,1,n) + 1]); } return 0;}
