之前刷了一點主席樹的題目，但是沒有系統(tǒng)的做過權(quán)值線段樹的題目。主席樹是多根權(quán)值線段樹的綜合。權(quán)值線段樹可以解決在總區(qū)間里求第k大的問題。在普通的線段樹里，我們每一個節(jié)點維護的是權(quán)值大小。但是在權(quán)值線段樹里維護的是數(shù)字在數(shù)組中的相對的位置。所以權(quán)值線段樹經(jīng)常需要和離散化結(jié)合在一起。
昨天hdu多校一個權(quán)值線段樹的題目。
Find the answer
Time Limit: 4000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 4521 Accepted Submission(s): 508
Problem Description

Given a sequence of n integers called W and an integer m. For each i (1 <= i <= n), you can choose some elements Wk (1 <= k < i), and change them to zero to make ∑ij=1Wj<=m. So what’s the minimum number of chosen elements to meet the requirements above?.
Input
The first line contains an integer Q — the number of test cases.
For each test case:
The first line contains two integers n and m — n represents the number of elemens in sequence W and m is as described above.
The second line contains n integers, which means the sequence W.
1 <= Q <= 15
1 <= n <= 2*105
1 <= m <= 109
For each i, 1 <= Wi <= m
Output
For each test case, you should output n integers in one line: i-th integer means the minimum number of chosen elements Wk (1 <= k < i), and change them to zero to make ∑ij=1Wj<=m.
Sample Input
2
7 15
1 2 3 4 5 6 7
5 100
80 40 40 40 60

Sample Output
0 0 0 0 0 2 3
0 1 1 2 3
給定n個數(shù)和一個數(shù)字m，對于位置i，我們需要保證從1~i-1的數(shù)字和小于m，那么我們最少使前面多少個數(shù)字為0。一開始就是暴力主席樹，每次找最大的去刪除。一開始數(shù)組開小了，該返回re卻返回的是TLE。1e5的數(shù)據(jù)量我們最差也應(yīng)該是nlogn的時間復(fù)雜度。這時權(quán)值線段樹就派上用場了。
對于每一個位置的數(shù)字，我們找出在他之前小于等于m-a[i]的數(shù)字的個數(shù)，再用I-ans-1就是我們要知道的答案了。統(tǒng)計完答案之后，就在將這個數(shù)插入到線段樹中就好了。1e9的數(shù)據(jù)量，需要離散化。
代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #define ll long long using namespace std;const int maxx=2e5+100; struct node{int l;int r;ll sum;ll num; }p[maxx<<2]; ll a[maxx],b[maxx]; int n; ll m; int getid(ll x,int len) {return lower_bound(b+1,b+1+len,x)-b; } void pushup(int cur) {p[cur].sum=p[cur<<1].sum+p[cur<<1|1].sum;//sum代表的是前面幾個數(shù)字的和p[cur].num=p[cur<<1].num+p[cur<<1|1].num;//num代表的是數(shù)字出現(xiàn)的次數(shù) } void build(int l,int r,int cur) {p[cur].l=l;p[cur].r=r;p[cur].sum=p[cur].num=0;if(l==r) return ;int mid=(l+r)>>1;build(l,mid,cur<<1);build(mid+1,r,cur<<1|1);pushup(cur); } int query(ll ant,int cur) {if(p[cur].sum<=ant) return p[cur].num;//如果這個節(jié)點的權(quán)值和小于ant就直接返回數(shù)字個數(shù)就可以if(p[cur].l==p[cur].r) return min(ant/b[p[cur].l],p[cur].num);//如果到達了葉子節(jié)點，我們就去湊antif(ant<=p[cur<<1].sum) return query(ant,cur<<1);//如果小于左子樹的權(quán)值，就進入左子樹else return p[cur<<1].num+query(ant-p[cur<<1].sum,cur<<1|1);//大于左子樹，就加上左子樹的數(shù)字個數(shù)再加上右子樹符合題意的數(shù)字個數(shù) } void update(int pos,ll add,int cur) {int L=p[cur].l;int R=p[cur].r;if(L==R)//單點更新，到達葉子節(jié)點才更新{p[cur].sum+=add;p[cur].num++;return ;}int mid=(L+R)>>1;if(pos<=mid) update(pos,add,cur<<1);else update(pos,add,cur<<1|1);pushup(cur); } int main() {int t;scanf("%d",&t);while(t--){scanf("%d%lld",&n,&m);for(int i=1;i<=n;i++) {scanf("%lld",&a[i]);b[i]=a[i];}sort(b+1,b+1+n);int len=unique(b+1,b+1+n)-b-1;//排序后的離散化build(1,n,1);for(int i=1;i<=n;i++){int ans=query(m-a[i],1);printf("%d ",i-ans-1);update(getid(a[i],len),a[i],1);//統(tǒng)計完答案后就更新}printf("\n");}return 0; }

