bzoj-2243染色
タイトル:
ルートのないツリーとツリー上の各ノードの初期色を指定します.
その後、m回の操作を行う.
C:xからyへの経路のすべての点をある色に染めます.
Q:xからyへのパスに何色のブロックが通っているかを問い合わせる.
n,m<=10^5;
問題:
裸の木の鎖の断面は、修正するときは遅延マークで維持します.
しかし、色が0の可能性があることに注意して、私は単独でboolの配列を開いてマークがあるかどうかを維持しました.
2つの区間をマージするときは、2つの端点の色が同じかどうかを判断します.
同じように端点をマージする場合は、答え-1です.
ツリーチェーン間を切り替えるときも端点を調べます.
そして私はWAになりました!
あとで調べろ、調べろ...
テンプレートが間違っていることに気づいた!それは正しいと思います...
前のコードと比較して違うことに気づいたんだな
LCAのような過程でxを交換し、yはdeep[top[x]私はdeep[x]ブログの中に木切れがないことに気づいて1発書いて伝わってきた後、テンプレートとして写します==;
コード:
ルートのないツリーとツリー上の各ノードの初期色を指定します.
その後、m回の操作を行う.
C:xからyへの経路のすべての点をある色に染めます.
Q:xからyへのパスに何色のブロックが通っているかを問い合わせる.
n,m<=10^5;
問題:
裸の木の鎖の断面は、修正するときは遅延マークで維持します.
しかし、色が0の可能性があることに注意して、私は単独でboolの配列を開いてマークがあるかどうかを維持しました.
2つの区間をマージするときは、2つの端点の色が同じかどうかを判断します.
同じように端点をマージする場合は、答え-1です.
ツリーチェーン間を切り替えるときも端点を調べます.
そして私はWAになりました!
あとで調べろ、調べろ...
テンプレートが間違っていることに気づいた!それは正しいと思います...
前のコードと比較して違うことに気づいたんだな
LCAのような過程でxを交換し、yはdeep[top[x]
コード:
#include<vector>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 110000
#define lson l,mid,no<<1
#define rson mid+1,r,no<<1|1
using namespace std;
vector<int>to[N];
int a[N], fa[N], ch[N], size[N], top[N], deep[N];
int p[N], rank[N], cov[N << 2], L[N << 2], R[N << 2], sum[N << 2], n, tot;
bool is[N << 2];
char str[10];
void dfs1(int x, int d, int pre)
{
deep[x] = d, fa[x] = pre, size[x] = 1;
int i, y;
for (i = 0; i < to[x].size(); i++)
{
if ((y = to[x][i]) != pre)
{
dfs1(y, d + 1, x);
size[x] += size[y];
if (size[y]>size[ch[x]])
ch[x] = y;
}
}
}
void dfs2(int x, int t)
{
top[x] = t;
p[x] = ++tot;
rank[tot] = x;
if (ch[x])
dfs2(ch[x], t);
int i, y;
for (i = 0; i < to[x].size(); i++)
{
y = to[x][i];
if (y != fa[x] && y != ch[x])
dfs2(y, y);
}
}
void Pushup(int no)
{
L[no] = L[no << 1], R[no] = R[no << 1 | 1];
sum[no] = sum[no << 1] + sum[no << 1 | 1] -(R[no << 1] == L[no << 1 | 1]);
}
void Pushdown(int no)
{
if (is[no])
{
sum[no << 1] = sum[no << 1 | 1] = 1;
is[no << 1] = is[no << 1 | 1] = 1;
cov[no << 1] = cov[no << 1 | 1] = cov[no];
L[no << 1] = R[no << 1] = L[no << 1 | 1] = R[no << 1 | 1] = cov[no];
cov[no] = is[no] = 0;
}
}
void Build(int l, int r, int no)
{
if (l == r)
L[no] = R[no] = a[rank[l]],
sum[no] = 1;
else
{
int mid = (l + r) >> 1;
Build(lson);
Build(rson);
Pushup(no);
}
}
void update(int l, int r, int no, int st, int en, int v)
{
if (st <= l&&r <= en)
{
L[no] = R[no] = v;
cov[no] = v;
sum[no] = 1;
is[no] = 1;
}
else
{
int mid = (l + r) >> 1;
Pushdown(no);
if (en <= mid) update(lson, st, en, v);
else if (st > mid) update(rson, st, en, v);
else update(lson, st, en, v), update(rson, st, en, v);
Pushup(no);
}
}
int get(int l, int r, int no, int k)
{
if (l == r)
return L[no];
else
{
int mid = (l + r) >> 1;
Pushdown(no);
if (k <= mid) return get(lson, k);
else return get(rson, k);
}
}
int query(int l, int r, int no, int st, int en)
{
if (st <= l&&r <= en)
return sum[no];
else
{
int mid = (l + r) >> 1;
Pushdown(no);
if (en <= mid) return query(lson, st, en);
else if (st > mid) return query(rson, st, en);
else
{
int ret = query(lson, st, en) + query(rson, st, en);
if (R[no << 1] == L[no << 1 | 1])
ret--;
return ret;
}
}
}
void op_C(int x, int y, int v)
{
while (top[x] != top[y])
{
if (deep[top[x]] < deep[top[y]]) swap(x, y);
update(1, n, 1, p[top[x]], p[x], v);
x = fa[top[x]];
}
if (deep[x] < deep[y]) swap(x, y);
update(1, n, 1, p[y], p[x], v);
}
int op_Q(int x, int y)
{
int ret = 0;
while (top[x] != top[y])
{
if (deep[top[x]] < deep[top[y]]) swap(x, y);
ret += query(1, n, 1, p[top[x]], p[x]);
if (get(1, n, 1, p[top[x]]) == get(1, n, 1, p[fa[top[x]]]))
ret--;
x = fa[top[x]];
}
if (deep[x] < deep[y]) swap(x, y);
ret += query(1, n, 1, p[y], p[x]);
return ret;
}
int main()
{
int m, i, j, k, x, y, v;
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
scanf("%d", a + i);
for (i = 1; i < n; i++)
{
scanf("%d%d", &x, &y);
to[x].push_back(y);
to[y].push_back(x);
}
dfs1(1, 1, 0);
dfs2(1, 0);
Build(1, n, 1);
for (i = 1; i <= m; i++)
{
scanf("%s", str);
if (str[0] == 'C')
{
scanf("%d%d%d", &x, &y, &v);
op_C(x, y, v);
}
else
{
scanf("%d%d", &x, &y);
printf("%d
", op_Q(x, y));
}
}
return 0;
}