ZOJ 2112 Dynamic Rankings (动态区间第K大) (线段树套SBT+二分)

2024-08-21 08:08

本文主要是介绍ZOJ 2112 Dynamic Rankings (动态区间第K大) (线段树套SBT+二分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:支持修改数组元素的区间第k大。

看题解这道题是可以用树状数组套主席树做的,但是树状数组套主席树不优化空间的话,要140MB左右,这题只给了32MB。

没看懂怎么优化,只能用线段树套平衡树了,我写的是线段树套SBT,线段树的每个节点上的SBT存这个节点代表的区间的所有数。

修改操作就是对于叶节点到根的所有SBT删除旧元素再加入新元素,删除的元素把下标入栈,插入元素时优先从栈中取。

对于一个数M求它在[L,R]中的排名就是用线段树分段求每一段中小于M的数的个数最后再+1就是M的排名,

有了这个操作就可以二分法找到区间的第k大。空间的话,n=50000,SBT只要开  n*( ceil(log2(n)) +1 ) 的空间就可以了,大约85万。

二分的时候,先做了一个优化,先求出所有涉及的节点,以及区间内的最大值最小值,然后再二分,从910ms优化到了730ms。

代码:(730ms  16404KB)

#include <iostream>
#include <cstdio>
#include <stack>
#include <algorithm>
#include <vector> 
#include <cstring>
#define inf 0x7fffffff
#define maxn 50007
#define maxnn 870007 
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
using namespace std; 
stack<int> D;//被删节点标号 
//SBT
int L[maxnn],R[maxnn],S[maxnn],K[maxnn],IP;//左右子树,树中元素个数,键值,指针
//左旋右旋 
void zig(int &x){int t=R[x];R[x]=L[t];L[t]=x;S[t]=S[x];S[x]=S[L[x]]+S[R[x]]+1;x=t;}
void zag(int &x){int t=L[x];L[x]=R[t];R[t]=x;S[t]=S[x];S[x]=S[L[x]]+S[R[x]]+1;x=t;}
void level(int &x){//平衡函数 if(S[L[L[x]]]>S[R[x]]) {zag(x);level(R[x]);level(x);return;}if(S[R[R[x]]]>S[L[x]]) {zig(x);level(L[x]);level(x);return;}if(S[R[L[x]]]>S[R[x]]) {zig(L[x]);zag(x);level(L[x]);level(R[x]);return;}if(S[L[R[x]]]>S[L[x]]) {zag(R[x]);zig(x);level(R[x]);level(L[x]);return;}
}
void Insert(int &x,int v){//加入元素 if(!x) {//取新元素下标 if(D.empty()) x=++IP;else x=D.top(),D.pop();//赋值 L[x]=R[x]=0;S[x]=1;K[x]=v;return;}//递归 v <= K[x]?Insert(L[x],v):Insert(R[x],v);//更新,平衡 ++S[x];level(x);
}
bool Del(int &x,int v){//删除元素 if(!x) return 0;bool T=0;if(v==K[x]){//如果到了要删的节点 if(R[x]){//如果有右子树 zig(x);//左旋 T=Del(L[x],v);//递归删除左子树 S[x]-=T;level(x);//更新+平衡 return T;}//无右子树,直接令x=L[x]来删除x节点,注意回收x的空间 D.push(x);x=L[x];return 1;}//没到要删的节点,递归删除 T = v < K[x]?Del(L[x],v):Del(R[x],v);S[x]-=T;level(x);return T;
}
int getRank(int x,int v){//求v在树x中的排名 if(!x) return 1;return v <= K[x]?getRank(L[x],v):1+S[L[x]]+getRank(R[x],v);
}
//常规
int n,m;//n数组元素个数,m操作个数 
int A[maxn];//原数组 
//线段树套平衡树,每个节点都是一颗SBT的根节点 
int SBT[maxn <<2];//树根 
int Max[maxn<<2],Min[maxn<<2],Minx,Maxx;//最大最小值
vector <int> Roots;//预存当前区间需要用到的节点
void build(int l,int r,int rt){//建树 for(int i=l;i<=r;++i) Insert(SBT[rt],A[i]);if(l==r) {Max[rt]=Min[rt]=A[l];return;}int m=(l+r)>>1;build(ls);build(rs);Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);Min[rt]=min(Min[rt<<1],Min[rt<<1|1]);
}
void Find(int L,int R,int l,int r,int rt){//预处理区间信息if(L <= l && r <= R) {Roots.push_back(rt);Maxx=max(Maxx,Max[rt]);Minx=min(Minx,Min[rt]);return;}int m=(l+r)>>1;if(L <= m) Find(L,R,ls);if(R >  m) Find(L,R,rs);
}
void Change(int X,int C,int l,int r,int rt){//修改元素:删旧的,插入新的 Del(SBT[rt],A[X]);Insert(SBT[rt],C);if(l==r) {Max[rt]=Min[rt]=C;return;}int m = (l + r) >> 1;X <= m?Change(X,C,ls):Change(X,C,rs);Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);Min[rt]=min(Min[rt<<1],Min[rt<<1|1]);
}
int main(void)
{int Test;scanf("%d",&Test);while(Test-->0){//初始化SBT L[0]=R[0]=S[0]=IP=0;while(!D.empty()) D.pop();memset(SBT,0,sizeof(SBT));//读取输入 scanf("%d%d",&n,&m);for(int i=1;i<=n;++i) scanf("%d",&A[i]);//建树 build(1,n,1);//处理操作 for(int i=0;i<m;++i){char op;int s,t,k;scanf(" %c%d%d",&op,&s,&t);if(op=='C'){//修改,A[s]中是旧的数组值,更改完后更新A[s] Change(s,t,1,n,1);A[s]=t;}else{scanf("%d",&k);Minx=inf;Maxx=0;Roots.clear();Find(s,t,1,n,1);//预处理区间//二分查找 int L=Minx,R=Maxx+1;while(L+1 < R){//左闭右开[L,R),求Rank=k的最大值 int M = (L + R) >> 1;int rank=1;for(int j=0;j<Roots.size();++j) rank+=getRank(SBT[Roots[j]],M)-1;if(rank <= k) L=M;else R=M;}printf("%d\n",L);}}}
return 0;
}






这篇关于ZOJ 2112 Dynamic Rankings (动态区间第K大) (线段树套SBT+二分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1092591

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl