PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Euler tour, LCA, fenwick/segment trees
PROBLEM:
You’re given a tree with vertex i having the value A_i.
Each value from 1 to N appears exactly twice.
Answer Q queries:
- Swap the values of two vertices.
- Given k, block all vertices on the path between the two vertices with value k.
Then, find how many pairs of vertices (x, y) satisfy A_x = A_y and the path from x to y doesn’t pass through a blocked vertex.
EXPLANATION:
In essence, we’re given N paths on the tree.
Each update removes two of these paths and adds two more in, while each query gives us a single path and asks us to find how many of the existing paths don’t intersect it.
To proceed, we first need a good enough criterion that lets us decide when two paths intersect.
Here’s one criterion:
The path between (u_1, u_2) intersects the path between (v_1, v_2) if and only if the lowest common ancestor (LCA) of one pair lies on the other path - that is,
- \text{lca}(u_1, u_2) lies on the path from v_1 to v_2, or
- \text{lca}(v_1, v_2) lies on the path from u_1 to u_2.
With this criterion, notice that answering a query is fairly straightforward: if we block the path (x, y), we can count the number of paths that intersect it as:
- Paths whose LCA lies on (x, y), or
- Paths containing \text{lca}(x, y).
A path whose LCA is itself \text{lca}(x, y) will fall under both cases, so we must make sure to either subtract them out or just not double-count in the first place.
To count “paths whose LCA lies on (x, y)”, we only really need to know, for each vertex u, how many paths have their LCA as u.
Then, this becomes a simple path sum from x to y.
Note that each update operation only changes a couple of paths, so we need to perform \mathcal{O}(1) point updates.
Here, we need to be able to handle point updates and path sums.
To count “paths containing \text{lca}(x, y)”, one way is to somehow add 1 to the vertices along every path, and then simply get the value at \text{lca}(x, y).
Here, we need to handle path additions and point queries.
It’s possible to simply bash this using the various tree decompositions (heavy-light or centroid with a lazy segment tree), but with a bit of cleverness we can avoid having to use any of them at all!
In particular, we have:
Point updates and path sums
Define b_u to be the sum of values on all vertices from the root to u.
Then,
- A point update at v increases the b_u value for all vertices u in the subtree of v.
- A path query (x, y) can be obtained by looking at the b values of vertices x, y, \text{lca}(x, y), in similar fashion to prefix sums.
Subtree updates can be treated as essentially subarray updates by first building the Euler tour of the tree.
We’re then reduced to “add on segment, point query”, which can be handled by a simple segment tree or fenwick tree, with the help of prefix sums.Specifically, to add 1 to the range [L, R], just add 1 to the value at L, and subtract 1 from the value at R+1.
Then, to point query for i, simply query the prefix sum till i.
Path additions and point queries
Here, we use a similar idea to the previous case, where range additions were turned into a couple of point additions, and point queries were turned into prefix queries.
Since we’re on a tree, rather than prefix queries we use subtree queries - and we make the point updates appropriately.To add 1 to the path (x, y), do the following:
- Add 1 to the value at x.
- Add 1 to the value at y.
- Subtract 1 from the value at \text{lca}(x, y).
- Subtract 1 from the value at \text{par}[\text{lca}(x, y)].
Now, to perform a point query at u, simply query for the sum of values across the entire subtree of u instead.
Again, building the Euler tour turns this into subarray queries, so we’re back to point updates with subarray queries which a segment tree/fenwick tree can handle.
Every query and update hence requires only a few LCA calls and point updates/range sum queries, each of which take \mathcal{O}(\log N) time.
TIME COMPLEXITY:
\mathcal{O}((N+Q)\log N) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define vi vector<int>
#define be(x) x.begin(),x.end()
#define pb push_back
struct item{
int m;
};
struct segtree{
int size;
vector<item> values;
item NEUTRAL_ELEMENT = {0};
item merge(item a,item b){
return {a.m+b.m};
}
item single(int v){
return {v};
}
void init(int n){
size=1;
while(size<n)size*=2;
values.resize(2*size);
values.assign(2*size,{0});
}
void build(vi &a,int x,int lx,int rx){
if(rx-lx==1){
if(lx<a.size()){
values[x]=single(a[lx]);
}
return;
}
int m = (lx+rx)/2;
build(a,2*x+1,lx,m);
build(a,2*x+2,m,rx);
values[x]=merge(values[2*x+1],values[2*x+2]);
}
void build(vi &a){
build(a,0,0,size);
}
void set(int i,int v,int x,int lx,int rx){
if(rx-lx==1){
values[x]=single(v);
return;
}
int m = (lx+rx)/2;
if(i<m){
set(i,v,2*x+1,lx,m);
}
else {
set(i,v,2*x+2,m,rx);
}
values[x]=merge(values[2*x+1],values[2*x+2]);
}
void set(int i,int v){
set(i,v,0,0,size);
}
item calc(int l,int r,int x,int lx,int rx){
if(lx>=r || l>=rx)return NEUTRAL_ELEMENT;
if(lx>=l && rx<=r)return values[x];
int m = (lx+rx)/2;
item s1 = calc(l,r,2*x+1,lx,m);
item s2 = calc(l,r,2*x+2,m,rx);
return merge(s1,s2);
}
int calc(int l,int r){
return calc(l,r,0,0,size).m;
}
};
const int MX = 4e5+5;
template<int SZ, bool VALS_IN_EDGES> struct HLD {
int N; vi adj[SZ];
int par[SZ], root[SZ], depth[SZ], sz[SZ], ti;
int pos[SZ]; vi rpos; // rpos not used but could be useful
segtree st;
void ae(int x, int y) { adj[x].pb(y), adj[y].pb(x); }
void dfsSz(int x) {
sz[x] = 1;
for(auto& y : adj[x]) {
par[y] = x; depth[y] = depth[x]+1;
adj[y].erase(find(be(adj[y]),x)); /// remove parent from adj list
dfsSz(y); sz[x] += sz[y];
if (sz[y] > sz[adj[x][0]]) swap(y,adj[x][0]);
}
}
void dfsHld(int x) {
pos[x] = ti++; rpos.pb(x);
for(auto y : adj[x]) {
root[y] = (y == adj[x][0] ? root[x] : y);
dfsHld(y); }
}
void init(int _N, int R = 0) { N = _N;
rpos.clear();
par[R] = depth[R] = ti = 0; dfsSz(R);
root[R] = R; dfsHld(R); st.init(N);
}
void clear(){
for(int i=0;i<N+1;i++){
par[i]=0,root[i]=0,depth[i]=0,sz[i]=0,pos[i]=0;
adj[i].clear();
}
ti=0;rpos.clear();
}
int lca(int x, int y) {
for (; root[x] != root[y]; y = par[root[y]])
if (depth[root[x]] > depth[root[y]]) swap(x,y);
return depth[x] < depth[y] ? x : y;
}
int dist(int x, int y) { // # edges on path
return depth[x]+depth[y]-2*depth[lca(x,y)]; }
void upd(int x,int v){
int res = st.calc(pos[x],pos[x]+1);
res += v;
st.set(pos[x],res);
}
ll queryPath(int x, int y) {
int res = 0;
for (; root[x] != root[y]; y = par[root[y]]) {
if (depth[root[x]] > depth[root[y]]){
swap(x,y);
}
res+=st.calc(pos[root[y]],pos[y]+1);
}
if (depth[x] > depth[y]) swap(x,y);
res+=st.calc(pos[x]+VALS_IN_EDGES,pos[y]+1);
return res;
}
ll querySub(int x){
int res = st.calc(pos[x],pos[x]+sz[x]);
return res;
}
};
HLD<MX,0> hl;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll tt=1;
cin>>tt;
while(tt--){
ll n,q;
cin >> n >> q;
hl.clear();
ll u,v;
for(int i=0;i<2*n-1;i++){
cin >> u >> v;
u--;v--;
hl.ae(u,v);
}
hl.init(2*n);
vi a(2*n);
for(int i=0;i<2*n;i++){
cin>>a[i];
a[i]--;
}
vector<array<int,2>> pos(n,{-1,-1});
for(int i=0;i<2*n;i++){
if(pos[a[i]][0] == -1){
pos[a[i]][0] = i;
}else{
pos[a[i]][1] = i;
}
}
for(int i=0;i<n;i++){
hl.upd(hl.lca(pos[i][0],pos[i][1]),1);
}
ll op,k,l,sm,rem,ans;
while(q--){
cin >> op;
if(op == 1){
cin >> u >> v;
u--;v--;
if(a[u] == a[v]){
continue;
}
hl.upd(hl.lca(pos[a[u]][0],pos[a[u]][1]),-1);
hl.upd(hl.lca(pos[a[v]][0],pos[a[v]][1]),-1);
if(pos[a[u]][0] == u){
pos[a[u]][0] = v;
}else{
pos[a[u]][1] = v;
}
if(pos[a[v]][0] == v){
pos[a[v]][0] = u;
}else{
pos[a[v]][1] = u;
}
hl.upd(hl.lca(pos[a[u]][0],pos[a[u]][1]),1);
hl.upd(hl.lca(pos[a[v]][0],pos[a[v]][1]),1);
swap(a[u],a[v]);
}
else{
cin >> k;
k--;
l = hl.lca(pos[k][0],pos[k][1]);
sm = hl.querySub(l) - hl.queryPath(pos[k][0],pos[k][1]);
rem = hl.sz[l] - hl.querySub(l)*2;
ans = sm;
ans += (2*n - hl.sz[l] - rem)/2;
cout<<ans<<"\n";
}
}
}
return 0;
}
Tester's code (C++)
//Har Har Mahadev
#include<bits/stdc++.h>
#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>
#ifdef _MSC_VER
#include <intrin.h>
#endif
#if __cplusplus >= 202002L
#include <bit>
#endif
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
#endif
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
#if __cplusplus >= 201703L
template <class S, auto op, auto e> struct segtree {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
#else
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
#endif
public:
segtree() : segtree(0) {}
explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
size = (int)internal::bit_ceil((unsigned int)(_n));
log = internal::countr_zero((unsigned int)size);
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() const { return d[1]; }
template <bool (*f)(S)> int max_right(int l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace atcoder;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
int depth[400005];
int visited[400005];
int up[400005][20];
vi adj[400005];
int st[400005];
int en[400005];
int timer = 0;
vi oc[400005];
int a[400005];
int cnt = 0;
void dfs(int v) {
visited[v]=true;
st[v] = timer++;
oc[v].pb(cnt);cnt++;
rep(i,1,20){
if(up[v][i-1]!=-1)up[v][i] = up[up[v][i-1]][i-1];
}
for(int x : adj[v]) {
if(!visited[x]) {
depth[x] = depth[up[x][0] = v]+1;
dfs(x);
}
}
en[v] = timer;
oc[v].pb(cnt);cnt++;
}
int jump(int x, int d) {
rep(i,0,20){
if((d >> i) & 1)
{if(x==-1)break;
x = up[x][i];}
}
return x;
}
int LCA(int a, int b) {
if(depth[a] < depth[b]) swap(a, b);
a = jump(a, depth[a] - depth[b]);
if(a == b) return a;
rrep(i,19,0){
int aT = up[a][i], bT = up[b][i];
if(aT != bT) a = aT, b = bT;
}
return up[a][0];
}
int dist(int a,int b) {
return depth[a]+depth[b]-2*depth[LCA(a,b)];
}
int op(int a,int b){
return a+b;
}
int e(){
return 0;
}
void solve()
{
int n,q;
cin >> n >> q;
timer = 0;
cnt = 0;
rep(i,0,2*n+1){
adj[i].clear();
visited[i] = 0;
oc[i].clear();
rep(j,0,20){
up[i][j] = -1;
}
}
rep(i,0,2*n-1){
int u,v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
dfs(1);
rep(i,1,2*n+1)cin >> a[i];
vi nd[n+1];
rep(i,1,2*n+1){
nd[a[i]].pb(i);
}
// rep(i,1,2*n+1){
// // cout << st[i] << " " << en[i] << "gi\n";
// cout << oc[i][0] << " " << oc[i][1] << "\n";
// }
// cout << "hi\n";return;
segtree<int,op,e> seg(2*n+1),seg1(4*n+1);
rep(i,1,n+1){
int l = LCA(nd[i][0],nd[i][1]);
seg.set(st[l],seg.get(st[l])+1);
seg1.set(oc[l][0],seg1.get(oc[l][0])+1);
seg1.set(oc[l][1],seg1.get(oc[l][1])-1);
}
// cout << "hi\n";return;
// rep(i,0,2*n)cout << seg.get(i) << " ";cout << "\n";
// rep(i,0,4*n)cout << seg1.get(i) << " ";cout << "\n";
rep(i,0,q){
int type;
cin >> type;
if(type == 1){
int u,v;
cin >> u >> v;
if(a[u] == a[v])continue;
// continue;
// cout << nd[a[u]][0] << " " << nd[a[u]][1] << " " << LCA(nd[a[u]][0],nd[a[u]][1]) << " " << nd[a[v]][0] << " " << nd[a[v]][1] << " " << LCA(nd[a[v]][0],nd[a[v]][1]) << "see\n";
seg.set(st[LCA(nd[a[u]][0],nd[a[u]][1])],seg.get(st[LCA(nd[a[u]][0],nd[a[u]][1])])-1);
seg1.set(oc[LCA(nd[a[u]][0],nd[a[u]][1])][0],seg1.get(oc[LCA(nd[a[u]][0],nd[a[u]][1])][0])-1);
seg1.set(oc[LCA(nd[a[u]][0],nd[a[u]][1])][1],seg1.get(oc[LCA(nd[a[u]][0],nd[a[u]][1])][1])+1);
// rep(j,0,4*n)cout << seg1.get(j) << " ";cout << "fi\n";
seg.set(st[LCA(nd[a[v]][0],nd[a[v]][1])],seg.get(st[LCA(nd[a[v]][0],nd[a[v]][1])])-1);
seg1.set(oc[LCA(nd[a[v]][0],nd[a[v]][1])][0],seg1.get(oc[LCA(nd[a[v]][0],nd[a[v]][1])][0])-1);
seg1.set(oc[LCA(nd[a[v]][0],nd[a[v]][1])][1],seg1.get(oc[LCA(nd[a[v]][0],nd[a[v]][1])][1])+1);
// rep(j,0,4*n)cout << seg1.get(j) << " ";cout << "li\n";
if(nd[a[u]][0] == u)nd[a[u]][0] = v;else nd[a[u]][1] = v;
if(nd[a[v]][0] == v)nd[a[v]][0] = u;else nd[a[v]][1] = u;
seg.set(st[LCA(nd[a[u]][0],nd[a[u]][1])],seg.get(st[LCA(nd[a[u]][0],nd[a[u]][1])])+1);
seg1.set(oc[LCA(nd[a[u]][0],nd[a[u]][1])][0],seg1.get(oc[LCA(nd[a[u]][0],nd[a[u]][1])][0])+1);
seg1.set(oc[LCA(nd[a[u]][0],nd[a[u]][1])][1],seg1.get(oc[LCA(nd[a[u]][0],nd[a[u]][1])][1])-1);
seg.set(st[LCA(nd[a[v]][0],nd[a[v]][1])],seg.get(st[LCA(nd[a[v]][0],nd[a[v]][1])])+1);
seg1.set(oc[LCA(nd[a[v]][0],nd[a[v]][1])][0],seg1.get(oc[LCA(nd[a[v]][0],nd[a[v]][1])][0])+1);
seg1.set(oc[LCA(nd[a[v]][0],nd[a[v]][1])][1],seg1.get(oc[LCA(nd[a[v]][0],nd[a[v]][1])][1])-1);
swap(a[u],a[v]);
// rep(j,0,2*n)cout << seg.get(j) << " ";cout << "hi\n";
// rep(j,0,4*n)cout << seg1.get(j) << " ";cout << "bi\n";
}
else{
int k;
cin >> k;
int l = LCA(nd[k][0],nd[k][1]);
int sbsm = seg.prod(st[l],en[l]);
// cout << l << " " << st[nd[k][0]]
int ptsm = seg1.prod(oc[l][0],oc[nd[k][0]][0]+1) + seg1.prod(oc[l][0],oc[nd[k][1]][0]+1) - seg.get(st[l]);
// cout << l << ' ' << sbsm << " " << ptsm << "dekh\n";
int ans = sbsm - ptsm;
ans += n + sbsm - (en[l] - st[l]);
cout << ans << "\n";
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
int t;
cin >> t;
while(t--)
solve();
return 0;
}
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
struct FT {
vector<ll> s;
FT(int n = 1) : s(n) {}
void update(int pos, ll dif) { // a[pos] += dif
for (; pos < size(s); pos |= pos + 1) s[pos] += dif;
}
ll query(int pos) { // sum of values in [0, pos)
ll res = 0;
for (; pos > 0; pos &= pos - 1) res += s[pos-1];
return res;
}
ll query(int L, int R) { // [L, R)
return query(R) - query(L);
}
};
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, q; cin >> n >> q;
vector adj(2*n, vector<int>());
for (int i = 0; i < 2*n-1; ++i) {
int u, v; cin >> u >> v;
--u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> a(2*n);
vector<set<int>> who(n+1);
for (int i = 0; i < 2*n; ++i) {
cin >> a[i];
who[a[i]].insert(i);
}
const int LG = 20;
vector<array<int, LG>> anc(2*n);
FT through(2*n), lca_ct(2*n);
vector<int> in(2*n), out(2*n);
int timer = 0;
auto dfs = [&] (const auto &self, int u, int p) -> void {
anc[u][0] = p;
in[u] = timer++;
for (int i = 1; i < LG; ++i) anc[u][i] = anc[anc[u][i-1]][i-1];
for (int v : adj[u]) {
if (v != p) self(self, v, u);
}
out[u] = timer;
};
auto is_anc = [&] (int u, int v) {
return in[u] <= in[v] and out[u] >= out[v];
};
auto lca = [&] (int u, int v) {
if (is_anc(u, v)) return u;
if (is_anc(v, u)) return v;
for (int i = LG-1; i >= 0; --i) {
if (!is_anc(anc[u][i], v)) u = anc[u][i];
}
return anc[u][0];
};
dfs(dfs, 0, 0);
auto update = [&] (int col, int mul) {
int u = *who[col].begin(), v = *who[col].rbegin();
int L = lca(u, v);
through.update(in[u], mul), through.update(in[v], mul);
through.update(in[L], -mul);
if (L > 0) through.update(in[anc[L][0]], -mul);
lca_ct.update(in[L], mul), lca_ct.update(out[L], -mul);
};
auto query = [&] (int col) {
int u = *who[col].begin(), v = *who[col].rbegin();
int L = lca(u, v);
int intersect = through.query(in[L], out[L]) + lca_ct.query(in[u]+1) + lca_ct.query(in[v]+1) - 2*lca_ct.query(in[L]+1);
return n - intersect;
};
for (int i = 1; i <= n; ++i) update(i, 1);
while (q--) {
int type; cin >> type;
if (type == 1) {
int u, v; cin >> u >> v;
--u, --v;
if (a[u] == a[v]) continue;
update(a[u], -1), update(a[v], -1);
who[a[u]].erase(u), who[a[v]].erase(v);
swap(a[u], a[v]);
who[a[u]].insert(u), who[a[v]].insert(v);
update(a[u], 1), update(a[v], 1);
}
else {
int k; cin >> k;
cout << query(k) << '\n';
}
}
}
}