ZOJ-2112-Dynamic Rankings(线段树套splay树)
2024-09-17 14:43:59
题意：
完成两个操作：
1.询问一个区间里第k小的数；
2.修改数列中一个数的值。
分析：
线段树套平衡树，线段树中的每个节点都有一棵平衡树，维护线段树所记录的这个区间的元素。
这样处理空间上是O(nlogn)的，因为线段树有logn层，每层的平衡树所记的节点总数都有n个。
修改很容易想到，把所有包含要修改点的区间的平衡树都修改了就行了
查询使用二分答案的方法
// File Name: 2112.cpp
// Author: Zlbing
// Created Time: 2013年10月07日 星期一 18时24分39秒
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
#define lson l,m,root<<1
#define rson m+1,r,root<<1|1
const int MAXN=5e4+;
//线段树套平衡树，线段树中的每个结点都有一颗平衡树，维护线段树所记录
//的这个区间的元素
//rt数组是维护线段树的数组，表示线段树结点中的平衡树的根
//对于spaly树中的修改只要将rt修改成rt[root]并传递root参数
struct SplayTree {
int sz[MAXN*];
int ch[MAXN*][];
int pre[MAXN*];
int top;
int rt[MAXN<<];
inline void up(int x){
sz[x] = cnt[x] + sz[ ch[x][] ] + sz[ ch[x][] ];
}
inline void Rotate(int x,int f){
int y=pre[x];
ch[y][!f] = ch[x][f];
pre[ ch[x][f] ] = y;
pre[x] = pre[y];
if(pre[x]) ch[ pre[y] ][ ch[pre[y]][] == y ] =x;
ch[x][f] = y;
pre[y] = x;
up(y);
}
inline void Splay(int x,int goal,int root){//将x旋转到goal的下面
while(pre[x] != goal){
if(pre[pre[x]] == goal) Rotate(x , ch[pre[x]][] == x);
else {
int y=pre[x],z=pre[y];
int f = (ch[z][]==y);
if(ch[y][f] == x) Rotate(x,!f),Rotate(x,f);
else Rotate(y,f),Rotate(x,f);
}
}
up(x);
if(goal==) rt[root]=x;
}
inline void RTO(int k,int goal,int root){//将第k位数旋转到goal的下面
int x=rt[root];
while(sz[ ch[x][] ] != k-) {
if(k < sz[ ch[x][] ]+) x=ch[x][];
else {
k-=(sz[ ch[x][] ]+);
x = ch[x][];
}
}
Splay(x,goal,root);
}
inline void vist(int x){
if(x){
printf("结点%2d : 左儿子 %2d 右儿子 %2d %2d sz=%d\n",x,ch[x][],ch[x][],val[x],sz[x]);
vist(ch[x][]);
vist(ch[x][]);
}
}
inline void Newnode(int &x,int c){
x=++top;
ch[x][] = ch[x][] = pre[x] = ;
sz[x]=; cnt[x]=;
val[x] = c;
}
inline void init(){
top=;
}
inline void Insert(int &x,int key,int f,int root){
if(!x) {
Newnode(x,key);
pre[x]=f;
Splay(x,,root);
return ;
}
if(key==val[x]){
cnt[x]++;
sz[x]++;
return ;
}else if(key<val[x]) {
Insert(ch[x][],key,x,root);
} else {
Insert(ch[x][],key,x,root);
}
up(x);
} void Del(int root){ //删除根结点
if(cnt[rt[root]]>)
{
cnt[rt[root]]--;
}
else
{
int t=rt[root];
if(ch[rt[root]][]) {
rt[root]=ch[rt[root]][];
RTO(,,root);
ch[rt[root]][]=ch[t][];
if(ch[rt[root]][]) pre[ch[rt[root]][]]=rt[root];
}
else rt[root]=ch[rt[root]][];
pre[rt[root]]=;
}
up(rt[root]);
}
void findpre(int x,int key,int &ans){ //找key前趋
if(!x) return ;
if(val[x] <= key){
ans=x;
findpre(ch[x][],key,ans);
} else
findpre(ch[x][],key,ans);
}
void findsucc(int x,int key,int &ans){ //找key后继
if(!x) return ;
if(val[x]>=key) {
ans=x;
findsucc(ch[x][],key,ans);
} else
findsucc(ch[x][],key,ans);
}
void findkey(int x,int key,int &ans)//找key
{
if(!x)return;
if(val[x]==key)
ans=x;
else if(val[x]>key)
findkey(ch[x][],key,ans);
else
findkey(ch[x][],key,ans);
}
//找第K大数
inline int find_kth(int x,int k,int root){
if(k<sz[ch[x][]]+) {
return find_kth(ch[x][],k,root);
}else if(k > sz[ ch[x][] ] + cnt[x] )
return find_kth(ch[x][],k-sz[ch[x][]]-cnt[x],root);
else{
Splay(x,,root);
return val[x];
}
}
int cnt[MAXN*];
int val[MAXN*];
//---------------------------------------------
//建立线段树和线段树中的每个结点的平衡树
void build(int l,int r,int root)
{
rt[root]=;
for(int i=l;i<=r;i++)
Insert(rt[root],a[i],,root);
if(l>=r)return;
int m=(l+r)>>;
build(lson);
build(rson);
}
void update(int l,int r,int root,int i,int x)
{
int ans=;
findkey(rt[root],a[i],ans);
Splay(ans,,root);
Del(root);
Insert(rt[root],x,,root); if(l>=r)return;
int m=(l+r)>>;
if(i<=m)update(lson,i,x);
else update(rson,i,x);
}
int cntLess(int x,int key)
{
int ret=;
while(x)
{
if(val[x]>key)
x=ch[x][];
else
{
ret+=cnt[x]+sz[ch[x][]];
x=ch[x][];
}
}
return ret;
}
int getnumLess(int l,int r,int root,int L,int R,int x)
{
if(L<=l&&R>=r)
return cntLess(rt[root],x);
int m=(l+r)>>;
int ret=;
if(L<=m)ret+=getnumLess(lson,L,R,x);
if(R>m)ret+=getnumLess(rson,L,R,x);
return ret;
}
int search(int L,int R,int k)
{
int l=,r=INF;
int ans=;
while(l<=r)
{
int m=(l+r)>>;
int cnt=getnumLess(,n,,L,R,m);
if(cnt>=k)
{
r=m-;
ans=m;
}
else l=m+;
}
return ans;
}
void solve()
{
scanf("%d%d",&n,&m);
REP(i,,n)
scanf("%d",&a[i]);
build(,n,);
REP(i,,m)
{
int x,y,z;
char str[];
scanf("%s",str);
if(str[]=='C')
{
scanf("%d%d",&x,&y);
update(,n,,x,y);
a[x]=y;
}
else
{
scanf("%d%d%d",&x,&y,&z);
int k=search(x,y,z);
printf("%d\n",k);
}
}
}
int a[MAXN];
int n,m; }spt;
int main()
{
int cas;
scanf("%d",&cas);
while(cas--)
{
spt.init();
spt.solve();
}
return ;
}
最新文章
- Spring MVC过滤器-委派过滤器代理（DelegatingFilterProxy）
- 【leetcode】Plus One (easy)
- Version of SQLCE in WP8
- 《android传感器高级编程》译者序
- Functional programming
- javascrip keyCode属性备案
- Cannot retrieve metalink for repository: epel. Please verify its path and try again
- Android之图片窗口和大小调节
- oc学习笔记2
- 怎样用Google APIs和Google的应用系统进行集成(3)----调用Google 发现（Discovery）API的RESTful服务
- sf中schedule设定
- Object-C知识点 (一) 常用知识点
- 【NOIP2015提高组】跳石头
- C语言拼接字符串以及进制转换
- Tomcat启动失败
- xargs与exec详解
- BZOJ1146 [CTSC2008]网络管理Network 树链剖分 主席树 树状数组
- iOS知识点持续更新。。。
- mongodb spring 配置文件
- 【Git】创建一个空分支