結(jié)束之后刷了刷權(quán)值線段樹的題目。orz
普通的平衡樹
您需要寫一種數(shù)據(jù)結(jié)構(gòu)（可參考題目標題），來維護一些數(shù)，其中需要提供以下操作：

插入x數(shù)

刪除x數(shù)(若有多個相同的數(shù)，因只刪除一個)

查詢x數(shù)的排名(若有多個相同的數(shù)，因輸出最小的排名)

查詢排名為x的數(shù)

求x的前驅(qū)(前驅(qū)定義為小于x，且最大的數(shù))

求x的后繼(后繼定義為大于x，且最小的數(shù))

Input
第一行為n，表示操作的個數(shù),下面n行每行有兩個數(shù)opt和x，opt表示操作的序號(1<=opt<=6)

Output
對于操作3,4,5,6每行輸出一個數(shù)，表示對應(yīng)答案

Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
Hint
1.n的數(shù)據(jù)范圍：n<=100000

2.每個數(shù)的數(shù)據(jù)范圍：[-2e9,2e9]
權(quán)值線段樹的題目貌似splay樹都能解決。但是不會splay樹。。
總共有6中操作。對于這個題目我們進行離線處理。
1.在那個數(shù)字的位置加一。
2.在那個數(shù)字的位置減一。
3.假設(shè)x在離散化后的數(shù)組中的位置是pos，我們統(tǒng)計出前pos-1有多少個數(shù)，再加一就好了
4.求第k大。。
5.前驅(qū)，假設(shè)x在離散化后的數(shù)組中的位置是pos，我們求出前pos-1的數(shù)目為num，去查詢排名第num的數(shù)字是什么就好了。
6.后驅(qū)，假設(shè)x在離散化后的數(shù)組中的位置是pos，我們求出前pos的數(shù)目為num，去查詢排名為num+1的數(shù)字是什么就好了。
代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<vector> #define ll long long using namespace std;const int maxx=1e5+100; struct N{int id;int v; }e[maxx]; struct node{int l;int r;int num; }p[maxx<<2]; int a[maxx],b[maxx]; int n,m;inline void pushup(int cur) {p[cur].num=p[cur<<1].num+p[cur<<1|1].num; } inline void build(int l,int r,int cur) {p[cur].l=l;p[cur].r=r;p[cur].num=0;if(l==r) return ;int mid=l+r>>1;build(l,mid,cur<<1);build(mid+1,r,cur<<1|1); } inline void update(int cur,int pos,int add) {int L=p[cur].l;int R=p[cur].r;if(L==R){p[cur].num+=add;return ;}int mid=L+R>>1;if(pos<=mid) update(cur<<1,pos,add);else update(cur<<1|1,pos,add);pushup(cur); } inline int query1(int l,int r,int cur) {if(l>r) return 0;if(p[cur].l>=l&&p[cur].r<=r) return p[cur].num;int mid=p[cur].l+p[cur].r>>1;if(r<=mid) return query1(l,r,cur<<1);if(l>mid) return query1(l,r,cur<<1|1);return query1(l,mid,cur<<1)+query1(mid+1,r,cur<<1|1); } //int query1(int l,int r,int cur){ // if(p[cur].l>=l&&p[cur].r<=r) return p[cur].num; // int mid=p[cur].l+p[cur].r>>1; // int ans=0; // if(l<=mid) ans+=query1(l,r,cur<<1); // if(r>mid) ans+=query1(l,r,cur<<1|1); // return ans; //} inline int query2(int pos,int cur) {int L=p[cur].l;int R=p[cur].r;if(L==R) return L;if(pos<=p[cur<<1].num) return query2(pos,cur<<1);else return query2(pos-p[cur<<1].num,cur<<1|1); } int main() {scanf("%d",&n);char op[2];int x,pos;int cnt=0;//build(1,maxx,1);for(int i=1;i<=n;i++){scanf("%d%d",&e[i].id,&e[i].v);if(e[i].id!=4) b[++cnt]=e[i].v;}sort(b+1,b+1+cnt);int len=unique(b+1,b+1+cnt)-b-1;build(1,len,1);for(int i=1;i<=n;i++){if(e[i].id==1) {pos=lower_bound(b+1,b+1+len,e[i].v)-b;update(1,pos,1);}else if(e[i].id==2) {pos=lower_bound(b+1,b+1+len,e[i].v)-b;update(1,pos,-1);}else if(e[i].id==3){pos=lower_bound(b+1,b+1+len,e[i].v)-b;printf("%d\n",query1(1,pos-1,1)+1);}else if(e[i].id==4) {printf("%d\n",b[query2(e[i].v,1)]);}else if(e[i].id==5){pos=lower_bound(b+1,b+1+len,e[i].v)-b;printf("%d\n",b[query2(query1(1,pos-1,1),1)]);}else if(e[i].id==6){pos=lower_bound(b+1,b+1+len,e[i].v)-b;printf("%d\n",b[query2(query1(1,pos,1)+1,1)]);}}return 0; } /*13 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598 3 81968 3 492737 3 106465*/

