#include "joitour.h"
#include <bits/stdc++.h>
using namespace std;
const int n = (1 << 17);
struct Node {
long long rep = 0;
long long nb0 = 0;
long long nb1 = 0;
long long nb2 = 0;
long long nb10 = 0;
long long nb12 = 0;
long long nb01 = 0;
long long nb21 = 0;
};
vector<Node> dp;
void combine(int node) {
dp[node].nb0 = dp[2 * node].nb0 + dp[2 * node + 1].nb0;
dp[node].nb1 = dp[2 * node].nb1 + dp[2 * node + 1].nb1;
dp[node].nb2 = dp[2 * node].nb2 + dp[2 * node + 1].nb2;
dp[node].nb01 = (dp[2 * node].nb01 + dp[2 * node + 1].nb01) + (dp[2 * node].nb0 * dp[2 * node + 1].nb1);
dp[node].nb21 = (dp[2 * node].nb21 + dp[2 * node + 1].nb21) + (dp[2 * node].nb2 * dp[2 * node + 1].nb1);
dp[node].nb10 = (dp[2 * node].nb10 + dp[2 * node + 1].nb10) + (dp[2 * node].nb1 * dp[2 * node + 1].nb0);
dp[node].nb12 = (dp[2 * node].nb12 + dp[2 * node + 1].nb12) + (dp[2 * node].nb1 * dp[2 * node + 1].nb2);
dp[node].rep = (dp[2 * node].rep + dp[2 * node + 1].rep) + (dp[2 * node].nb0 * dp[2 * node + 1].nb12) + (dp[2 * node].nb2 * dp[2 * node + 1].nb10) + (dp[2 * node].nb21 * dp[2 * node + 1].nb0) + (dp[2 * node].nb01 * dp[2 * node + 1].nb2);
return;
}
void init(int N, vector<int> f, vector<int> u, vector<int> v, int q) {
dp.resize(2 * n);
for (int i = 0; i < N; i ++) {
Node nouv;
dp[n + i] = nouv;
if (f[i] == 0) {
dp[n + i].nb0 = 1;
}
if (f[i] == 1) {
dp[n + i].nb1 = 1;
}
if (f[i] == 2) {
dp[n + i].nb2 = 1;
}
}
for (int j = n - 1; j >= 1; j --) {
combine(j);
}
}
void change(int x, int y) {
Node nouv;
dp[n + x] = nouv;
if (y == 0) {
dp[n + x].nb0 = 1;
}
if (y == 1) {
dp[n + x].nb1 = 1;
}
if (y == 2) {
dp[n + x].nb2 = 1;
}
for (int cur = (n + x) / 2; cur > 0; cur /= 2) {
combine(cur);
}
}
long long num_tours() {
return dp[1].rep;
}
