洛谷P3871 [TJOI2010]中位数(splay)
2018-07-06 01:20:10来源:博客园 阅读 ()
题目描述
给定一个由N个元素组成的整数序列,现在有两种操作:
1 add a
在该序列的最后添加一个整数a,组成长度为N + 1的整数序列
2 mid 输出当前序列的中位数
中位数是指将一个序列按照从小到大排序后处在中间位置的数。(若序列长度为偶数,则指处在中间位置的两个数中较小的那个)
例1:1 2 13 14 15 16 中位数为13
例2:1 3 5 7 10 11 17 中位数为7
例3:1 1 1 2 3 中位数为1
输入输出格式
输入格式:
第一行为初始序列长度N。第二行为N个整数,表示整数序列,数字之间用空格分隔。第三行为操作数M,即要进行M次操作。下面为M行,每行输入格式如题意所述。
输出格式:
对于每个mid操作输出中位数的值
输入输出样例
6 1 2 13 14 15 16 5 add 5 add 3 mid add 20 mid
5 13
说明
对于30%的数据,1 ≤ N ≤ 10,000,0 ≤ M ≤ 1,000
对于100%的数据,1 ≤ N ≤ 100,000,0 ≤ M ≤ 10,000
序列中整数的绝对值不超过1,000,000,000,序列中的数可能有重复
每个测试点时限1秒
这题不是随便做么。。
口胡一下我能想到的做法吧,,
1.$M < 10000$的话vector暴力插入不知道能不能A,
2.直接用平衡树,我写的是splay,不想写代码的话可以用pb_ds里维护了siz域的红黑树
3.先离线,对权值离散化,然后用权值线段树查。
4.沿用https://www.luogu.org/problemnew/show/P1801这道题的做法
#include<cstdio> using namespace std; const int MAXN = 1e6 + 10; #define ls(x) ch[x][0] #define rs(x) ch[x][1] #define root ch[0][1] int fa[MAXN], val[MAXN], rev[MAXN], siz[MAXN], ch[MAXN][2], tot = 0; bool ident(int x) { return ch[fa[x]][0] == x ? 0 : 1; } void connect(int x, int _fa, int opt) { fa[x] = _fa, ch[fa[x]][opt] = x; } void update(int x) { siz[x] = siz[ls(x)] + siz[rs(x)] + rev[x]; } void rotate(int x) { int Y = fa[x], R = fa[Y]; int Yson = ident(x), Rson = ident(Y); int B = ch[x][Yson ^ 1]; connect(B, Y, Yson); connect(x, R, Rson); connect(Y, x, Yson ^ 1); //tag update(Y); update(x); } void splay(int x, int to) { to = fa[to]; while(fa[x] != to) { int y = fa[x]; if(fa[y] == to) rotate(x); else if(ident(x) == ident(y)) rotate(y), rotate(x); else rotate(x), rotate(x); } } int NewNode(int _fa, int _val) { val[++tot] = _val; fa[tot] = _fa; siz[tot] = rev[tot] = 1; return tot; } void insert(int x) { if(!root) {root = NewNode(0, x); return ;} int now = root; while(now) { siz[now]++; if(val[now] == x) {rev[now]++; return ;} int nxt = val[now] < x; if(!ch[now][nxt]) {ch[now][nxt] = NewNode(now, x); splay(ch[now][nxt], root); return ;} now = ch[now][nxt]; } } int ARank(int x) { int now = root; while(now) { //if(siz[now] == x) return val[now]; int used = siz[now] - siz[rs(now)]; if(x > siz[ls(now)] && x <= used) return val[now]; if(used < x) x = x - used, now = ch[now][1]; else now = ch[now][0]; } } char opt[5]; int main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif int N; scanf("%d", &N); for(int i = 1; i <= N; i++) { int x; scanf("%d", &x); insert(x); } int Q; scanf("%d", &Q); while(Q--) { scanf("%s", opt + 1); if(opt[1] == 'a') { int x; scanf("%d", &x); insert(x); N++; } else printf("%d\n", ARank(N / 2 + (N & 1))); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷P1164->小A点菜 2020-05-18
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 洛谷P1034 矩形覆盖 2020-03-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash