区间修改 单点查询
分析
这题不同于一般的线段树题,这题是在树上进行操作,因此为了将其转换为一般的区间操作,我们先对这颗树进行dfs
序编码,然后令一个节点代表的范围为他的子孙节点编码范围:
在查询的时候,节点的编号就可以用编码范围的左端点表示
#include <iostream>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#define bug1(g) cout<<"test: "<<g<<endl
#define bug2(g , i) cout<<"test: "<<g<<" "<<i<<endl
#define bug3(g , i , k) cout<<"test: "<<g<<" "<<i<<" "<<k<<endl
#define bug4(a , g , i , k) cout<<"test: "<<a<<" "<<g<<" "<<i<<" "<<k<<endl
#define all(x) x.begin(), x.end()
#define lb(x, y) lower_bound(all(x), y)
#define INF 0x3f3f3f3f
#define fi first
#define se second
#define met(a , b) memset(a , b , sizeof a);
#define pb push_back
using namespace std;
typedef long long LL ;
typedef pair<int , int> PII;
template <typename T> T chMa(T &x, T y) { if (y > x) x = y; return x; }
template <typename T> T chMi(T &x, T y) { if (y < x) x = y; return x; }
#define lc u << 1
#define rc u << 1 | 1
const int N = 50010;
vector<int> edge[N];
int din[N];
PII seg[N];
int idx;
struct Node {
int l, r, v;
}tr[N * 4];
void build (int u, int l, int r) {
tr[u] = {l, r, -1};
if (l == r) return;
int mid = l + r >> 1;
build (lc, l, mid), build (rc, mid + 1, r);
}
void pushdown (int u) {
if (~tr[u].v) {
tr[lc].v = tr[rc].v = tr[u].v;
tr[u].v = -1;
}
}
void modify (int u, int l, int r, int v) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].v = v;
return;
}
pushdown (u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify (lc, l, r, v);
if (r > mid) modify (rc, l, r, v);
}
int query (int u, int x) {
if (~tr[u].v) return tr[u].v;
if (tr[u].l == tr[u].r) return -1;
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) return query (lc, x);
return query (rc, x);
}
void dfs (int u)
{
seg[u].fi = ++ idx;
for (int &v : edge[u]) dfs (v);
seg[u].se = idx;
}
void solve()
{
int n;
cin >> n;
build (1, 1, n);
idx = 0;
for (int i = 1; i <= n; i++) edge[i].clear();
memset(din, 0, (n + 1) * 4);
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
edge[v].pb(u);
din[u]++;
}
for (int i = 1; i <= n; i++) {
if (!din[i]) {
dfs (i);
}
}
int m;
cin >> m;
while (m--) {
char op[2];
int x, y;
cin >> op;
if (*op == 'C') {
cin >> x;
cout << query (1, seg[x].fi) << endl;
} else {
cin >> x >> y;
modify (1, seg[x].fi, seg[x].se, y);
}
}
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int T = 1;
cin >> T;
for(int turn = 1 ; turn <= T ; turn++) {
cout << "Case #" << turn << ":\n", solve();
}
}
他不是一颗一般的线段树,你看这棵树又长又宽
你看这个树画的多丑
日常看见美女发题解,虽然看不懂
你哪里看出我是
美女
了头像哈哈哈
网络水太深,你把握不住呀
惊到