Compare text

Find the difference between two text files

Real-time editor

Hide unchanged lines

Disable line wrap

Layout

Diff precision

Syntax highlighting

Diffchecker Desktop The most secure way to run Diffchecker. Get the Diffchecker Desktop app: your diffs never leave your computer!Get Desktop

Untitled diff

Created 10 years agoDiff never expires

12 removals

Lines
Total
Removed

Characters
Total
Removed

To continue using this feature, upgrade to Diffchecker Pro View Pricing

136 lines

8 additions

Lines
Total
Added

Characters
Total
Added

To continue using this feature, upgrade to Diffchecker Pro View Pricing

128 lines

#include <bits/stdc++.h>

using namespace std;

#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; }

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...); }

#define MAXN 100013

#define MAXM 100013

#define MAXC 100013

#define MAXSQRT 320

int N, M;

int C[MAXN];

vector<int> adj[MAXN];

int preorder[MAXN]; // where a node appears in preorder

int ID[MAXN]; // real value of a preorder index

int endofsubtree[MAXN]; // last element in preorder of subtree of this node

int t = 0;

int BL[MAXN];

struct query {

int id, b, e, k;

bool operator<(query other) {

return BL[b] == BL[other.b] ? e < other.e : BL[b] < BL[other.b];

}

} Q[MAXM];

int VAL[MAXN]; // mo stuff

bool VIS[MAXN];

int ANS[MAXM];

struct fenwick {

int ar[MAXC] = {0};

int query(int idx) {

int ans = 0;

for (int i = idx + 1; i > 0; i -= i & -i) {

ans += ar[i];

}

return ans;

}

void update(int idx, int x) {

for (int i = idx + 1; i < MAXC; i += i & -i) {

ar[i] += x;

}

} F;

void dfs(int n, int prev=-1) {

preorder[n] = t++;

ID[preorder[n]] = n;

for (int x : adj[n]) {

if (x != prev) {

dfs(x, n);

}

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);

}

void compute() {

int curB = Q[0].b, curE = Q[0].b - 1;

for (int i = 0; i < M; i++) {

query q = Q[i];

// 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);

}

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

// freopen("input.txt", "r", stdin);

// freopen("output.txt", "w", stdout);

cin >> N >> M;

for (int i = 0; i < N; i++) {

cin >> C[i];

}

// okee read in the edges

for (int i = 0; i < N - 1; i++) {

int a, b;

cin >> a >> b;

a--; b--;

adj[a].push_back(b);

adj[b].push_back(a);

}

dfs(0);

int size = sqrt(N);

for (int i = 0; i < N; i++) {

BL[i] = i / size;

}

for (int i = 0; i < M; i++) {

int v, k;

cin >> v >> k; v--;

Q[i].id = i;

Q[i].b = preorder[v];

Q[i].e = endofsubtree[v];

Q[i].k = k;

}

sort(Q, Q + M);

compute();

for (int i = 0; i < M; i++) {

cout << ANS[i] << '\n';

}

cout.flush();

return 0;

}

Saved diffs

Original text

Open file

#include <bits/stdc++.h>
using namespace std;

#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; }
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...); }

#define MAXN 100013
#define MAXM 100013
#define MAXC 100013
#define MAXSQRT 320

int N, M;
int C[MAXN];
vector<int> adj[MAXN];
int preorder[MAXN]; // where a node appears in preorder
int ID[MAXN]; // real value of a preorder index
int endofsubtree[MAXN]; // last element in preorder of subtree of this node
int t = 0;
int BL[MAXN];

struct query {
	int id, b, e, k;
	bool operator<(query other) {
		return BL[b] == BL[other.b] ? e < other.e : BL[b] < BL[other.b];
	}
} Q[MAXM];
int VAL[MAXN]; // mo stuff
bool VIS[MAXN];
int ANS[MAXM];

