-18 Removals
+10 Additions
#include <bits/stdc++.h>#include <bits/stdc++.h>
using namespace std;using namespace std;
#define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }#define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }
vector<string> split(const string& s, char c) { vector<string> v; stringstream ss(s); string x; while (getline(ss, x, c)) v.push_back(move(x)); return v; }vector<string> split(const string& s, char c) { vector<string> v; stringstream ss(s); string x; while (getline(ss, x, c)) v.push_back(move(x)); return v; }
void err(vector<string>::iterator it) {}void err(vector<string>::iterator it) {}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args) { cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << '\n'; err(++it, args...); }template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args) { cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << '\n'; err(++it, args...); }
#define MAXN 100013#define MAXN 100013
#define MAXM 100013#define MAXM 100013
#define MAXC 100013#define MAXC 100013
#define MAXSQRT 320#define MAXSQRT 320
int N, M;int N, M;
int C[MAXN];int C[MAXN];
vector<int> adj[MAXN];vector<int> adj[MAXN];
int preorder[MAXN]; // where a node appears in preorderint preorder[MAXN]; // where a node appears in preorder
int ID[MAXN]; // real value of a preorder indexint ID[MAXN]; // real value of a preorder index
int endofsubtree[MAXN]; // last element in preorder of subtree of this nodeint endofsubtree[MAXN]; // last element in preorder of subtree of this node
int t = 0;int t = 0;
int BL[MAXN];int BL[MAXN];
struct query {struct query {
int id, b, e, k; int id, b, e, k;
bool operator<(query other) { bool operator<(query other) {
return BL[b] == BL[other.b] ? e < other.e : BL[b] < BL[other.b]; return BL[b] == BL[other.b] ? e < other.e : BL[b] < BL[other.b];
} }
} Q[MAXM];} Q[MAXM];
int VAL[MAXN]; // mo stuffint VAL[MAXN]; // mo stuff
bool VIS[MAXN];
int ANS[MAXM];int ANS[MAXM];
struct fenwick {struct fenwick {
int ar[MAXC] = {0}; int ar[MAXC] = {0};
int query(int idx) { int query(int idx) {
int ans = 0; int ans = 0;
for (int i = idx + 1; i > 0; i -= i & -i) { for (int i = idx + 1; i > 0; i -= i & -i) {
ans += ar[i]; ans += ar[i];
} }
return ans; return ans;
} }
void update(int idx, int x) { void update(int idx, int x) {
for (int i = idx + 1; i < MAXC; i += i & -i) { for (int i = idx + 1; i < MAXC; i += i & -i) {
ar[i] += x; ar[i] += x;
} }
} }
} F;} F;
void dfs(int n, int prev=-1) {void dfs(int n, int prev=-1) {
preorder[n] = t++; preorder[n] = t++;
ID[preorder[n]] = n; ID[preorder[n]] = n;
for (int x : adj[n]) { for (int x : adj[n]) {
if (x != prev) { if (x != prev) {
dfs(x, n); dfs(x, n);
} }
} }
endofsubtree[n] = t - 1; endofsubtree[n] = t - 1;
}}
inline void check(int x) {inline void check(int x, int p) {
int prev = VAL[C[x]]; F.update(VAL[C[x]], -1);
if (VIS[x]) { VAL[C[x]] += p;
VAL[C[x]]--;
}
else {
VAL[C[x]]++;
}
VIS[x] ^= 1;
F.update(prev, -1);
F.update(VAL[C[x]], 1); F.update(VAL[C[x]], 1);
}}
void compute() {void compute() {
int curB = Q[0].b, curE = Q[0].b - 1; int curB = Q[0].b, curE = Q[0].b - 1;
for (int i = 0; i < M; i++) { for (int i = 0; i < M; i++) {
query q = Q[i]; query q = Q[i];
// error(q.id, q.b, q.e); // error(q.id, q.b, q.e);
while (curB > q.b) check(ID[--curB]); while (curB > q.b) check(ID[--curB], 1);
while (curB < q.b) check(ID[curB++]); while (curB < q.b) check(ID[curB++], -1);
while (curE > q.e) check(ID[curE--]); while (curE > q.e) check(ID[curE--], -1);
while (curE < q.e) check(ID[++curE]); while (curE < q.e) check(ID[++curE], 1);
ANS[q.id] = F.query(MAXC - 1) - F.query(q.k - 1); ANS[q.id] = F.query(MAXC - 1) - F.query(q.k - 1);
} }
}}
int main() {int main() {
ios_base::sync_with_stdio(false); ios_base::sync_with_stdio(false);
cin.tie(0); cin.tie(0);
// freopen("input.txt", "r", stdin); // freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout); // freopen("output.txt", "w", stdout);
cin >> N >> M; cin >> N >> M;
for (int i = 0; i < N; i++) { for (int i = 0; i < N; i++) {
cin >> C[i]; cin >> C[i];
} }
// okee read in the edges // okee read in the edges
for (int i = 0; i < N - 1; i++) { for (int i = 0; i < N - 1; i++) {
int a, b; int a, b;
cin >> a >> b; cin >> a >> b;
a--; b--; a--; b--;
adj[a].push_back(b); adj[a].push_back(b);
adj[b].push_back(a); adj[b].push_back(a);
} }
dfs(0); dfs(0);
int size = sqrt(N); int size = sqrt(N);
for (int i = 0; i < N; i++) { for (int i = 0; i < N; i++) {
BL[i] = i / size; BL[i] = i / size;
} }
for (int i = 0; i < M; i++) { for (int i = 0; i < M; i++) {
int v, k; int v, k;
cin >> v >> k; v--; cin >> v >> k; v--;
Q[i].id = i; Q[i].id = i;
Q[i].b = preorder[v]; Q[i].b = preorder[v];
Q[i].e = endofsubtree[v]; Q[i].e = endofsubtree[v];
Q[i].k = k; Q[i].k = k;
} }
sort(Q, Q + M); sort(Q, Q + M);
compute(); compute();
for (int i = 0; i < M; i++) { for (int i = 0; i < M; i++) {
cout << ANS[i] << '\n'; cout << ANS[i] << '\n';
} }
cout.flush(); cout.flush();
return 0; return 0;
}}
Editor
Clear
Export as PDF
Original Text
Changed Text