Codeforces Round #665 (Div.2)

比赛链接 / 官方题解链接

橙名留念！

A. Distance and Axis

Solution

不动 $A$ 点的话，距离差最大就是 $x_A$，所以如果 $k>x_A$，把 $A$ 移动 $k-x_A$ 就好。

如果 $k<x_A$，如果 $k$ 与 $x_A$ 同奇偶，那么一定可以找到这么个 $k$；否则 $A$ 需要挪一格。

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int main(){
	int T; for(read(T); T; T--){
		int n, k; read(n, k);
		if(k >= n)	printf("%d\n", k - n);
		else	printf("%d\n", ((n ^ k) & 1));
	}
	return 0;
}

---

B. Ternary Sequence

Solution

考虑 $b$ 序列，它的 $2$ 一定是优先去和 $a$ 的 $0$ 去匹配，多了的拿去和 $a$ 的 $2$ 匹配，再多就只能和 $a$ 的 $1$ 匹配了。稍微分类讨论一下就解决了。

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

int main(){
	int T; for(read(T); T; T--){
		int x1, y1, z1, x2, y2, z2; read(x1, y1, z1, x2, y2, z2);
		int ans = 0;
		if(z2 >= x1 + z1){
			printf("%d\n", -(z2 - x1 - z1) * 2);
			continue;
		}
		else if(z2 >= x1){
			z2 -= x1; z1 -= z2;
			printf("%d\n", 2 * min(y2, z1));
		}
		else	printf("%d\n", 2 * min(y2, z1));
	}
	return 0;
}

---

C. Mere Array

Solution

设最小值为 $mn$，那么所有 $mn$ 的倍数都可以以 $mn$ 作为“桥梁”任意交换位置，所以 $mn$ 的倍数们一定可以排成有序的。这之后再检验一下整个序列是否有序即可。

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;

int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); }

int n, a[N];

int main(){
	int T; for(read(T); T; T--){
		read(n);
		int mn = 1e9 + 1;
		for(int i = 1; i <= n; i++){
			read(a[i]);
			mn = min(mn, a[i]);
		}
		vi v;
		for(int i = 1; i <= n; i++){
			if(a[i] % mn == 0){
				v.pb(a[i]);
				a[i] = 0;
			}
		}
		sort(v.begin(), v.end());
		int pos = 1;
		for(auto &k : v){
			while(pos <= n && a[pos])	pos++;
			a[pos] = k;
		}
		bool ok = true;
		for(int i = 2; i <= n; i++){
			if(a[i] < a[i-1]){
				ok = false;
				break;
			}
		}
		puts(ok ? "YES" : "NO");
	}
	return 0;
}

---

D. Maximum Distributed Tree

Solution

显然是考虑每条边的贡献——一条边的贡献就是它两端连接的子树大小乘积，记为 $w$。于是乎，$\text{ANS}=\sum_{i=1}^{n-1}w_ia_i$，$a_i$ 就是我们为这条边分配的值。首先根据排序不等式易知，要想答案最大，一定是最大的 $w$ 配最大的 $a$，最小的 $w$ 配最小的 $a$。其次贪心很容易证明：如果质因数个数超过了 $n-1$，就把最大的几个质因数乘起来，这样答案最大。问题解决。

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;
const LL MOD = 1e9+7;

int n, m;
vi edge[N];

LL p[N], w[N], sz[N];
void dfs(int x, int f){
	sz[x] = 1;
	for(auto &to : edge[x]){
		if(to == f)	continue;
		dfs(to, x);
		sz[x] += sz[to];
	}
	w[x] = sz[x] * (n - sz[x]);
}

inline void initCASES(){
	for(int i = 1; i <= n; i++){
		edge[i].clear();
		p[i] = w[i] = sz[i] = 0;
	}
}

