What is Piggy's optimal strategy?

What does $$$2l \le r$$$ mean?

#include <bits/stdc++.h>
using namespace std;

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%d\n", __lg(r));
	}
	return 0;
}

Consider each bit separately.

Calculate the time when the $$$d$$$-th bit of $$$a_n$$$ becomes $$$1$$$.

The answer is the bitwise OR of the range $$$[\max(0, n - m), n + m]$$$. Let's figure out how to calculate the bitwise OR of the range $$$[l, r]$$$.

We can consider each bit separately. If the $$$d$$$-th bit of $$$l$$$ is $$$1$$$ or the $$$d$$$-th bit of $$$r$$$ is $$$1$$$, then the $$$d$$$-th bit of the answer is $$$1$$$.

Otherwise, if $$$\left\lfloor\frac{l}{2^{d + 1}}\right\rfloor \ne \left\lfloor\frac{r}{2^{d + 1}}\right\rfloor$$$, then the $$$d$$$-th bit has been flipped at least twice from $$$l$$$ to $$$r$$$, so in this case the $$$d$$$-th bit of the answer is also $$$1$$$.

Time complexity: $$$O(\log (n + m))$$$ per test case.

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

void solve() {
	ll n, m;
	scanf("%lld%lld", &n, &m);
	ll ans = 0;
	for (int i = 0; i <= 30; ++i) {
		ll x = n & ((1LL << (i + 1)) - 1);
		ll t = (1LL << i) - x;
		if (n >= (1LL << i)) {
			t = min(t, x + 1);
		}
		if (x >= (1LL << i) || t <= m) {
			ans |= (1LL << i);
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

void solve() {
	ll n, m;
	scanf("%lld%lld", &n, &m);
	ll l = max(0LL, n - m), r = n + m, ans = 0;
	for (int i = 31; ~i; --i) {
		if ((l & (1LL << i)) || (r & (1LL << i)) || (l >> (i + 1)) != (r >> (i + 1))) {
			ans |= (1LL << i);
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Figure out the case where $$$a'_1 \ne -1, a'_n \ne -1$$$ and $$$a'_2 = a'_3 = \cdots = a'_{n - 1} = -1$$$ first.

Imagine a full binary tree. Consider the sequence as a walk on the full binary tree.

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;

int n, a[maxn];

inline vector<int> path(int x, int y) {
	vector<int> L, R;
	while (__lg(x) > __lg(y)) {
		L.pb(x);
		x >>= 1;
	}
	while (__lg(y) > __lg(x)) {
		R.pb(y);
		y >>= 1;
	}
	while (x != y) {
		L.pb(x);
		R.pb(y);
		x >>= 1;
		y >>= 1;
	}
	L.pb(x);
	reverse(R.begin(), R.end());
	for (int x : R) {
		L.pb(x);
	}
	return L;
}

void solve() {
	scanf("%d", &n);
	int l = -1, r = -1;
	vector<int> vc;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		if (a[i] != -1) {
			if (l == -1) {
				l = i;
			}
			r = i;
			vc.pb(i);
		}
	}
	if (l == -1) {
		for (int i = 1; i <= n; ++i) {
			printf("%d%c", (i & 1) + 1, " \n"[i == n]);
		}
		return;
	}
	for (int i = l - 1; i; --i) {
		a[i] = (((l - i) & 1) ? a[l] * 2 : a[l]);
	}
	for (int i = r + 1; i <= n; ++i) {
		a[i] = (((i - r) & 1) ? a[r] * 2 : a[r]);
	}
	for (int _ = 1; _ < (int)vc.size(); ++_) {
		int l = vc[_ - 1], r = vc[_];
		vector<int> p = path(a[l], a[r]);
		if (((int)p.size() & 1) != ((r - l + 1) & 1) || r - l + 1 < (int)p.size()) {
			puts("-1");
			return;
		}
		for (int i = 0; i < (int)p.size(); ++i) {
			a[l + i] = p[i];
		}
		for (int i = l + (int)p.size(), o = 1; i <= r; ++i, o ^= 1) {
			a[i] = (o ? a[i - 1] * 2 : a[i - 1] / 2);
		}
	}
	for (int i = 1; i <= n; ++i) {
		printf("%d%c", a[i], " \n"[i == n]);
	}
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

$$$a_i$$$ should take different primes.

Transform it into a graph problem.

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 4000100;
const int N = 1000000;

int n, a[maxn], pr[maxn], tot, stk[maxn], top;
bool vis[maxn];

inline void init() {
	for (int i = 2; i <= N; ++i) {
		if (!vis[i]) {
			pr[++tot] = i;
		}
		for (int j = 1; j <= tot && i * pr[j] <= N; ++j) {
			vis[i * pr[j]] = 1;
			if (i % pr[j] == 0) {
				break;
			}
		}
	}
	mems(vis, 0);
}

inline bool check(int x) {
	if (x & 1) {
		return x + 1 + x * (x - 1) / 2 >= n;
	} else {
		return x * (x - 1) / 2 - x / 2 + 2 + x >= n;
	}
}

vector<pii> G[10000];

void dfs(int u) {
	while (G[u].size()) {
		pii p = G[u].back();
		G[u].pop_back();
		if (vis[p.scd]) {
			continue;
		}
		vis[p.scd] = 1;
		dfs(p.fst);
	}
	stk[++top] = pr[u];
}

void solve() {
	scanf("%d", &n);
	int l = 1, r = 10000, ans = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	for (int i = 1; i <= ans; ++i) {
		vector<pii>().swap(G[i]);
	}
	int tot = 0;
	for (int i = 1; i <= ans; ++i) {
		for (int j = i; j <= ans; ++j) {
			if (ans % 2 == 0 && i % 2 == 0 && i + 1 == j) {
				continue;
			}
			G[i].pb(j, ++tot);
			G[j].pb(i, tot);
		}
	}
	for (int i = 1; i <= tot; ++i) {
		vis[i] = 0;
	}
	top = 0;
	dfs(1);
	reverse(stk + 1, stk + top + 1);
	for (int i = 1; i <= n; ++i) {
		printf("%d%c", stk[i], " \n"[i == n]);
	}
}

int main() {
	init();
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

Stop thinking about Boruvka.

Most of the edges in the graph are useless.

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 1000100;

int n, lsh[maxn], tot, fa[maxn];
pii b[maxn];

struct node {
	int l, r, x;
} a[maxn];

struct edg {
	int u, v, d;
	edg(int a = 0, int b = 0, int c = 0) : u(a), v(b), d(c) {}
} E[maxn];

int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline bool merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x != y) {
		fa[x] = y;
		return 1;
	} else {
		return 0;
	}
}

void solve() {
	tot = 0;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i].l >> a[i].r >> a[i].x;
		lsh[++tot] = a[i].l;
		lsh[++tot] = (++a[i].r);
	}
	int m = 0;
	sort(lsh + 1, lsh + tot + 1);
	tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
	for (int i = 1; i <= n; ++i) {
		a[i].l = lower_bound(lsh + 1, lsh + tot + 1, a[i].l) - lsh;
		a[i].r = lower_bound(lsh + 1, lsh + tot + 1, a[i].r) - lsh;
		b[++m] = mkp(a[i].l, i);
		b[++m] = mkp(a[i].r, -i);
	}
	set<pii> S;
	sort(b + 1, b + m + 1);
	int tt = 0;
	for (int i = 1; i <= m; ++i) {
		int j = b[i].scd;
		if (j > 0) {
			auto it = S.insert(mkp(a[j].x, j)).fst;
			if (it != S.begin()) {
				int k = prev(it)->scd;
				E[++tt] = edg(j, k, abs(a[j].x - a[k].x));
			}
			if (next(it) != S.end()) {
				int k = next(it)->scd;
				E[++tt] = edg(j, k, abs(a[j].x - a[k].x));
			}
		} else {
			j = -j;
			S.erase(mkp(a[j].x, j));
		}
	}
	for (int i = 1; i <= n; ++i) {
		fa[i] = i;
	}
	sort(E + 1, E + tt + 1, [&](const edg &a, const edg &b) {
		return a.d < b.d;
	});
	ll ans = 0, cnt = 0;
	for (int i = 1; i <= tt; ++i) {
		if (merge(E[i].u, E[i].v)) {
			++cnt;
			ans += E[i].d;
		}
	}
	cout << (cnt == n - 1 ? ans : -1) << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

Try some dp that takes $$$O(n^2)$$$ time.

What's the maximum MEX in the optimal good set of paths?

TBD

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
 
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
 
const int maxn = 25050;
const int inf = 0x3f3f3f3f;
 
int n, m, a[maxn], f[maxn][4000];
vector<int> G[maxn];
 
void dfs(int u) {
	if (G[u].empty()) {
		for (int i = 1; i <= m; ++i) {
			f[u][i] = (i == a[u] ? inf : i);
		}
		return;
	}
	if ((int)G[u].size() == 1) {
		int v = G[u][0];
		dfs(v);
		int mn = inf;
		for (int i = 1; i <= m; ++i) {
			if (i != a[u]) {
				mn = min(mn, f[v][i]);
			}
		}
		for (int i = 1; i <= m; ++i) {
			f[u][i] = min(f[v][i], mn + (u > 1 ? i : 0));
		}
		if (a[u] <= m) {
			f[u][a[u]] = inf;
		}
		return;
	}
	int v = G[u][0], w = G[u][1], mn1 = inf, mn2 = inf, mn3 = inf;
	dfs(v);
	dfs(w);
	for (int i = 1; i <= m; ++i) {
		if (i != a[u]) {
			mn1 = min(mn1, f[v][i] + f[w][i] - i);
			mn2 = min(mn2, f[v][i]);
			mn3 = min(mn3, f[w][i]);
		}
	}
	for (int i = 1; i <= m; ++i) {
		f[u][i] = min({mn1 + (u > 1 ? i : 0), mn2 + mn3 + (u > 1 ? i : 0), mn2 + f[w][i], mn3 + f[v][i]});
	}
	if (a[u] <= m) {
		f[u][a[u]] = inf;
	}
}
 
void solve() {
	scanf("%d", &n);
	m = min(n + 1, 3863);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		vector<int>().swap(G[i]);
	}
	for (int i = 2, p; i <= n; ++i) {
		scanf("%d", &p);
		G[p].pb(i);
	}
	dfs(1);
	printf("%d\n", *min_element(f[1] + 1, f[1] + m + 1));
}
 
int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
namespace my_std{
	#define ll long long
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 1e18
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
#define LC tree[x].lc
#define RC tree[x].rc
set<ll> s[25025];
ll t,n,a[25025],ch[25025][2],ans=inf;
ll rt[25025],tot=0,val1[25025],val2[25025];
struct node{
	ll minn,lc,rc,lz,lzmin;
	il void addtag(ll v,ll minv,ll l){
		minn=min(minn+v,minv+l);
		lz+=v;
		lzmin=min(lzmin+v,minv);
	}
}tree[7000070];
il void pushup(ll x){
	tree[x].minn=min(tree[LC].minn,tree[RC].minn);
}
il ll newnode(){
	tree[++tot]=(node){(ll)inf,0,0,0,(ll)inf};
	return tot;
}
il void pushdown(ll x,ll l,ll r){
	if(!LC) LC=newnode();
	if(!RC) RC=newnode();
	ll mid=(l+r)>>1;
	tree[LC].addtag(tree[x].lz,tree[x].lzmin,l);
	tree[RC].addtag(tree[x].lz,tree[x].lzmin,mid+1);
	tree[x].lz=0;
	tree[x].lzmin=inf;
}
void upd(ll &x,ll l,ll r,ll pos,ll v){
	if(!x) x=newnode();
	if(l==r){
		tree[x].minn=v;
		return;
	}
	ll mid=(l+r)>>1;
	pushdown(x,l,r);
	if(pos<=mid) upd(LC,l,mid,pos,v);
	else upd(RC,mid+1,r,pos,v);
	pushup(x);
}
void mdf(ll &x,ll l,ll r,ll ql,ll qr,ll v){
	if(ql>qr) return;
	if(!x) x=newnode();
	if(ql<=l&&r<=qr){
		tree[x].addtag(v,(ll)inf,l);
		return;
	}
	ll mid=(l+r)>>1;
	pushdown(x,l,r);
	if(ql<=mid) mdf(LC,l,mid,ql,qr,v);
	if(mid<qr) mdf(RC,mid+1,r,ql,qr,v);
	pushup(x);
}
void mdf2(ll &x,ll l,ll r,ll ql,ll qr,ll v){
	if(ql>qr) return;
	if(!x) x=newnode();
	if(ql<=l&&r<=qr){
		tree[x].addtag(0,v,l);
		return;
	}
	ll mid=(l+r)>>1;
	pushdown(x,l,r);
	if(ql<=mid) mdf2(LC,l,mid,ql,qr,v);
	if(mid<qr) mdf2(RC,mid+1,r,ql,qr,v);
	pushup(x);
}
ll query(ll x,ll l,ll r,ll pos){
	if(l==r) return tree[x].minn;
	ll mid=(l+r)>>1;
	pushdown(x,l,r);
	if(pos<=mid) return query(LC,l,mid,pos);
	else return query(RC,mid+1,r,pos);
}
void dfs(ll u){
	if(!ch[u][0]){
		mdf2(rt[u],1,n+1,1,n+1,0);
		if(a[u]<=(n+1)){
			upd(rt[u],1,n+1,a[u],(ll)inf);
			s[u].insert(a[u]);
		}
		return;
	}
	else if(!ch[u][1]){
		dfs(ch[u][0]);
		rt[u]=rt[ch[u][0]];
		swap(s[u],s[ch[u][0]]);
		if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u],(ll)inf);
		ll minn=tree[rt[u]].minn;
		mdf2(rt[u],1,n+1,1,n+1,minn);
		if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u],(ll)inf);
		if(u==1) ans=min(ans,tree[rt[u]].minn);
		if(a[u]<=(n+1)) s[u].insert(a[u]);
		return;
	}
	else{
		ll x=ch[u][0],y=ch[u][1];
		dfs(x);
		dfs(y);
		if(s[x].size()<s[y].size()) swap(x,y);
		if(a[u]<=(n+1)){
			upd(rt[x],1,n+1,a[u],(ll)inf);
			upd(rt[y],1,n+1,a[u],(ll)inf);
			s[x].insert(a[u]);
			s[y].insert(a[u]);
		}
		ll minn1=tree[rt[x]].minn,minn2=tree[rt[y]].minn,minn=minn1+minn2;
		for(set<ll>::iterator it=s[y].begin();it!=s[y].end();it++){
			ll pos=*it;
			val1[pos]=query(rt[x],1,n+1,pos);
			val2[pos]=query(rt[y],1,n+1,pos);
			minn=min(minn,val1[pos]+val2[pos]-pos);
			upd(rt[x],1,n+1,pos,(ll)inf);
		}
		ll mex=1;
		while(s[y].find(mex)!=s[y].end()) mex++;
		ll k=query(rt[y],1,n+1,mex)-mex;
		minn=min(minn,tree[rt[x]].minn+k);
		rt[u]=rt[x];
		mdf(rt[u],1,n+1,1,n+1,minn2);
		mdf2(rt[u],1,n+1,1,n+1,minn1+k);
		swap(s[u],s[x]);
		for(set<ll>::iterator it=s[y].begin();it!=s[y].end();it++){
			ll pos=*it;
			upd(rt[u],1,n+1,pos,min(minn1+val2[pos],minn2+val1[pos]));
			s[u].insert(pos);
		}
		mdf2(rt[u],1,n+1,1,n+1,minn);
		if(u==1){
			ans=min(ans,minn);
			ans=min(ans,tree[rt[u]].minn);
		}
		if(a[u]<=(n+1)) upd(rt[u],1,n+1,a[u],(ll)inf);
	}
}
il void clr(){
	fr(i,1,n) ch[i][0]=ch[i][1]=0;
	fr(i,1,n) s[i].clear();
	fr(i,1,n) rt[i]=0;
	tot=0;
	ans=inf;
}
int main(){
	t=read();
	while(t--){
		n=read();
		fr(i,1,n) a[i]=read();
		fr(i,2,n){
			ll x=read();
			if(!ch[x][0]) ch[x][0]=i;
			else ch[x][1]=i;
		}
		tree[0]=(node){(ll)inf,0,0,0,(ll)inf};
		dfs(1);
		writeln(ans);
		clr();
	}
}
/*
1
5
3 2 2 1 1
1 1 2 2
ans:
4
*/