struct fenwick {
	int ar[MAXC] = {0};
	int query(int idx) {
		int ans = 0;
		for (int i = idx + 1; i > 0; i -= i & -i) {
			ans += ar[i];
		}
		return ans;
	}
	void update(int idx, int x) {
		for (int i = idx + 1; i < MAXC; i += i & -i) {
			ar[i] += x;
		}
	}
} F;

void dfs(int n, int prev=-1) {
	preorder[n] = t++;
	ID[preorder[n]] = n;

for (int x : adj[n]) {
		if (x != prev) {
			dfs(x, n);
		}
	}

endofsubtree[n] = t - 1;
}

inline void check(int x) {
	int prev = VAL[C[x]];
	if (VIS[x]) {
		VAL[C[x]]--;
	}
	else {
		VAL[C[x]]++;
	}
	VIS[x] ^= 1;
	F.update(prev, -1);
	F.update(VAL[C[x]], 1);
}

void compute() {
	int curB = Q[0].b, curE = Q[0].b - 1;
	for (int i = 0; i < M; i++) {
		query q = Q[i];
		// error(q.id, q.b, q.e);

while (curB > q.b) check(ID[--curB]);
		while (curB < q.b) check(ID[curB++]);
		while (curE > q.e) check(ID[curE--]);
		while (curE < q.e) check(ID[++curE]);

ANS[q.id] = F.query(MAXC - 1) - F.query(q.k - 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}

// okee read in the edges
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

dfs(0);

int size = sqrt(N);
	for (int i = 0; i < N; i++) {
		BL[i] = i / size;
	}

for (int i = 0; i < M; i++) {
		int v, k;
		cin >> v >> k; v--;
		Q[i].id = i;
		Q[i].b = preorder[v];
		Q[i].e = endofsubtree[v];
		Q[i].k = k;
	}

sort(Q, Q + M);
	compute();
	for (int i = 0; i < M; i++) {
		cout << ANS[i] << '\n';
	}

cout.flush();
	return 0;
}

Changed text

Open file

#include <bits/stdc++.h>
using namespace std;

#define MAXN 100013
#define MAXM 100013
#define MAXC 100013
#define MAXSQRT 320

struct query {
	int id, b, e, k;
	bool operator<(query other) {
		return BL[b] == BL[other.b] ? e < other.e : BL[b] < BL[other.b];
	}
} Q[MAXM];
int VAL[MAXN]; // mo stuff
int ANS[MAXM];

void dfs(int n, int prev=-1) {
	preorder[n] = t++;
	ID[preorder[n]] = n;

for (int x : adj[n]) {
		if (x != prev) {
			dfs(x, n);
		}
	}

endofsubtree[n] = t - 1;
}

inline void check(int x, int p) {
	F.update(VAL[C[x]], -1);
	VAL[C[x]] += p;
	F.update(VAL[C[x]], 1);
}

void compute() {
	int curB = Q[0].b, curE = Q[0].b - 1;
	for (int i = 0; i < M; i++) {
		query q = Q[i];
		// error(q.id, q.b, q.e);

while (curB > q.b) check(ID[--curB], 1);
		while (curB < q.b) check(ID[curB++], -1);
		while (curE > q.e) check(ID[curE--], -1);
		while (curE < q.e) check(ID[++curE], 1);

ANS[q.id] = F.query(MAXC - 1) - F.query(q.k - 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}

// okee read in the edges
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

dfs(0);

int size = sqrt(N);
	for (int i = 0; i < N; i++) {
		BL[i] = i / size;
	}

for (int i = 0; i < M; i++) {
		int v, k;
		cin >> v >> k; v--;
		Q[i].id = i;
		Q[i].b = preorder[v];
		Q[i].e = endofsubtree[v];
		Q[i].k = k;
	}

sort(Q, Q + M);
	compute();
	for (int i = 0; i < M; i++) {
		cout << ANS[i] << '\n';
	}

cout.flush();
	return 0;
}