郁悶的出納員
OIER公司是一家大型專業(yè)化軟件公司，有著數(shù)以萬計的員工。作為一名出納員，我的任務(wù)之一便是統(tǒng)計每位員工的
工資。這本來是一份不錯的工作，但是令人郁悶的是，我們的老板反復(fù)無常，經(jīng)常調(diào)整員工的工資。如果他心情好
，就可能把每位員工的工資加上一個相同的量。反之，如果心情不好，就可能把他們的工資扣除一個相同的量。我
真不知道除了調(diào)工資他還做什么其它事情。工資的頻繁調(diào)整很讓員工反感，尤其是集體扣除工資的時候，一旦某位
員工發(fā)現(xiàn)自己的工資已經(jīng)低于了合同規(guī)定的工資下界，他就會立刻氣憤地離開公司，并且再也不會回來了。每位員
工的工資下界都是統(tǒng)一規(guī)定的。每當(dāng)一個人離開公司，我就要從電腦中把他的工資檔案刪去，同樣，每當(dāng)公司招聘
了一位新員工，我就得為他新建一個工資檔案。老板經(jīng)常到我這邊來詢問工資情況，他并不問具體某位員工的工資
情況，而是問現(xiàn)在工資第k多的員工拿多少工資。每當(dāng)這時，我就不得不對數(shù)萬個員工進行一次漫長的排序，然后
告訴他答案。好了，現(xiàn)在你已經(jīng)對我的工作了解不少了。正如你猜的那樣，我想請你編一個工資統(tǒng)計程序。怎么樣
，不是很困難吧？
Input
第一行有兩個非負整數(shù)n和min。n表示下面有多少條命令，min表示工資下界。
接下來的n行，每行表示一條命令。命令可以是以下四種之一：
名稱 格式 作用
I命令 I_k 新建一個工資檔案，初始工資為k。
如果某員工的初始工資低于工資下界，他將立刻離開公司。
A命令 A_k 把每位員工的工資加上k
S命令 S_k 把每位員工的工資扣除k
F命令 F_k 查詢第k多的工資
_（下劃線）表示一個空格，I命令、A命令、S命令中的k是一個非負整數(shù)，F命令中的k是一個正整數(shù)。
在初始時，可以認為公司里一個員工也沒有。
I命令的條數(shù)不超過100000
A命令和S命令的總條數(shù)不超過100
F命令的條數(shù)不超過100000
每次工資調(diào)整的調(diào)整量不超過1000
新員工的工資不超過100000
Output
輸出行數(shù)為F命令的條數(shù)加一。
對于每條F命令，你的程序要輸出一行，僅包含一個整數(shù)，為當(dāng)前工資第k多的員工所拿的工資數(shù)，
如果k大于目前員工的數(shù)目，則輸出-1。
輸出文件的最后一行包含一個整數(shù)，為離開公司的員工的總數(shù)。
Sample Input
9 10
I 60
I 70
S 50
F 2
I 30
S 15
A 5
F 1
F 2
Sample Output
10
20
-1
2
代碼如下：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #define ll long long using namespace std;const int base=200020; const int maxx=400040; int add,sum; int n,m;struct node{int l;int r;int num;int lazy; }p[maxx<<2];void pushup(int cur) {p[cur].num=p[cur<<1].num+p[cur<<1|1].num; } void pushdown(int cur) {if(p[cur].lazy){p[cur<<1].num=p[cur<<1|1].num=0;p[cur<<1].lazy=p[cur<<1|1].lazy=1;p[cur].lazy=0;} } void build(int l,int r,int cur) {p[cur].l=l;p[cur].r=r;p[cur].num=p[cur].lazy=0;if(l==r) return ;int mid=l+r>>1;build(l,mid,cur<<1);build(mid+1,r,cur<<1|1); } void insert(int cur,int add) {int L=p[cur].l;int R=p[cur].r;if(L==R) {p[cur].num++;return ;}pushdown(cur);int mid=L+R>>1;if(add<=mid) insert(cur<<1,add);else insert(cur<<1|1,add);pushup(cur); } void update(int cur,int add) {int L=p[cur].l;int R=p[cur].r;if(L==R){if(p[cur].l<add) p[cur].num=0;return ;}if(p[cur].r<add){p[cur].num=0;p[cur].lazy=1;return ;}pushdown(cur);int mid=(L+R)>>1;if(add<=mid) update(cur<<1,add);else update(cur<<1,add),update(cur<<1|1,add);pushup(cur); } int query(int cur,int k) {if(p[cur].l==p[cur].r) return p[cur].l;int L=p[cur].l;int R=p[cur].r;pushdown(cur);if(k<=p[cur<<1].num) return query(cur<<1,k);else return query(cur<<1|1,k-p[cur<<1].num);pushup(cur); } int main() {scanf("%d%d",&n,&m);build(1,maxx,1);char op[2];int x;sum=add=0;while(n--){scanf("%s%d",op,&x);if(op[0]=='I'){if(x<m) continue;sum++;insert(1,x-add+base);}else if(op[0]=='A') add+=x;else if(op[0]=='S'){add-=x;update(1,m-add+base);}else if(op[0]=='F'){if(p[1].num<x) puts("-1");else printf("%d\n",query(1,p[1].num-x+1)+add-base);}}printf("%d\n",sum-p[1].num); }

路漫漫其修遠兮，努力加油a啊(^o)/~

總結(jié)

以上是生活随笔為你收集整理的权值线段树小结（hdu多校，普通平衡树，郁闷的出纳员）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。