First approach: Optimize the straightforward solution.

Multiply instead of divide. What happens to the last digit when multiplying?

Consider islands of two colours and the bridges between them.

Iterate over all possible combination, order and direction of extra edges.

First approach: 2D segment tree (or quadtree) with a set or vector on each node, representing the set of barriers that cover this node.

#include <bits/stdc++.h>
using namespace std;
#define Maxn 4000007
bool vis[Maxn];
int a[4007],b[4007],n;
int main()
{
	scanf("%d",&n);
	memset(vis,false,sizeof(vis));
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		vis[a[i]]=true;
	}
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		vis[b[i]]=true;
	}
	int ans=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			if (vis[a[i]^b[j]]) ++ans;
	if (ans%2==0) printf("Karen\n"); else printf("Koyomi\n");
	return 0;
}

#include <stdio.h>

int main()
{
    puts("Karen");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
long long L,R;
int ans;
int main()
{
	scanf("%lld%lld",&L,&R);
	if (R-L>=10) printf("%d\n",0);
	else
	{
		ans=1;
		for (long long i=L+1;i<=R;i++)
			ans=(1LL*ans*(i%10))%10;
		printf("%d\n",ans);
	}
	return 0;
}

#include <bits/stdc++.h>
#define Maxn 5007
#define modp 998244353
int p[Maxn][Maxn];
int pre[Maxn];
int a,b,c;
int solve(int x,int y)
{
	int res=0;
	for (int k=0;k<=x&&k<=y;k++)
	{
		int del=pre[k];
		del=(1LL*del*p[x][k])%modp;
		del=(1LL*del*p[y][k])%modp;
		res=(res+del)%modp;
	}
	return res;
}
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	memset(p,0,sizeof(p));
	p[0][0]=1;
	for (int i=1;i<=5000;i++)
	{
		p[i][0]=1;
		for (int j=1;j<=i;j++)
			p[i][j]=(p[i-1][j-1]+p[i-1][j])%modp;
	}
	memset(pre,0,sizeof(pre));
	pre[0]=1;
	for (int i=1;i<=5000;i++)
		pre[i]=(1LL*pre[i-1]*i)%modp;
	int ans=1;
	ans=(1LL*ans*solve(a,b))%modp;
	ans=(1LL*ans*solve(b,c))%modp;
	ans=(1LL*ans*solve(a,c))%modp;
	printf("%d\n",ans);
	return 0;
}

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>

using namespace std;

const int MAXN=255;

const int Mod=1000000007;
inline void add_mod(int &x,int y)
{
    x=(x+y<Mod ? x+y : x+y-Mod);
}

int u[MAXN],v[MAXN];

map<int,int> mp;
inline int get_id(int x)
{
    if(!mp[x])mp[x]=(int)mp.size();
    return mp[x];
}

vector<int> e[MAXN];
void add_edge(int u,int v)
{
    e[u].push_back(v);
    e[v].push_back(u);
}

inline int cal_size(int u,int n,int d)
{
    int t=u,c=0,res;
    while(t)c++,t>>=1;
    res=(1<<(d-c+1))-1,t=c;
    while(t<d)t++,u=u<<1|1;
    return res-max(min(u-n,1<<(d-c)),0);
}

int num[MAXN];
void pre_dp(int u,int f)
{
    for(auto &v:e[u])
    {
        if(v==f)continue;
        num[u]-=num[v];
        pre_dp(v,u);
    }
}

int vis[MAXN];
void dfs(int u,int &tot)
{
    add_mod(tot,num[u]);
    vis[u]=1;
    for(auto &v:e[u])
        if(!vis[v])dfs(v,tot);
    vis[u]=0;
}

int main()
{
    int n,m,d=0;
    scanf("%d%d",&n,&m);
    while((1<<d)<=n)d++;
    get_id(1);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        int t=u[i];
        while(t)get_id(t),t>>=1;
        t=v[i];
        while(t)get_id(t),t>>=1;
    }
    for(auto &t:mp)
    {
        int u=t.first,id=t.second;
        if(u>1)add_edge(get_id(u),get_id(u>>1));
        num[id]=cal_size(u,n,d);
    }
    pre_dp(1,0);
    for(int i=0;i<m;i++)
        add_edge(get_id(u[i]),get_id(v[i]));
    int res=0;
    for(int i=1;i<=(int)mp.size();i++)
    {
        int tot=0;
        dfs(i,tot);
        add_mod(res,1LL*tot*num[i]%Mod);
    }
    printf("%d\n",res);
    return 0;
}

#include <bits/stdc++.h>

#define rep(i, x, y) for (int i = (x), _ = (y); i <= _; ++i)
#define down(i, x, y) for (int i = (x) - 1, _ = (y); i >= _; --i)
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define bin(x) (1<<(x))
//#define LX_JUDGE

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

template<typename T> inline void upmax(T &x, T y) { x < y ? x = y : 0; }
template<typename T> inline void upmin(T &x, T y) { x > y ? x = y : 0; }

template<typename T> inline void read(T &x) {
	char c;
	while ((c = getchar()) < '0' or c > '9');
	for (x = c - '0'; (c = getchar()) >= '0' and c <= '9'; x = x * 10 + c - '0');
}

