#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector <pair<ll, ll>> vp;
typedef pair<ll, ll> pll;
typedef map <ll, ll> mll;
typedef set <ll> sll;
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define print(x) for (auto i : x) cout << i << ' '; cout << '\n';
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
const ll maxn = 2e5+5;
const ll mod = 1e9+7;
const ll inf = 2e18;
ll pw(ll a, ll b, ll M = mod) {ll ans = 1; for (; b; a = ((a * a) % M), b >>= 1) if (b & 1) ans = (ans * a) % M; return ans;}
ll n, m, q, a[maxn], mn[4*maxn], mx[4*maxn], sum[4*maxn];
void upd(ll id, ll l, ll r, ll p) {
if (r - l == 1) {
sum[id] = 1 - sum[id];
return;
}
ll mid = (l+r)/2;
if (p < mid) upd(2*id, l, mid, p);
else upd(2*id+1, mid, r, p);
sum[id] = sum[2*id] + sum[2*id+1];
}
ll get(ll id, ll l, ll r, ll s, ll e) {
if (s >= r || e <= l) return 0;
if (s <= l && e >= r) return sum[id];
ll mid = (l+r)/2;
return get(2*id, l, mid, s, e) + get(2*id+1, mid, r, s, e);
}
void updMin(ll id, ll l, ll r, ll s, ll e, ll v) {
if (mn[id] == 0) mn[id] = inf;
if (s >= r || e <= l) return;
if (s <= l && e >= r) {
mn[id] = min(mn[id], v);
return;
}
ll mid = (l+r)/2;
updMin(2*id, l, mid, s, e, v);
updMin(2*id+1, mid, r, s, e, v);
}
ll getMin(ll id, ll l, ll r, ll p) {
if (r - l == 1) return mn[id];
ll mid = (l+r)/2;
if (p < mid) return min(mn[id], getMin(2*id, l, mid, p));
return min(mn[id], getMin(2*id+1, mid, r, p));
}
void updMax(ll id, ll l, ll r, ll s, ll e, ll v) {
if (s >= r || e <= l) return;
if (s <= l && e >= r) {
mx[id] = max(mx[id], v);
return;
}
ll mid = (l+r)/2;
updMax(2*id, l, mid, s, e, v);
updMax(2*id+1, mid, r, s, e, v);
}
ll getMax(ll id, ll l, ll r, ll p) {
if (r - l == 1) return mx[id];
ll mid = (l+r)/2;
if (p < mid) return max(mx[id], getMax(2*id, l, mid, p));
return max(mx[id], getMax(2*id+1, mid, r, p));
}
int main() {
FastIO
cin >> n >> m >> q;
for (ll i = 1; i < n; i++) {
ll v, u;
cin >> v >> u;
}
for (ll i = 1; i <= n; i++) {
updMin(1, 1, n+1, i, i+1, i);
updMax(1, 1, n+1, i, i+1, i);
}
for (ll i = 1; i <= m; i++) {
ll p;
cin >> p;
upd(1, 1, n+1, p);
a[p] = 1 - a[p];
if (a[p] == 1) {
ll s = 0, e = 0, l = 1, r = p-1;
if (get(1, 1, n+1, p-1, p) == 0) s = p;
else if (get(1, 1, n+1, 1, p) == p-1) {
s = 1;
} else {
while (r - l > 1) {
ll mid = (l+r)/2;
if (get(1, 1, n+1, mid, p) == p-mid) r = mid;
else l = mid;
}
s = r;
}
l = p, r = n;
while (r - l > 1) {
ll mid = (l+r)/2;
if (get(1, 1, n+1, p, mid+1) == mid-p+1) l = mid;
else r = mid;
}
e = l+1;
updMin(1, 1, n+1, s, e+1, getMin(1, 1, n+1, s));
updMax(1, 1, n+1, s, e+1, getMax(1, 1, n+1, e));
}
}
while (q--) {
ll p; cin >> p;
cout << getMax(1, 1, n+1, p) - getMin(1, 1, n+1, p) + 1 << '\n';
}
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |