_int_me @ 2018-08-18 15:49:29
我的思路是写一个AVL树，不过为了每次都能找到指定位置的数，每个节点都有一个参数用来保存当前节点的左子树共有多少个数，然后还都有一个su来保存当前节点这个数有多少个。 自己构造了很多小数据都能过，但在题里第一个点就wa了，而且confusion就是后面的点都MLE了，但是100000*7的int应该不会爆吧。。求解惑谢谢 代码：
using namespace std; int c = 0, n, a; int nw = 1; int ro = 1; struct avl { int fa; int ls; int rs; int su; int v; int bt;//平衡因子 int lt;//记录左子树有多少个数 }aa[100005]; void ll(int o)//ll rr 都是旋转 rtt为判断用何种旋转 { int oo = aa[o].ls; aa[oo].fa = aa[o].fa; if (aa[oo].fa == 0) { ro = oo; } if (aa[o].fa) { if (aa[aa[o].fa].v < aa[o].v) { aa[aa[o].fa].rs = oo; } else { aa[aa[o].fa].ls = oo; } } aa[o].fa = oo; aa[o].ls = aa[oo].rs; if (aa[oo].rs) { aa[o].lt = aa[aa[oo].rs].lt + aa[aa[oo].rs].su; aa[aa[oo].rs].fa = o; } else { aa[o].lt = 0; } aa[oo].rs = o; } void rr(int o) { int oo = aa[o].rs; aa[oo].fa = aa[o].fa; if (aa[oo].fa == 0) { ro = oo; } if (aa[o].fa) { if (aa[aa[o].fa].v < aa[o].v) { aa[aa[o].fa].rs = oo; } else { aa[aa[o].fa].ls = oo; } } aa[o].fa = oo; aa[o].rs = aa[oo].ls; if (aa[oo].ls) { aa[aa[oo].ls].fa = o; } aa[oo].ls = o; aa[oo].lt += aa[o].su + aa[o].lt; } void rtt(int o) { if (aa[o].bt > 0) { int ooo = aa[o].ls; if (aa[ooo].bt > 0) { ll(o); aa[o].bt = aa[ooo].bt = 0; return; } if (aa[ooo].bt < 0) { rr(ooo); ll(o); if (aa[aa[ooo].rs].bt == 0) { aa[o].bt = aa[ooo].bt = 0; } if (aa[aa[ooo].rs].bt == 0 - 1) { aa[o].bt = 0; aa[ooo].bt = 1; } if (aa[aa[ooo].rs].bt == 1) { aa[o].bt = 0 - 1; aa[ooo].bt = 0; } return; }
}
if (aa[o].bt < 0)
{
int ooo = aa[o].rs;
if (aa[ooo].bt < 0)
{
rr(o);
aa[o].bt = aa[ooo].bt = 0;
return;
}
if (aa[ooo].bt > 0)
{
ll(ooo);
rr(o);
if (aa[aa[ooo].ls].bt == 0)
{
aa[o].bt = aa[ooo].bt = 0;
}
if (aa[aa[ooo].ls].bt == 0 - 1)
{
aa[o].bt = 1;
aa[ooo].bt = 0;
}
if (aa[aa[ooo].ls].bt == 1)
{
aa[o].bt = 0;
aa[ooo].bt = 0 - 1;
}
return;
}
}}
by _int_me @ 2018-08-18 15:51:13
ok 我重发。。
by Drinkkk @ 2018-08-18 15:55:57
希望更丰富的展现？使用Markdown
by 文文殿下 @ 2018-08-18 15:56:23
希望更丰富的展现？使用Markdown
by decoqwq @ 2018-08-18 15:58:43
@_int_me 不是一个vector就好了吗
by 一扶苏一 @ 2018-08-18 16:07:06
希望更丰富的展现？使用Markdown
by _int_me @ 2018-08-18 16:08:31
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int c = 0, n, a;
int nw = 1;
int ro = 1;
struct avl
{
int fa;
int ls;
int rs;
int su;
int v;
int bt;
int lt;
}aa[100005];
void ll(int o)
{
int oo = aa[o].ls;
aa[oo].fa = aa[o].fa;
if (aa[oo].fa == 0)
{
ro = oo;
}
if (aa[o].fa)
{
if (aa[aa[o].fa].v < aa[o].v)
{
aa[aa[o].fa].rs = oo;
}
else
{
aa[aa[o].fa].ls = oo;
}
}
aa[o].fa = oo;
aa[o].ls = aa[oo].rs;
if (aa[oo].rs)
{
aa[o].lt = aa[aa[oo].rs].lt + aa[aa[oo].rs].su;
aa[aa[oo].rs].fa = o;
}
else
{
aa[o].lt = 0;
}
aa[oo].rs = o;
}
void rr(int o)
{
int oo = aa[o].rs;
aa[oo].fa = aa[o].fa;
if (aa[oo].fa == 0)
{
ro = oo;
}
if (aa[o].fa)
{
if (aa[aa[o].fa].v < aa[o].v)
{
aa[aa[o].fa].rs = oo;
}
else
{
aa[aa[o].fa].ls = oo;
}
}
aa[o].fa = oo;
aa[o].rs = aa[oo].ls;
if (aa[oo].ls)
{
aa[aa[oo].ls].fa = o;
}
aa[oo].ls = o;
aa[oo].lt += aa[o].su + aa[o].lt;
}
void rtt(int o)
{
if (aa[o].bt > 0)
{
int ooo = aa[o].ls;
if (aa[ooo].bt > 0)
{
ll(o);
aa[o].bt = aa[ooo].bt = 0;
return;
}
if (aa[ooo].bt < 0)
{
rr(ooo);
ll(o);
if (aa[aa[ooo].rs].bt == 0)
{
aa[o].bt = aa[ooo].bt = 0;
}
if (aa[aa[ooo].rs].bt == 0 - 1)
{
aa[o].bt = 0;
aa[ooo].bt = 1;
}
if (aa[aa[ooo].rs].bt == 1)
{
aa[o].bt = 0 - 1;
aa[ooo].bt = 0;
}
return;
}
}
if (aa[o].bt < 0)
{
int ooo = aa[o].rs;
if (aa[ooo].bt < 0)
{
rr(o);
aa[o].bt = aa[ooo].bt = 0;
return;
}
if (aa[ooo].bt > 0)
{
ll(ooo);
rr(o);
if (aa[aa[ooo].ls].bt == 0)
{
aa[o].bt = aa[ooo].bt = 0;
}
if (aa[aa[ooo].ls].bt == 0 - 1)
{
aa[o].bt = 1;
aa[ooo].bt = 0;
}
if (aa[aa[ooo].ls].bt == 1)
{
aa[o].bt = 0;
aa[ooo].bt = 0 - 1;
}
return;
}
}
}
void bu(int o, int f, int x)
{
aa[o].v = x;
aa[o].su++;
aa[o].fa = f;
}
int cr(int o, int x)
{
if (x == aa[o].v)
{
++aa[o].su;
return 0;
}
else if (x < aa[o].v)
{
++aa[o].lt;
if (aa[o].ls)
{
int cc = cr(aa[o].ls, x);
aa[o].bt += cc;
if (aa[o].bt == 2)
{
rtt(o);
return 1;
}
if (cc == 0 || !aa[o].bt)
{
return 0;
}
if (aa[o].bt)
{
return 1;
}
}
aa[o].ls = nw;
bu(nw++, o, x);
++aa[o].bt;
if (aa[o].bt)
{
return 1;
}
return 0;
}
else
{
if (aa[o].rs)
{
int cc = cr(aa[o].rs, x);
aa[o].bt -= cc;
if (aa[o].bt == 0 - 2)
{
rtt(o);
return 0;
}
if (cc == 0 || !aa[o].bt)
{
return 0;
}
if (aa[o].bt)
{
return 1;
}
}
aa[o].rs = nw;
bu(nw++, o, x);
--aa[o].bt;
if (aa[o].bt)
{
return 1;
}
return 0;
}
}
void md(int o, int p)
{
if (aa[o].lt < p && aa[o].lt + aa[o].su >= p)
{
printf("%d\n", aa[o].v);
return;
}
if (aa[o].lt >= p)
{
md(aa[o].ls, p);
}
if (aa[o].lt + aa[o].su < p)
{
md(aa[o].rs, p - (aa[o].lt + aa[o].su));
}
}
int main()
{
// freopen("tt.txt", "r", stdin);
// freopen("ttt.txt", "w", stdout);
scanf("%d", &n);
scanf("%d", &a);
bu(nw++, 0, a);
printf("%d\n", a);
for (int i = 2; i <= n; i++)
{
scanf("%d", &a);
cr(ro, a);
if (i & 1)
{
md(ro, i / 2 + 1);
}
}
return 0;
}by _int_me @ 2018-08-18 16:09:35
ll rr rtt都是关于旋转的代码 cr是插入 md是查询
by _int_me @ 2018-08-18 16:12:27
那个cc是为了调节平衡因子而设置的中间变量