/*
Wei Wai Wei Wai
Zumigat nan damu dimi kwayt rayt
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
/*typedef __uint128_t L;
struct FastMod {
ull b, m;
FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
ull reduce(ull a) {
ull q = (ull)((L(m) * a) >> 64);
ull r = a - q * b; // can be proven that 0 <= r < 2*b
return r >= b ? r - b : r;
}
};
FastMod FM(2);*/
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << H;
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e5 + 10;
int n, a[maxn], f[maxn], sz[maxn], chn[maxn], par[maxn], st[maxn], en[maxn], val[maxn], Q[maxn], tme;
vector<int> g[maxn], num;
vector<pii> ans;
set<pair<pii,int>> seg;
void add(int idx, int x){
for (; idx <= n; idx += idx & -idx) f[idx] += x;
}
int get(int idx){
int res = 0;
for (; idx; idx -= idx & -idx) res += f[idx];
return res;
}
int get(int l, int r){
if (r < l) return 0;
return get(r) - get(l-1);
}
void dfs(int v, int p = -1){
par[v] = p;
sz[v] = 1;
for (auto u: g[v]){
dfs(u, v);
sz[u] += sz[v];
}
}
void hld(int v, int c){
st[v] = ++tme;
chn[v] = c;
int bc = -1;
for (auto u: g[v]) if (bc == -1 || sz[bc] < sz[u]) bc = u;
if (bc != -1) hld(bc, c);
for (auto u: g[v]) if (u != bc) hld(u, u);
en[v] = tme;
}
void change(int l, int r, int x){
vector<pii> res;
auto it = seg.lower_bound({{l, 0}, 0});
if (it != seg.begin()){
it--;
pair<pii,int> tmp = *it;
if (tmp.F.S >= l){
res.push_back({tmp.S, tmp.F.S - l + 1});
seg.erase(it);
seg.insert({{tmp.F.F, l-1}, tmp.S});
}
}
while(!seg.empty()){
auto it = seg.lower_bound({{l, 0}, 0});
if (it == seg.end() || (*it).F.F > r) break;
pair<pii,int> tmp = *it;
if (tmp.F.S <= r){
res.push_back({tmp.S, tmp.F.S - tmp.F.F + 1});
seg.erase(it);
}
else{
res.push_back({tmp.S, r - tmp.F.F + 1});
seg.erase(it);
seg.insert({{r+1, tmp.F.S}, tmp.S});
}
}
seg.insert({{l, r}, x});
reverse(all(res));
for (auto x: res) ans.push_back(x);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
num.push_back(a[i]);
}
sort(all(num));
num.resize(distance(num.begin(), unique(all(num))));
for (int i = 1; i <= n; i++){
a[i] = lower_bound(all(num), a[i]) - num.begin() + 1;
}
for (int i = 1; i < n; i++){
int x; cin >> x >> Q[i];
g[x].push_back(Q[i]);
}
dfs(1);
hld(1, 1);
for (int i = 1; i <= n; i++){
seg.insert({{st[i], st[i]}, a[i]});
}
for (int i = 1; i < n; i++){
ans.clear();
int v = par[Q[i]];
while(v != -1){
change(st[chn[v]], st[v], a[Q[i]]);
v = par[chn[v]];
}
reverse(all(ans));
ll res = 0;
for (auto [x, y]: ans){
res += get(x+1, n);
add(x, y);
}
cout << res << '\n';
for (auto [x, y]: ans){
add(x, -y);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
