이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44
using namespace std;
const int MAXN = (int) 2e5;
const int LOG = 19;
vector <int> g[MAXN + 1];
int lvl[MAXN + 1];
int rmq[2 * MAXN + 1][LOG + 1];
int first[MAXN + 1], sz;
void dfs(int nod, int par) {
rmq[++sz][0] = nod;
first[nod] = sz;
lvl[nod] = lvl[par] + 1;
for(auto it : g[nod]) {
if(it != par) {
dfs(it, nod);
rmq[++sz][0] = nod;
}
}
}
char lg[2 * MAXN + 1];
inline void prec(int n) {
dfs(1, 0);
for(int i = 2; i <= sz; i++) {
lg[i] = lg[i >> 1] + 1;
}
for(int bit = 1; (1 << bit) <= sz; bit++) {
for(int i = 1; i + (1 << bit) <= sz + 1; i++) {
int a = rmq[i][bit - 1], b = rmq[i + (1 << (bit - 1))][bit - 1];
if(lvl[a] < lvl[b])
rmq[i][bit] = a;
else
rmq[i][bit] = b;
}
}
}
inline int get(int x, int y) {
x = first[x], y = first[y];
if(x > y) {
swap(x, y);
}
int bit = lg[y - x + 1];
int a = rmq[x][bit], b = rmq[y - (1 << bit) + 1][bit];
if(lvl[a] < lvl[b])
return a;
return b;
}
int arr[MAXN + 1];
struct SegTree {
vector < multiset <int> > aint;
int n;
SegTree(int _n) {
n = _n;
aint.resize(4 * n + 1);
}
void update(int nod, int left, int right, int pos, int val, bool type) {
if(type) {
aint[nod].insert(val);
}
else {
aint[nod].erase(aint[nod].find(val));
}
if(left == right) {
return ;
}
else {
int mid = (left + right) / 2;
if(pos <= mid)
update(2 * nod, left, mid, pos, val, type);
else
update(2 * nod + 1, mid + 1, right, pos, val, type);
}
}
pair <bool, int> query(int nod, int left, int right, int l, int r, int val) {
if(l <= left && right <= r) {
if(left == right) {
if(*aint[nod].begin() == val) {
return {1, left};
}
return {0, 0};
}
auto it = aint[nod].find(val);
pair <int, int> ans = {0, 0};
if(it != aint[nod].end()) {
int mid = (left + right) / 2;
if(aint[2 * nod].find(val) != aint[2 * nod].end()) {
ans = query(2 * nod, left, mid, l, r, val);
}
else {
ans = query(2 * nod + 1, mid + 1, right, l, r, val);
}
}
return ans;
}
else {
int mid = (left + right) / 2;
pair <int, int> ans = {0, 0};
if(l <= mid)
ans = query(2 * nod, left, mid, l, r, val);
if(mid < r && ans.first == 0) {
pair <int, int> aux = query(2 * nod + 1, mid + 1, right, l, r, val);
if(aux.first == 1) {
ans = aux;
}
}
return ans;
}
}
};
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, n, m, q;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> q;
for(i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
prec(n);
for(i = 1; i<= m; i++) {
cin >> arr[i];
}
SegTree segt1(m), segt2(m);
for(i = 1; i <= m; i++) {
segt1.update(1, 1, m, i, arr[i], 1);
if(i < m) {
segt2.update(1, 1, m, i, get(arr[i], arr[i + 1]), 1);
}
}
while(q > 0) {
q--;
int type;
cin >> type;
if(type == 1) {
int pos, nod;
cin >> pos >> nod;
segt1.update(1, 1, m, pos, arr[pos], 0);
segt1.update(1, 1, m, pos, nod, 1);
if(pos > 1) {
segt2.update(1, 1, m, pos - 1, get(arr[pos - 1], arr[pos]), 0);
segt2.update(1, 1, m, pos - 1, get(arr[pos - 1], nod), 1);
}
if(pos < m) {
segt2.update(1, 1, m, pos, get(arr[pos], arr[pos + 1]), 0);
segt2.update(1, 1, m, pos, get(nod, arr[pos + 1]), 1);
}
arr[pos] = nod;
}
else {
int l, r, nod;
cin >> l >> r >> nod;
pair <int, int> ans = {0, 0};
ans = segt1.query(1, 1, m, l, r, nod);
if(ans.first == 0) {
if(l < r) {
ans = segt2.query(1, 1, m, l, r - 1, nod);
}
if(ans.first) {
cout << ans.second << " " << ans.second + 1 << "\n";
}
else {
cout << -1 << " " << -1 << "\n";
}
}
else {
cout << ans.second << " " << ans.second << "\n";
}
}
}
//cin.close();
//cout.close();
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... |