本文共 8544 字，大约阅读时间需要 28 分钟。
之前刷了一点主席树的题目，但是没有系统的做过权值线段树的题目。主席树是多根权值线段树的综合。权值线段树可以解决在总区间里求第k大的问题。在普通的线段树里，我们每一个节点维护的是权值大小。但是在权值线段树里维护的是数字在数组中的相对的位置。所以权值线段树经常需要和离散化结合在一起。
昨天hdu多校一个权值线段树的题目。 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 DescriptionGiven 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 60Sample Output
0 0 0 0 0 2 3 0 1 1 2 3 给定n个数和一个数字m，对于位置i，我们需要保证从1~i-1的数字和小于m，那么我们最少使前面多少个数字为0。一开始就是暴力主席树，每次找最大的去删除。一开始数组开小了，该返回re却返回的是TLE。1e5的数据量我们最差也应该是nlogn的时间复杂度。这时权值线段树就派上用场了。 对于每一个位置的数字，我们找出在他之前小于等于m-a[i]的数字的个数，再用I-ans-1就是我们要知道的答案了。统计完答案之后，就在将这个数插入到线段树中就好了。1e9的数据量，需要离散化。 代码如下：#include#include #include #include #include #include #define ll long longusing 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代表的是前面几个数字的和 p[cur].num=p[cur<<1].num+p[cur<<1|1].num;//num代表的是数字出现的次数}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;//如果这个节点的权值和小于ant就直接返回数字个数就可以 if(p[cur].l==p[cur].r) return min(ant/b[p[cur].l],p[cur].num);//如果到达了叶子节点，我们就去凑ant if(ant<=p[cur<<1].sum) return query(ant,cur<<1);//如果小于左子树的权值，就进入左子树 else return p[cur<<1].num+query(ant-p[cur<<1].sum,cur<<1|1);//大于左子树，就加上左子树的数字个数再加上右子树符合题意的数字个数}void update(int pos,ll add,int cur){ int L=p[cur].l; int R=p[cur].r; if(L==R)//单点更新，到达叶子节点才更新 { 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);//统计完答案后就更新 } printf("\n"); } return 0;}
结束之后刷了刷权值线段树的题目。orz
普通的平衡树 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)Output
对于操作3,4,5,6每行输出一个数，表示对应答案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的数据范围：n<=1000002.每个数的数据范围：[-2e9,2e9]
权值线段树的题目貌似splay树都能解决。但是不会splay树。。 总共有6中操作。对于这个题目我们进行离线处理。 1.在那个数字的位置加一。 2.在那个数字的位置减一。 3.假设x在离散化后的数组中的位置是pos，我们统计出前pos-1有多少个数，再加一就好了 4.求第k大。。 5.前驱，假设x在离散化后的数组中的位置是pos，我们求出前pos-1的数目为num，去查询排名第num的数字是什么就好了。 6.后驱，假设x在离散化后的数组中的位置是pos，我们求出前pos的数目为num，去查询排名为num+1的数字是什么就好了。 代码如下：#include#include #include #include #include #include #define ll long longusing 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;}/*131 1064654 11 3177211 4609291 6449851 841851 898516 819681 4927375 4935983 819683 4927373 106465*/
郁闷的出纳员
OIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的 工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好 ，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我 真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位 员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员 工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘 了一位新员工，我就得为他新建一个工资档案。老板经常到我这边来询问工资情况，他并不问具体某位员工的工资 情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后 告诉他答案。好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样 ，不是很困难吧？ Input 第一行有两个非负整数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是一个非负整数，F命令中的k是一个正整数。 在初始时，可以认为公司里一个员工也没有。 I命令的条数不超过100000 A命令和S命令的总条数不超过100 F命令的条数不超过100000 每次工资调整的调整量不超过1000 新员工的工资不超过100000 Output 输出行数为F命令的条数加一。 对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数， 如果k大于目前员工的数目，则输出-1。 输出文件的最后一行包含一个整数，为离开公司的员工的总数。 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 代码如下：