Atcoder Beginner Contest 127

被 $E$ 给卡住了.数据范围读错还行.

前 $3$ 道题目主要考察读入和输出.

D Integer Cards

• 贪心 + 二分.
• 显然可以随意安排操作的顺序.于是可以给操作按照 $c$ 从大到小排序,那么前面的操作就不会影响后面的操作.
• 于是每次操作的时候贪心选小的替换,替换后直接将那部分删去就可以了.

Copy

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int n,m,a[MAXN];
ll t[MAXN],sum[MAXN];
struct opt
{
	int b,c;
	bool operator < (const opt &rhs) const
	{
		return c>rhs.c;
	}
}q[MAXN];
ll ans=0;
int head,tail;
int bs(int x)
{
	int L=head,R=tail,res=-1;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(a[mid]<x)
			L=mid+1,res=mid;
		else
			R=mid-1;
	}
	return res;
}
int main()
{
	n=read();
	m=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i)
		sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=m;++i)
	{
		q[i].b=read();
		q[i].c=read();
	}
	sort(q+1,q+1+m);
	head=1,tail=n;
	for(int i=1;i<=m;++i)
	{
		int pos=bs(q[i].c);
		if(pos==-1)
			continue;
		int tmp=min(q[i].b,pos-head+1);
		ans+=1LL*tmp*q[i].c;
		head=head+tmp;
	}
	while(head<=tail)
	{
		ans+=a[head];
		++head;
	}
	cout<<ans<<endl;
	return 0;
}

E Cell Distance

• $N\times M\leq 2\times 10^5$ ,我看成 $N,M\leq 2\times 10^5$ 了…
• 考虑一对点 $p,q$ ,它们显然会在 $C^{K-2}_{NM}$ 个方案中被计入贡献.
• 于是只需要枚举每个点,计算它到其他点的距离和,再乘上 $C_{NM}^{K-2}$ ,最后还要除以 $2$ .

F Absolute Minima

• 平衡树 + 线段树.
• 那个 $b$ 显然没什么用,可以单独算.
• 问题就变成可以在数轴上插入点,每次询问到这些点距离和最小的位置与这个距离和.
• 若现在有 $k$ 个点,第一问,显然应该取中位数.这个可以用一颗平衡树维护答案.
• 第二问,把绝对值拆开,只需要询问当前比 $x$ 小的数总和,当前比 $x$ 大的数总和.用了离散化 + 权值线段树.感觉应该有更简单的方法?

Copy

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10;
struct FhqTreap
{
#define rt treap[o]
#define ls treap[treap[o].lson]
#define rs treap[treap[o].rson]
	int x,y,z,ans;
	int idx;
	FhqTreap()
	{
		x=y=z=0;
		idx=0;
	}
	struct node
	{
		int lson,rson,key,weight,size;
	} treap[MAXN];
	inline int newnode(int key)
	{
		++idx;
		treap[idx].size=1;
		treap[idx].weight=rand();
		treap[idx].key=key;
		return idx;
	}
	inline void pushup(int o)
	{
		rt.size=ls.size+rs.size+1;
	}
	void split(int& x,int& y,int key,int o)//小于等于key的分在x中
	{
		if(!o)
			x=y=0;
		else
		{
			if(rt.key<=key)
			{
				x=o;
				split(rt.rson,y,key,rt.rson);
			}
			else
			{
				y=o;
				split(x,rt.lson,key,rt.lson);
			}
			pushup(o);
		}
	}
	int merge(int x,int y)//合并,保证x的权值小于y的权值. key_x<key_y
	{
		if(x==0||y==0)
			return x+y;
		if(treap[x].weight<treap[y].weight)
		{
			treap[x].rson=merge(treap[x].rson,y);
			pushup(x);
			return x;
		}
		else
		{
			treap[y].lson=merge(x,treap[y].lson);
			pushup(y);
			return y;
		}
	}
	inline int Rank(int&root,int key)//get the node (which key equals to the key)'s rank.
	{
		split(x,y,key-1,root);
		ans=treap[x].size+1;
		root=merge(x,y);
		return ans;
	}
	inline int kth(int o,int rank)// find the id of the node which rank is the rank in the tree which root is o.
	{
		while(1)
		{
			if(ls.size>=rank)
				o=rt.lson;//the answer must be in o's lson,search in it.
			else if(ls.size+1==rank)
				return treap[o].key;//o is the rank'th.
			else
			{
				rank-=ls.size+1;
				o=rt.rson;//cannot find in o and o's lson,search in o's rson.
			}
		}
	}
	inline void Insert(int&root,int key)// insert a node which key is the key in whole the tree.
	{
		split(x,y,key,root);
		root=merge(merge(x,newnode(key)),y);
	}
} T;
ll bsum=0;
int Q,k=0,Rt=0;
struct query
{
	int op,a,b;
}q[MAXN];
int A[MAXN],cnt=0;
struct Segtree
{
	struct node
	{
		ll sum,tot;
		int l,r;
	}Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
	void pushup(int o)
	{
		root.sum=lson.sum+rson.sum;
	}
	void BuildTree(int o,int l,int r)
	{
		root.l=l,root.r=r;
		root.sum=0;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid);
		BuildTree(o<<1|1,mid+1,r);
	}
	void upd(int o,int pos,int c)
	{
		int l=root.l,r=root.r;
		if(l==r)
		{
			root.sum+=c;
			return;
		}
		int mid=(l+r)>>1;
		if(pos<=mid)
			upd(o<<1,pos,c);
		else
			upd(o<<1|1,pos,c);
		pushup(o);
	}
	ll query(int o,int L,int R)
	{
		if(L>R)
			return 0;
		int l=root.l,r=root.r;
		if(L<=l && r<=R)
			return root.sum;
		ll res=0;
		int mid=(l+r)>>1;
		if(L<=mid)
			res+=query(o<<1,L,R);
		if(R>mid)
			res+=query(o<<1|1,L,R);
		return res;
	}
}Seg;
int rnk(int x)
{
	return lower_bound(A+1,A+1+cnt,x)-A;
}
int main()
{
	Q=read();
	for(int i=1;i<=Q;++i)
	{
		q[i].op=read();
		if(q[i].op==1)
		{
			A[++cnt]=q[i].a=read();
			q[i].b=read();
		}
	}
	sort(A+1,A+1+cnt);
	cnt=unique(A+1,A+1+cnt)-(A+1);
	Seg.BuildTree(1,1,cnt);
	for(int i=1;i<=Q;++i)
	{
		if(q[i].op==1)
		{
			int a=q[i].a,b=q[i].b;
			++k;
			bsum+=b;
			Seg.upd(1,rnk(a),a);
			T.Insert(Rt,a);
		}
		else
		{
			int rk=(k+1)>>1;
			int x=T.kth(Rt,rk);
			rk=T.Rank(Rt,x);
			int pos=rnk(x);
			ll res=1LL*(rk-1)*x-Seg.query(1,1,pos-1)-1LL*(k-rk+1)*x+Seg.query(1,pos,cnt);
			printf("%d %lld\n",x,res+bsum);
		}
	}
	return 0;
}