博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Bzoj1901 Dynamic Ranking
阅读量:5849 次
发布时间:2019-06-19

本文共 2768 字,大约阅读时间需要 9 分钟。

动态区间第k小

离散化后

那么每个点开一棵线段树(主席树)再套一个树状数组在外面

每次询问区间内的树的个数时

相当于进行了一次树状数组求区间和的操作,只是是把树状数组那个点看做主席树,对log棵主席树求区间和

然后每次询问,修改时就是把log棵主席树同时跳到儿子,修改也是log棵

时间复杂度O(nlogn*logn)空间复杂度O(nlogn*logn)

# include 
# define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;const int _(2e4 + 10), __(2e6 + 10);IL ll Read(){ RG char c = getchar(); RG ll x = 0, z = 1; for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1; for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); return x * z;}int n, m, len, p[_], a[_], ql[_], qr[_], qk[_], qo[_];int ls[__], rs[__], sz[__], rt[__], num, tmp[2][20];IL void Modify(RG int &x, RG int l, RG int r, RG int pos, RG int val){ if(!x) x = ++num; sz[x] += val; if(l == r) return; RG int mid = (l + r) >> 1; if(pos <= mid) Modify(ls[x], l, mid, pos, val); else Modify(rs[x], mid + 1, r, pos, val);}IL void PreModify(RG int x, RG int val){ RG int k = lower_bound(p + 1, p + len + 1, a[x]) - p; for(RG int i = x; i <= n; i += i & -i) Modify(rt[i], 1, len, k, val);}IL int Query(RG int l, RG int r, RG int k){ if(l == r) return l; RG int mid = (l + r) >> 1, sum = 0; for(RG int i = 1; i <= tmp[1][0]; i++) sum += sz[ls[tmp[1][i]]]; for(RG int i = 1; i <= tmp[0][0]; i++) sum -= sz[ls[tmp[0][i]]]; if(k <= sum){ for(RG int i = 1; i <= tmp[1][0]; i++) tmp[1][i] = ls[tmp[1][i]]; for(RG int i = 1; i <= tmp[0][0]; i++) tmp[0][i] = ls[tmp[0][i]]; return Query(l, mid, k); } else{ for(RG int i = 1; i <= tmp[1][0]; i++) tmp[1][i] = rs[tmp[1][i]]; for(RG int i = 1; i <= tmp[0][0]; i++) tmp[0][i] = rs[tmp[0][i]]; return Query(mid + 1, r, k - sum); }}IL int PreQuery(RG int l, RG int r, RG int k){ Fill(tmp, 0); for(RG int i = r; i; i -= i & -i) tmp[1][++tmp[1][0]] = rt[i]; for(RG int i = l - 1; i; i -= i & -i) tmp[0][++tmp[0][0]] = rt[i]; return Query(1, len, k);}int main(RG int argc, RG char* argv[]){ n = Read(); m = Read(); for(RG int i = 1; i <= n; i++) a[i] = Read(), p[++len] = a[i]; for(RG int i = 1; i <= m; i++){ RG char c; scanf(" %c", &c); qo[i] = c == 'Q'; if(qo[i]) ql[i] = Read(), qr[i] = Read(), qk[i] = Read(); else ql[i] = qr[i] = Read(), qk[i] = Read(), p[++len] = qk[i]; } sort(p + 1, p + len + 1); len = unique(p + 1, p + len + 1) - p - 1; for(RG int i = 1; i <= n; i++) PreModify(i, 1); for(RG int i = 1; i <= m; i++) if(qo[i]) printf("%d\n", p[PreQuery(ql[i], qr[i], qk[i])]); else{ PreModify(ql[i], -1); a[ql[i]] = qk[i]; PreModify(ql[i], 1); } return 0;}

转载于:https://www.cnblogs.com/cjoieryl/p/8206370.html

你可能感兴趣的文章
PL/SQL --> DML 触发器
查看>>
PHP设计模式学习笔记: 策略模式
查看>>
利用P2P终结者实现机顶盒限速
查看>>
python笔记(基础进阶1.8-1.9)
查看>>
Html5 web sql database
查看>>
Centos6.4制作Tengine的rpm包
查看>>
Jenkins进阶系列之——11详解Jenkins节点配置
查看>>
xshell远程连接centos7 rz/sz命名配置
查看>>
第一次来,因为一个CSS问题而来
查看>>
DAYDREAM和VIVE平台的框架API
查看>>
我和学员那些事
查看>>
DNS基本介绍及应用软件bind9编译安装
查看>>
禁止指定user_agent
查看>>
新手必须掌握的Linux命令
查看>>
Shell ⑦
查看>>
sso实现Cookie共享
查看>>
数据库工作于独立主机的lamp平台安装实现
查看>>
vim使用技巧及快捷键
查看>>
windows和的linux的netstat
查看>>
Apache与浏览器之间的并发,连接,请求
查看>>