int main(){
	int T; for(read(T); T; T--){
		read(n);
		initCASES();
		for(int i = 1; i < n; i++){
			int u, v; read(u, v);
			edge[u].pb(v), edge[v].pb(u);
		}
		dfs(n, 0);
		n--;
		sort(w+1, w+n+1);
		read(m);
		vector<LL> p(m);
		for(int i = 0; i < m; i++)	read(p[i]);
		sort(p.begin(), p.end()), reverse(p.begin(), p.end());
		int size = p.size();
		while(size < n)	p.pb(1), size++;
		reverse(p.begin(), p.end());
		LL ans = 0;
		for(int i = 1; i <= n; i++){
			if(i == n){
				LL prod = 1;
				for(int j = n - 1; j < size; j++)	(prod *= p[j]) %= MOD;
				(ans += prod * w[i] % MOD) %= MOD;
			}
			else	(ans += w[i] * p[i-1]) %= MOD;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

---

E. Divide Square

Solution

有两种情况会使答案加一：有一条贯穿整个矩形的直线，或两条直线在矩形内部产生一个交点。

换句话说，答案等于贯穿矩形的直线数量加上矩形内部交点的数量。

前者很好求，对于后者，把所有水平直线按左端点排序，把所有竖直直线按横坐标排序，枚举竖直直线的同时一个优先队列存储能与之产生交点的水平直线有哪些，在线段树中维护它们的纵坐标，于是在线段树中就可以查询交点数了。

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;
const int M = 1000005;

struct segTree{
	int l, r; LL sum;
}tr[M<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
#define len(id) (tr[id].r - tr[id].l + 1)
inline void pushup(int id){
	tr[id].sum = tr[lid].sum + tr[rid].sum;
}
void build(int id, int l, int r){
	tr[id].l = l, tr[id].r = r, tr[id].sum = 0;
	if(l == r)	return;
	build(lid, l, mid), build(rid, mid+1, r);
	pushup(id);
}
void add(int id, int pos, LL val){
	if(tr[id].l == tr[id].r){
		tr[id].sum += val;
		return;
	}
	if(pos <= mid)	add(lid, pos, val);
	else	add(rid, pos, val);
	pushup(id);
}
int sum(int id, int l, int r){
	if(tr[id].l == l && tr[id].r == r)
		return tr[id].sum;
	if(r <= mid)	return sum(lid, l, r);
	else if(l > mid)	return sum(rid, l, r);
	else	return sum(lid, l, mid) + sum(rid, mid+1, r);
}

struct Horizontal{
	int y, lx, rx;
	bool operator < (const Horizontal &A) const{
		return lx < A.lx;
	}
}h[N];
struct Vertical{
	int x, ly, ry;
	bool operator < (const Vertical &A) const{
		return x < A.x;
	}
}v[N];

struct Node{
	int val, id;
	bool operator < (const Node &A) const{
		return val > A.val;
	}
};

int main(){
	build(1, 0, 1e6);
	int n, m; read(n, m);
	LL ans = 1;
	for(int i = 1; i <= n; i++){
		read(h[i].y, h[i].lx, h[i].rx);
		ans += h[i].lx == 0 && h[i].rx == 1e6;
	}
	for(int i = 1; i <= m; i++){
		read(v[i].x, v[i].ly, v[i].ry);
		ans += v[i].ly == 0 && v[i].ry == 1e6;
	}
	sort(h+1, h+n+1), sort(v+1, v+m+1);
	priority_queue<Node> q;
	int pt = 0;
	for(int i = 1; i <= m; i++){
		while(pt < n && h[pt+1].lx <= v[i].x){
			pt++;
			add(1, h[pt].y, 1);
			q.push((Node){h[pt].rx, pt});
		}
		while(!q.empty() && h[q.top().id].rx < v[i].x){
			add(1, h[q.top().id].y, -1);
			q.pop();
		}
		ans += sum(1, v[i].ly, v[i].ry);
	}
	printf("%lld\n", ans);
	return 0;
}

---

F. Reverse and Swap

Solution

考虑线段树维护原序列，设线段树从上往下是第 $0$ 层、第 $1$ 层、……第 $n$ 层。容易发现，$Swap(k)$ 操作就是给第 $n-k-1$ 层的所有节点打上子树交换标记，而 $Reverse(k)$ 操作就是给第 $n-k$ 到第 $n$ 层的所有节点打上子树交换标记。既然如此，我们就记录一下每一层的标记状况，修改或查询的时候按照标记状况决定往左子树还是右子树走——原本该往左子树走的，如果有标记，就往右子树的对应区间走；原本该往右子树走的，如果有标记，就往左子树的对应区间走。换句话说，序列还是原来那个顺序，我们把对序列的操作变成了对操作区间的操作，如此解决问题。

Code

#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 550005;

int n, q;
LL a[N];
int tag[N], lg[N<<2];

struct segTree{
	LL sum;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((l + r) >> 1)
inline void pushup(int id){
	tr[id].sum = tr[lid].sum + tr[rid].sum;
}
void build(int id, int l, int r){
	tr[id].sum = 0;
	if(l == r){
		tr[id].sum = a[l];
		return;
	}
	build(lid, l, mid), build(rid, mid+1, r);
	pushup(id);
}
void replace(int id, int l, int r, int pos, LL val){
	if(l == r){
		tr[id].sum = val;
		return;
	}
	if(pos <= mid){
		if(!tag[lg[id]])	replace(lid, l, mid, pos, val);
		else	replace(rid, mid+1, r, r-mid+pos, val);
	}
	else{
		if(!tag[lg[id]])	replace(rid, mid+1, r, pos, val);
		else	replace(lid, l, mid, pos-mid-1+l, val);
	}
	pushup(id);
}
LL sum(int id, int l, int r, int ql, int qr){
	if(l == ql && r == qr)	return tr[id].sum;
	if(qr <= mid){
		if(!tag[lg[id]])	return sum(lid, l, mid, ql, qr);
		else	return sum(rid, mid+1, r, r-mid+ql, r-mid+qr);
	}
	else if(ql > mid){
		if(!tag[lg[id]])	return sum(rid, mid+1, r, ql, qr);
		else	return sum(lid, l, mid, ql-mid-1+l, qr-mid-1+l);
	}
	else{
		if(!tag[lg[id]])
			return sum(lid, l, mid, ql, mid) + sum(rid, mid+1, r, mid+1, qr);
		else
			return sum(rid, mid+1, r, r-mid+ql, r) + sum(lid, l, mid, l, qr-mid-1+l);
	}
}

int main(){
	read(n, q);
	lg[1] = 0; for(int i = 2; i < (1 << (n + 1)); i++) lg[i] = lg[i/2] + 1;
	for(int i = 1; i <= (1 << n); i++)	read(a[i]);
	build(1, 1, 1<<n);
	while(q--){
		int opt; read(opt);
		if(opt == 1){
			int x, k; read(x, k);
			replace(1, 1, 1<<n, x, k);
		}
		else if(opt == 2){
			int k; read(k);
			for(int i = n - k; i <= n; i++)	tag[i] ^= 1;
		}
		else if(opt == 3){
			int k; read(k);
			tag[n-k-1] ^= 1;
		}
		else{
			int l, r; read(l, r);
			printf("%lld\n", sum(1, 1, 1<<n, l, r));
		}
	}
	return 0;
}