Comparing sensitive data, confidential files or internal emails?

Most legal and privacy policies prohibit uploading sensitive data online. Diffchecker Desktop ensures your confidential information never leaves your computer. Work offline and compare documents securely.

Untitled diff

Created Diff never expires
15 removals
136 lines
7 additions
128 lines
#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 preorder
int preorder[MAXN]; // where a node appears in preorder
int ID[MAXN]; // real value of a preorder index
int ID[MAXN]; // real value of a preorder index
int endofsubtree[MAXN]; // last element in preorder of subtree of this node
int 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 stuff
int 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;
}
}