const int inf = 0x3f3f3f3f;
const int MAX_N = 2500;

struct Data {
	int u, d, id;
	Data() {}
	Data(int u, int d, int id) : u(u), d(d), id(id) {}
};

class SegmentTree {
	map<pii, int> G;
	int n, pcnt;
	vector<Data> H[MAX_N * 4 + 255];
#define ls (o << 1)
#define rs (o << 1 | 1)

	int _l, _r, _u, _d, _id;

	void ins(int o, int l, int r) {
		if (_l <= l and r <= _r) {
			//printf("%d %d %d %d\n", l, r, _u, _d);
			H[o].pb(Data(_u, _d, _id));
			return ;
		}
		int m = (l + r) / 2;
		if (_l <= m) ins(ls, l, m);
		if (m < _r) ins(rs, m + 1, r);
	}
	void del(int o, int l, int r) {
		if (_l <= l and r <= _r) {
			for (vector<Data>::iterator it = H[o].begin(); it != H[o].end(); it++) {
				if (it->id == _id) {
					H[o].erase(it);
					break ;
				}
			}
			return ;
		}
		int m = (l + r) / 2;
		if (_l <= m) del(ls, l, m);
		if (m < _r) del(rs, m + 1, r);
	}
	inline int _ask(const vector<Data> &q, int h) {
		int best = inf, ans = -1;
		for (auto to : q) {
			if (to.u <= h and h <= to.d and to.d - to.u < best) {
				best = to.d - to.u;
				ans = to.id;
			}
		}
		return ans;
	}
	int ask(int o, int l, int r) {
		if (l == r) return _ask(H[o], _u);
		int m = (l + r) / 2;
		int ans = m >= _l ? ask(ls, l, m) : ask(rs, m + 1, r);
		return ans < 0 ? _ask(H[o], _u) : ans;
	}
#undef ls
#undef rs
public :
	void init(int n) {
		this->n = n;
		pcnt = 1;
	}
	void ins(int l, int u, int r, int d) {
		G[mp(l, u)] = _id = pcnt++;
		_l = l, _r = r, _u = u, _d = d;
		ins(1, 1, n);
	}
	void del(int l, int u, int r, int d) {
		_id = G[mp(l, u)];
		G.erase(mp(l, u));
		_l = l, _r = r;
		del(1, 1, n);
	}
	int ask(int x, int y) {
		_l = x, _u = y;
		return ask(1, 1, n);
	}
} my;

int main() {
	int n, m, Q;
	read(n), read(m), read(Q);
	my.init(2500); // FIX ME
	int opt, r1, c1, r2, c2;
	while (Q--) {
		read(opt), read(r1), read(c1), read(r2), read(c2);
		if (opt == 3) {
			//int a = my.ask(r1, c1), b = my.ask(r2, c2);
			//printf("%d %d\n", a, b);
			puts(my.ask(r1, c1) == my.ask(r2, c2) ? "Yes" : "No");
		} else if (opt == 1) {
			my.ins(r1, c1, r2, c2);
		} else {
			my.del(r1, c1, r2, c2);
		}
	}
	return 0;
}

#include <bits/stdc++.h>
#define Maxn 2507
using namespace std;
int n,m,q;
map<pair<pair<int,int>,pair<int,int> >,pair<unsigned long long,unsigned long long> > mp;
pair<unsigned long long,unsigned long long> s[Maxn][Maxn];
void add(int x,int y,pair<unsigned long long,unsigned long long> del)
{
	for (int kx=x;kx<=2503;kx+=kx&(-kx))
		for (int ky=y;ky<=2503;ky+=ky&(-ky))
		{
			s[kx][ky].first+=del.first;
			s[kx][ky].second+=del.second;
		}
}
pair<unsigned long long,unsigned long long> query(int x,int y)
{
	pair<unsigned long long,unsigned long long> res=make_pair(0,0);
	for (int kx=x;kx;kx-=kx&(-kx))
		for (int ky=y;ky;ky-=ky&(-ky))
		{
			res.first+=s[kx][ky].first;
			res.second+=s[kx][ky].second;
		}
	return res;
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	memset(s,0,sizeof(s));
	srand(20001206);
	mp.clear();
	for (int i=1;i<=q;i++)
	{
		int t,r1,c1,r2,c2;
		scanf("%d%d%d%d%d",&t,&r1,&c1,&r2,&c2);
		pair<unsigned long long,unsigned long long> del,udel;
		if (t==1)
		{
			del.first=rand();
			del.second=rand();
			udel=make_pair(-del.first,-del.second);
			mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))]=del;
			add(r1,c1,del);
			add(r1,c2+1,udel);
			add(r2+1,c1,udel);
			add(r2+1,c2+1,del);
		} else if (t==2)
		{
			del=mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))];
			mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))]=make_pair(0,0);
			udel=make_pair(-del.first,-del.second);
			add(r1,c1,udel);
			add(r1,c2+1,del);
			add(r2+1,c1,del);
			add(r2+1,c2+1,udel);
		}
		else
		{
			del=query(r1,c1);
			udel=query(r2,c2);
			if (del==udel) printf("Yes\n"); else printf("No\n");
		}
	}
	return 0;
}