#809. 「UNR #7」那些你不要的

被吊打场。

题目简介

题目名称： 那些你不想要的

题目来源：

评测链接：https://uoj.ac/problem/809

形式化题意：存在一个长度为 的序列 ，二人进行博弈，每次每个人选择一个长度为 的区间删除，并使剩余的合并。先手希望剩下的那一个数最大，后手希望最小。求最优策略下剩下的数。多测。

数据范围：

太傻逼了，考场上胡了一个神秘线段树调了一上午。

考虑按照奇偶性分治，容易发现（我就没发现）无论如何一次操作会删除一个当前序列奇数位的数，一个当前序列偶数位的数，而这个结论放在原序列也是成立的。

不妨将奇数位的记为 ，偶数位的记为 ，则原序列一定形如：

$$\{ x,y,x,y,x,\dots,x,y,x \}$$

那么，无论先手后手操作哪一个区间，这个结构都不会变。而最后剩下的那一个数一定是一个 。

所以，现在的博弈变成了先后手在一个区间里删除一个数，使最后一个数最大。

那不就是中位数吗，直接输出就结了。时间复杂度 或者 ，不会还有人不会实现吧（别骂了）。代码里还有爆零线段树遗址。

AC Code

// ----- Eternally question-----
// Problem: A. 那些你不要的
// Contest: UOJ - UOJ NOI Round #7 Day1
// URL: https://uoj.ac/contest/84/problem/809
// Memory Limit:  512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-15 08:55:37
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e6+10;
const int INF=0x3f3f3f3f;
int Test,N,a[MAXN],Suc[MAXN];
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment
{
	int l,r;
	int mx,rmx,mxpos;
	int mn,rmn,mnpos;
}Tr[MAXN<<2];
inline void pushUp(int p)
{
	Tr[p].mx=std::max(Tr[ls].mx,Tr[rs].mx),
	Tr[p].mn=std::min(Tr[ls].mn,Tr[rs].mn);
	Tr[p].rmx=std::max(Tr[ls].rmx,Tr[rs].rmx),
	Tr[p].rmn=std::min(Tr[ls].rmn,Tr[rs].rmn);
	if(Tr[ls].mx==Tr[rs].mx)
	{
		if(Tr[ls].rmx>Tr[rs].rmx) Tr[p].mxpos=Tr[ls].mxpos;
		else Tr[p].mxpos=Tr[rs].mxpos;
	}
	if(Tr[ls].mx>Tr[rs].mx) Tr[p].mxpos=Tr[ls].mxpos;
	if(Tr[rs].mx>Tr[ls].mx) Tr[p].mxpos=Tr[rs].mxpos;
	if(Tr[ls].mn==Tr[rs].mn)
	{
		if(Tr[ls].rmn<Tr[rs].rmn) Tr[p].mnpos=Tr[ls].mnpos;
		else Tr[p].mnpos=Tr[rs].mnpos;
	}
	if(Tr[ls].mn<Tr[rs].mn) Tr[p].mnpos=Tr[ls].mnpos;
	if(Tr[rs].mn<Tr[ls].mn) Tr[p].mnpos=Tr[rs].mnpos;
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r;
	if(l==r)
	{
		Suc[l]=l+1;
		int vx=Suc[l]==N+1?-INF:a[Suc[l]],vn=Suc[l]==N+1?INF:a[Suc[l]];
		Tr[p].mx=a[l]+vx,Tr[p].mn=a[l]+vn;
		Tr[p].rmx=std::max(a[l],vx),
		Tr[p].rmn=std::min(a[l],vn);
		Tr[p].mxpos=Tr[p].mnpos=l;
		return ;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
void reFresh(int p,int x)
{
	if(x<=0) return ;
	if(Tr[p].l==Tr[p].r)
	{
		int vx=Suc[x]==N+1?-INF:a[Suc[x]],vn=Suc[x]==N+1?INF:a[Suc[x]];
		Tr[p].mx=a[x]+vx,Tr[p].mn=a[x]+vn;
		Tr[p].rmx=std::max(a[x],vx),
		Tr[p].rmn=std::min(a[x],vn);
		return ;
	}
	int mid=(Tr[p].l+Tr[p].r)>>1;
	x<=mid?reFresh(ls,x):reFresh(rs,x);
	pushUp(p);
}
void modifyDel(int p,int x)
{
	if(Tr[p].l==Tr[p].r)
	{
		Tr[p].mx=Tr[p].rmx=-1;
		Tr[p].mn=Tr[p].rmn=INF;
		return ;
	}
	int mid=(Tr[p].l+Tr[p].r)>>1;
	x<=mid?modifyDel(ls,x):modifyDel(rs,x);
	pushUp(p);
}
struct Position
{
	struct St
	{ int l,r,mx,mn; }Tr[MAXN<<2];
	inline void pushUp(int p)
	{
		Tr[p].mx=std::max(Tr[ls].mx,Tr[rs].mx);
		Tr[p].mn=std::min(Tr[ls].mn,Tr[rs].mn);
	}
	void build(int p,int l,int r)
	{
		Tr[p].l=l,Tr[p].r=r;
		if(l==r) return Tr[p].mx=Tr[p].mn=l,void();
		int mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		pushUp(p);
	}
	void modifyX(int p,int x,int v)
	{
		if(Tr[p].l==Tr[p].r) return Tr[p].mx=Tr[p].mn=v,void();
		int mid=(Tr[p].l+Tr[p].r)>>1;
		x<=mid?modifyX(ls,x,v):modifyX(rs,x,v);
		pushUp(p);
	}
	int queryMin(int p,int l,int r)
	{
		if(l>r) return N+1;
		if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].mn;
		int mid=(Tr[p].l+Tr[p].r)>>1,res=N+1;
		if(l<=mid) checkMin(res,queryMin(ls,l,r));
		if(mid<r) checkMin(res,queryMin(rs,l,r));
		return res;
	}
	int queryMax(int p,int l,int r)
	{
		if(l>r) return 0;
		if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].mx;
		int mid=(Tr[p].l+Tr[p].r)>>1,res=0;
		if(l<=mid) checkMax(res,queryMax(ls,l,r));
		if(mid<r) checkMax(res,queryMax(rs,l,r));
		return res;
	}
}Suf,Pre;
int tmp[MAXN];
inline void solve()
{
	int M=0;
	for(int i=1;i<=N;i+=2) tmp[++M]=a[i];
	std::sort(tmp+1,tmp+M+1);
	write(tmp[M/2+1],'\n');
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		read(N);a[N+1]=0;
		for(int i=1;i<=N;++i) read(a[i])/*,(a[i]==500406)&&(write(i,'\n'),1)*/;
		solve();
		continue;
		build(1,1,N),Suf.build(1,1,N),Pre.build(1,1,N);Suc[0]=1;
		for(int i=1;i<=(N>>1);++i)
		{
			int pos=i&1?Tr[1].mnpos:Tr[1].mxpos;
			// write(Tr[1].mnpos,' ');
			modifyDel(1,pos),modifyDel(1,Suc[pos]);
			Pre.modifyX(1,pos,-1),Pre.modifyX(1,Suc[pos],-1);
			Suf.modifyX(1,pos,N+1),Suf.modifyX(1,Suc[pos],N+1);
			if(pos==735261/*||pos==192463||pos==905666||pos==862215*/) write(i,' '),puts("yes");
			if(Suc[pos]==735261/*||Suc[pos]==192463||Suc[pos]==905666||Suc[pos]==862215*/) write(i,' '),puts("yes");
			int pre=Pre.queryMax(1,1,pos-1);
			if(i==278841) write("Erase:",pos,' ',Suc[pos],'-',a[pos],' ',a[Suc[pos]],' ',pre,'\n');
			checkMax(pre,0);
			Suc[pre]=Suf.queryMin(1,pos,N);
			reFresh(1,pre);
			// write(pos,'\n');
		}
		write(a[Suc[0]],'\n');
	}
	return 0;
}