Comparar texto

Encuentra la diferencia entre dos archivos de texto

Editor live
Ocultar sin cambios
Sin ajuste de línea
Vista
Nivel de detalle
Resaltado de sintaxis

Untitled diff

Creado El diff nunca expira
12 eliminaciones
136 líneas
8 adiciones
128 líneas
#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;
}
}


Diferencias guardadas