Atcoder Beginner Contest 127

Posted on | Edited on | Views:

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

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

D Integer Cards

  • 贪心 + 二分.
  • 显然可以随意安排操作的顺序.于是可以给操作按照 $c$ 从大到小排序,那么前面的操作就不会影响后面的操作.
  • 于是每次操作的时候贪心选小的替换,替换后直接将那部分删去就可以了.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#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$ 大的数总和.用了离散化 + 权值线段树.感觉应该有更简单的方法?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#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;
}