#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
#define pb push_back
#define f first
#define s second
const int MAXN = 1e5 + 10;
int N;
struct LSegTr {
int tr[4 * MAXN];
void push(int i, int l, int r) {
if (l == r || tr[i] == -1) return;
tr[i * 2] = tr[i];
tr[i * 2 + 1] = tr[i];
tr[i] = -1;
}
int q(int i, int l, int r, int x) {
push(i, l, r);
if (l == r) {
return tr[i];
}
int mid = (l + r) / 2;
if (x <= mid) {
return q(i * 2, l, mid, x);
} else {
return q(i * 2 + 1, mid + 1, r, x);
}
}
void u(int i, int l, int r, int s, int e, int d) {
push(i, l, r);
if (e < l || r < s) {
return;
}
if (s <= l && r <= e) {
tr[i] = d;
return;
}
int mid = (l + r) / 2;
u(i * 2, l, mid, s, e, d);
u(i * 2 + 1, mid + 1, r, s, e, d);
}
int q(int x) {
return q(1, 0, N - 1, x);
}
void u(int s, int e, int d) {
return u(1, 0, N - 1, s, e, d);
}
};
int rt;
vi aL[MAXN];
int p[MAXN], d[MAXN], hC[MAXN], cS[MAXN];
LSegTr tr;
int tI[MAXN];
int tV[MAXN];
int initDFS(int cV) {
int cCnt = 1, mSCnt = 0;
for (int aV : aL[cV]) {
if (aV != p[cV]) {
p[aV] = cV;
d[aV] = d[cV] + 1;
int aCnt = initDFS(aV);
if (aCnt > mSCnt) {
mSCnt = aCnt;
hC[cV] = aV;
}
cCnt += aCnt;
}
}
return cCnt;
}
void init() {
fill(hC, hC + MAXN, -1);
p[rt] = -1;
initDFS(rt);
int nTI = 0;
for (int curS = 0; curS < N; curS++) {
if (curS == rt || hC[p[curS]] != curS) {
for (int cV = curS; cV != -1; cV = hC[cV]) {
cS[cV] = curS;
tV[nTI] = cV;
tI[cV] = nTI++;
}
}
}
}
int fSame(int l, int r, int cT) {
assert(tr.q(r) == cT);
while (l != r) {
int mid = (l + r) / 2;
if (tr.q(mid) == cT) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
vector<pi> path;
void query(int cV) {
path.clear();
while (cV != -1) {
int cCS = cS[cV];
int cT = tr.q(tI[cV]);
int cFS = fSame(tI[cCS], tI[cV], cT);
path.pb({cT, tI[cV] - cFS + 1});
cV = p[tV[cFS]];
}
}
void update(int cV, int cT) {
while (cV != -1) {
int cCS = cS[cV];
tr.u(tI[cCS], tI[cV], cT);
cV = p[cCS];
}
}
int color[MAXN];
vector<pi> proc;
void processPath() {
proc.clear();
reverse(path.begin(), path.end());
int cC = -1;
int cCnt = 0;
for (pi x : path) {
if (color[x.f] == cC) {
cCnt += x.s;
} else {
if (cCnt > 0) {
proc.pb({cC, cCnt});
}
cC = color[x.f];
cCnt = x.s;
}
}
if (cCnt > 0) {
proc.pb({cC, cCnt});
}
}
int cnt = 0;
vector<pi> cntInversions(vector<pi> &input) {
if (input.size() == 1) {
return input;
}
int mid = input.size() / 2;
vector<pi> a = vector<pi>(input.begin(), input.begin() + mid);
vector<pi> b = vector<pi>(input.begin() + mid, input.end());
a = cntInversions(a);
b = cntInversions(b);
vector<pi> combine;
int nA = 0;
int nB = 0;
int remA = 0;
for (pi x : a) {
remA += x.s;
}
while (nA < a.size() || nB < b.size()) {
if (nA < a.size()) {
if (nB < b.size()) {
if (b[nB].f < a[nA].f) {
combine.pb(b[nB++]);
cnt += remA;
} else {
remA -= a[nA].s;
combine.pb(a[nA++]);
}
}
else{
remA -= a[nA].s;
combine.pb(a[nA++]);
}
}
else{
assert(nB < b.size());
combine.pb(b[nB++]);
}
}
return combine;
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> color[i];
}
vi queries;
for (int i = 0; i < N - 1; i++) {
int a, b;
cin >> a >> b;
a--, b--;
aL[a].pb(b);
queries.pb(b);
}
rt = 0;
init();
fill(tr.tr, tr.tr + 4 * MAXN, -1);
update(rt, 0);
for (int cQ : queries) {
query(p[cQ]);
processPath();
cnt = 0;
cntInversions(proc);
cout << cnt << endl;
update(cQ, cQ);
}
}
Compilation message
construction.cpp: In function 'std::vector<std::pair<int, int> > cntInversions(std::vector<std::pair<int, int> >&)':
construction.cpp:208:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (nA < a.size() || nB < b.size()) {
~~~^~~~~~~~~~
construction.cpp:208:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (nA < a.size() || nB < b.size()) {
~~~^~~~~~~~~~
construction.cpp:209:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (nA < a.size()) {
~~~^~~~~~~~~~
construction.cpp:210:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (nB < b.size()) {
~~~^~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
from construction.cpp:1:
construction.cpp:225:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(nB < b.size());
~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4600 KB |
Output is correct |
| 2 |
Correct |
8 ms |
4728 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
4600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4600 KB |
Output is correct |
| 2 |
Correct |
8 ms |
4728 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
4600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
4600 KB |
Output is correct |
| 2 |
Correct |
8 ms |
4728 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
4600 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
