【前缀中位数】 stdKonjac的小站

题目描述

给定一个长度为 N 的序列 A，标号为 1～N ，其第 i 个数字为 A_i 。要求一个长度同样为 N 的序列 B 。已知，B_i 为序列 A 中 1～i 所有数的中位数。

定义中位数：对于长度为 2m 的序列，中位数为第 m 小的数，对于长度为 2m+1 的序列，中位数为第 m+1 小的数。

输入格式

第一行一个整数 N ，表示序列 A 长度。
接下来一行有 N 个用空格隔开的数，第 i 个数表示 A_i。

输出格式

输出 N 行，每行一个数，第 i 行的数表示 B_i 。

样例数据 1

输入

3
1 2 3

输出

1
1
2

备注

【数据范围】
对于 30% 的数据有：N<=200；
对于 60% 的数据有：N<=2000；
对于 100% 的数据有：N<=200000，所有数字在 10⁹范围内。

第一次写主席树没加读优常数各种巨大982ms险过QAQ 后来还是照着YYY大神的模板重写了一遍只用了300+ms(窝巢我原来写的真的是主席树!?)瞬间感受到了蒟蒻和神犇的差距……

不说了接下来上模板TAT：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define N 200001
#define Maxval 1000000001
using namespace std;
int n,cnt,pos,a[N],root[N<<5];
struct node{int lson,rson,sum;}tree[N<<5];
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void newnode(int now)
{
	root[now]=++cnt;
	tree[cnt]=tree[root[now-1]];
}
void update(int rt,int L,int R,int val)
{
	if(L==R){tree[rt].sum++;return;}
	int mid=(L+R)>>1;
	if(val<=mid)
	{
		tree[++cnt]=tree[tree[rt].lson];
		tree[rt].lson=cnt;
		update(tree[rt].lson,L,mid,val);
	}
	if(val>mid)
	{
		tree[++cnt]=tree[tree[rt].rson];
		tree[rt].rson=cnt;
		update(tree[rt].rson,mid+1,R,val);
	}
	tree[rt].sum=tree[tree[rt].lson].sum+tree[tree[rt].rson].sum;
}
void query(int left,int right,int L,int R,int pos)
{
	if(L==R) {cout<<L<<endl;return;}
	int mid=(L+R)>>1;
	int now=tree[tree[right].lson].sum-tree[tree[left].lson].sum;
	if(now>=pos) query(tree[left].lson,tree[right].lson,L,mid,pos);
	if(now<pos)  query(tree[left].rson,tree[right].rson,mid+1,R,pos-now);
}
void init()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
	   a[i]=read();
	   newnode(i);
	   update(root[i],1,Maxval,a[i]);
	}
}
void ask()
{
	for(int i=1;i<=n;i++)
	{
		pos=(i%2==0)?(i>>1):(i>>1)+1;
		query(root[0],root[i],1,Maxval,pos);
	}
}
int main()
{
     freopen("T3.in","r",stdin);
     freopen("T3.out","w",stdout);
     init();
     ask();
     return 0;
}

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#define N 200001

#define Maxval 1000000001

using namespace std;

int n,cnt,pos,a[N],root[N<<5];

struct node{int lson,rson,sum;}tree[N<<5];

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}

while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}

return x*f;

}

void newnode(int now)

{

root[now]=++cnt;

tree[cnt]=tree[root[now-1]];

}

void update(int rt,int L,int R,int val)

{

if(L==R){tree[rt].sum++;return;}

int mid=(L+R)>>1;

if(val<=mid)

{

tree[++cnt]=tree[tree[rt].lson];

tree[rt].lson=cnt;

update(tree[rt].lson,L,mid,val);

}

if(val>mid)

{

tree[++cnt]=tree[tree[rt].rson];

tree[rt].rson=cnt;

update(tree[rt].rson,mid+1,R,val);

}

tree[rt].sum=tree[tree[rt].lson].sum+tree[tree[rt].rson].sum;

}

void query(int left,int right,int L,int R,int pos)

{

if(L==R) {cout<<L<<endl;return;}

int mid=(L+R)>>1;

int now=tree[tree[right].lson].sum-tree[tree[left].lson].sum;

if(now>=pos) query(tree[left].lson,tree[right].lson,L,mid,pos);

if(now<pos) query(tree[left].rson,tree[right].rson,mid+1,R,pos-now);

}

void init()

{

n=read();

for(int i=1;i<=n;i++)

{

a[i]=read();

newnode(i);

update(root[i],1,Maxval,a[i]);

}

void ask()

{

for(int i=1;i<=n;i++)

{

pos=(i%2==0)?(i>>1):(i>>1)+1;

query(root[0],root[i],1,Maxval,pos);

}

int main()

{

freopen("T3.in","r",stdin);

freopen("T3.out","w",stdout);

init();

ask();

return 0;

}