NC50487. 染色
描述
输入描述
第一行包括两个整数n,m，表示节点数和操作数；
第二行包含n个正整数表示n个节点的初始颜色；
接下来若干行包含两个整数x和y，表示x和y之间有一条无向边；
接下来若干行每行描述一个操作：
C a b c表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）染上颜色；
Q a b表示这是一个询问操作，把节点a到节点b路径上（包括a和b）的颜色段数量。
输出描述
对于每个询问操作，输出一行询问结果。
示例1
输入:
6 5 2 2 1 2 1 1 1 2 1 3 2 4 2 5 2 6 Q 3 5 C 2 1 1 Q 3 5 C 5 1 2 Q 3 5
输出:
3 1 2
Java 解法, 执行用时: 1633ms, 内存消耗: 45544K, 提交时间: 2021-09-21 08:50:45
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String args[]){
new Main().solve();
}
Scanner in;
PrintWriter out;
public void solve(){
in = new Scanner(System.in);
out = new PrintWriter(System.out);
go();
}
long s[];
long ll[];
long rr[];
long setv[];
void build(int id,int left,int right){
if(left==right){
s[id] = 1;
ll[id] = rr[id] = wt[pt[left]];
return;
}
int mid = (left+right)/2;
build(id*2,left,mid);
build(id*2+1,mid+1,right);
s[id] = s[id*2] + s[id*2+1];
if(rr[id*2]==ll[id*2+1]){
s[id]--;
}
rr[id] = rr[id*2+1];
ll[id] = ll[id*2];
}
long[] qry(int id,int left,int right,int l,int r){
if(left>=l&&right<=r){
return new long[]{s[id],ll[id],rr[id]};
}else if(left>r||right<l){
return new long[]{0,-1,-1};
}
int mid = (left+right)/2;
if(setv[id]!=-1){
setv[id*2] = setv[id*2+1] = setv[id];
ll[id*2]=rr[id*2]=ll[id*2+1]=rr[id*2+1] = setv[id];
s[id*2] = s[id*2+1] = 1;
setv[id] = -1;
}
long v1[] = qry(id*2,left,mid,l,r);
long v2[] = qry(id*2+1,mid+1,right,l,r);
s[id] = s[id*2] + s[id*2+1];
if(rr[id*2]==ll[id*2+1]){
s[id]--;
}
rr[id] = rr[id*2+1];
ll[id] = ll[id*2];
if(v1[0]==0){
return v2;
}else if(v2[0]==0){
return v1;
}
long add = 0;
if(v1[2]==v2[1]){
add = -1;
}
long le = v1[1];
long ri = v2[2];
return new long[]{v1[0]+v2[0]+add, le, ri};
}
// void update(int id,int left,int right,int l,long val){
// if(left>l||right<l){
// return;
// }else if(left==right){
// s[id] += val;
// return;
// }
// int mid = (left+right)/2;
// if(mx[id]!=0){
// mx[id*2] += mx[id];
// mx[id*2+1] += mx[id];
//
// s[id*2] += mx[id]*(mid-left+1);
// s[id*2+1] += mx[id]*(right-(mid+1)+1);
//
//
// mx[id] = 0;
// }
//
// update(id*2,left,mid,l,val);
// update(id*2+1,mid+1,right,l,val);
// s[id] = s[id*2] + s[id*2+1];
//
// }
void update(int id,int left,int right,int l,int r,long val){
if(left>r||right<l){
return;
}else if(left>=l&&right<=r){
setv[id] = val;
ll[id] = val;
rr[id] = val;
s[id] = 1;
return;
}
int mid = (left+right)/2;
if(setv[id]!=-1){
setv[id*2] = setv[id*2+1] = setv[id];
ll[id*2]=rr[id*2]=ll[id*2+1]=rr[id*2+1] = setv[id];
s[id*2] = s[id*2+1] = 1;
setv[id] = -1;
}
update(id*2,left,mid,l,r,val);
update(id*2+1,mid+1,right,l,r,val);
s[id] = s[id*2] + s[id*2+1];
if(rr[id*2]==ll[id*2+1]){
s[id]--;
}
rr[id] = rr[id*2+1];
ll[id] = ll[id*2];
}
int h[],ne[],to[],wt[];
int ct = 0;
void add(int u,int v){
to[ct] = v;
ne[ct] = h[u];
h[u] = ct++;
}
int n;
void go(){
n = in.nextInt();
int q = in.nextInt();
h = new int[n];
Arrays.fill(h,-1);
ne = new int[2*(n-1)];
to = new int[2*(n-1)];
wt = new int[n];
fa = new int[n];
dep = new int[n];
top = new int[n];
son = new int[n];
sz = new int[n];
Arrays.fill(sz,1);
dfn = new int[n];
pt = new int[n];
gpt = new int[n];
stk = new int[n];
for(int i= 0;i<n;++i){
wt[i] = in.nextInt();
}
for(int i=0;i<n-1;++i){
int u = in.nextInt()-1;
int v = in.nextInt()-1;
add(u,v);
add(v,u);
}
// dfs1(0);
// dfs2(0);
treeLink(0);
s = new long[n*4];
ll = new long[n*4];
rr = new long[n*4];
setv = new long[n*4];
Arrays.fill(setv,-1);
build(1,0,n-1);
for(int i=0;i<q;++i){
String c = in.next();
if("C".equals(c)){
int u = in.nextInt()-1;
int v = in.nextInt()-1;
int w = in.nextInt();
while(top[u]!=top[v]){
if(dep[top[u]]>=dep[top[v]]){
update(1,0,n-1,dfn[top[u]],dfn[u],w);
u = fa[top[u]];
}else{
update(1,0,n-1,dfn[top[v]],dfn[v],w);
v = fa[top[v]];
}
}
if(dep[u]>=dep[v]){
update(1,0,n-1,dfn[v],dfn[u],w);
}else{
update(1,0,n-1,dfn[u],dfn[v],w);
}
}else{
int u = in.nextInt()-1;
int v = in.nextInt()-1;
long lu = -1000;
long lv = -1000;
long r= 0;
while(top[u]!=top[v]){
if(dep[top[u]]>=dep[top[v]]){
long p[] = qry(1,0,n-1,dfn[top[u]],dfn[u]);
r += p[0];
if(lu==p[2]){
r--;
}
u = fa[top[u]];
lu = p[1];
}else{
long p[] = qry(1,0,n-1,dfn[top[v]],dfn[v]);
r += p[0];
if(lv==p[2]){
r--;
}
v = fa[top[v]];
lv = p[1];
}
}
if(dep[u]>=dep[v]){
long p[] = qry(1,0,n-1,dfn[v],dfn[u]);
r += p[0];
if (p[1] == lv) {
r--;
}
if (p[2] == lu) {
r--;
}
}else{
long p[] = qry(1,0,n-1,dfn[u],dfn[v]);
r += p[0];
if (p[1] == lu) {
r--;
}
if (p[2] == lv) {
r--;
}
}
out.println(r);
}
}
out.close();
}
int fa[],dep[],top[],son[],sz[],dfn[],pt[],gpt[],stk[];
void dfs1(int rt){
sz[rt] = 1;
for(int i=h[rt];i!=-1;i=ne[i]){
int v = to[i];
if(v==fa[rt]) continue;
fa[v] = rt;
dep[v] = dep[rt] + 1;
dfs1(v);
sz[rt] += sz[v];
if(son[rt]==0||sz[son[rt]]<sz[v]){
son[rt] = v;
}
}
}
int id = 0;
void dfs2(int rt){
dfn[rt] = id;
pt[id++] = rt;
if(son[rt]!=0){
top[son[rt]] = top[rt];
dfs2(son[rt]);
}
for(int i=h[rt];i!=-1;i=ne[i]){
int v = to[i];
if(v==fa[rt]||v==son[rt]) continue;
top[v] = v;
dfs2(v);
}
}
public void treeLink(int ort){
int p = 0;
stk[p++] = ort;
int clock = 0;
int rt = -1;
while(p>0) {
rt = stk[--p];
gpt[clock++] = rt;
for (int i = h[rt]; i != -1; i = ne[i]) {
int v = to[i];
if (fa[rt] == v) continue;
fa[v] = rt;
dep[v] = dep[rt] + 1;
stk[p++] = v;
}
}
for(int i=n-1;i>0;--i){
int cur = gpt[i];
int fat = fa[cur];
sz[fat] += sz[cur];
if (son[fat]== 0 || sz[cur] > sz[son[fat]]) {
son[fat] = cur;
}
}
// for (int i = 1; i < n; i++) top[gpt[i]] = gpt[i] == son[fa[gpt[i]]] ? top[fa[gpt[i]]] : gpt[i];
p = 0;
stk[p++] = ort;
while(p>0) {
rt = stk[--p];
dfn[rt] = id;
pt[id++] = rt;
for (int i = h[rt]; i != -1; i = ne[i]) {
int v = to[i];
if (fa[rt] == v || v == son[rt]) continue;
top[v] = v;
stk[p++] = v;
}
if(son[rt]!=0) {
top[son[rt]] = top[rt];
stk[p++] = son[rt];
}
}
}
}
C++14(g++5.4) 解法, 执行用时: 396ms, 内存消耗: 17528K, 提交时间: 2020-01-28 18:37:15
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+1;
int N, M;
vector<int> G[MAXN];
int fa[MAXN];
int dep[MAXN];
int siz[MAXN];
int son[MAXN];
int top[MAXN];
int dfn[MAXN];
int rnk[MAXN];
int clk;
void dfs1(int s, int f) {
fa[s] = f;
siz[s] = 1;
dep[s] = dep[f] + 1;
for (auto t: G[s]) if (t != f) {
dfs1(t, s);
siz[s] += siz[t];
if (siz[son[s]] < siz[t]) son[s] = t;
}
}
void dfs2(int s, int f, int tp) {
top[s] = tp;
dfn[s] = ++clk;
rnk[clk] = s;
if (son[s]) dfs2(son[s], s, tp);
for (auto t: G[s]) if (t != f && t != son[s]) dfs2(t, s, t);
}
int color_left[MAXN*4];
int color_right[MAXN*4];
int sum[MAXN*4];
int delay[MAXN*4];
int v_color[MAXN];
void change(int o, int l, int r, int L, int R, int c);
void push_down(int o, int l, int m, int r) {
if (delay[o] == 0) return;
change(o*2, l, m, l, m, delay[o]);
change(o*2+1, m+1, r, m+1, r, delay[o]);
delay[o] = 0;
}
void change(int o, int l, int r, int L, int R, int c) {
if (R < l || r < L) return;
if (L <= l && r <= R) {
delay[o] = color_left[o] = color_right[o] = c;
sum[o] = 1;
return;
}
int m = (l+r)/2;
push_down(o, l, m, r);
change(o*2, l, m, L, R, c);
change(o*2+1, m+1, r, L, R, c);
sum[o] = sum[o*2] + sum[o*2+1];
color_left[o] = color_left[o*2];
color_right[o] = color_right[o*2+1];
if (sum[o*2] && sum[o*2+1] && color_right[o*2] == color_left[o*2+1]) sum[o]--;
}
int query_sum(int o, int l, int r, int L, int R) {
if (R < l || r < L) return 0;
if (L <= l && r <= R) return sum[o];
int m = (l+r)/2;
int tot = 0;
push_down(o, l, m, r);
int ltot = query_sum(o*2, l, m, L, R);
int rtot = query_sum(o*2+1, m+1, r, L, R);
tot = ltot + rtot;
if (ltot != 0 && rtot != 0 && color_right[o*2] == color_left[o*2+1]) tot--;
return tot;
}
int query_color(int o, int l, int r, int idx) {
if (delay[o]) return delay[o];
int m = (l+r)/2;
if (idx <= m) return query_color(o*2, l, m, idx);
return query_color(o*2+1, m+1, r, idx);
}
int main() {
ios::sync_with_stdio(false);
cin >> N >> M;
for (int i = 1; i <= N; i++) cin >> v_color[i];
for (int i = 1; i <= N; i++) assert(v_color[i] != 0);
for (int i = 1; i < N; i++) {
int u, v; cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(1, 0);
dfs2(1, 0, 1);
for (int i = 1; i <= N; i++) change(1, 1, N, dfn[i], dfn[i], v_color[i]);
while (M--) {
string op; cin >> op;
if (op == "C") {
int a, b, c; cin >> a >> b >> c;
assert(c!=0);
while (top[a] != top[b]) {
if (dep[top[a]] > dep[top[b]]) swap(a, b);
change(1, 1, N, dfn[top[b]], dfn[b], c);
b = fa[top[b]];
}
if (dep[a] > dep[b]) swap(a, b);
change(1, 1, N, dfn[a], dfn[b], c);
} else {
int a, b; cin >> a >> b;
int tot = 0;
int last_a = 0, last_b = 0;
while (top[a] != top[b]) {
// cout << a << " " << b << " " << last_a << " " << last_b << endl;
if (dep[top[a]] > dep[top[b]]) swap(a, b), swap(last_a, last_b);
tot += query_sum(1, 1, N, dfn[top[b]], dfn[b]);
if (query_color(1, 1, N, dfn[b]) == last_b) tot--;
last_b = query_color(1, 1, N, dfn[top[b]]);
b = fa[top[b]];
}
if (dep[a] > dep[b]) swap(a, b), swap(last_a, last_b);
tot += query_sum(1, 1, N, dfn[a], dfn[b]);
if (query_color(1, 1, N, dfn[b]) == last_b) tot--;
if (query_color(1, 1, N, dfn[a]) == last_a) tot--;
cout << tot << endl;
}
}
}
C++11(clang++ 3.9) 解法, 执行用时: 410ms, 内存消耗: 17608K, 提交时间: 2020-05-30 21:59:28
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
int N,M;
vector<int> G[MAXN];
int fa[MAXN];
int dep[MAXN];
int siz[MAXN];
int son[MAXN];
int top[MAXN];
int dfn[MAXN];
int rnk[MAXN];
int clk;
void dfs1(int s,int f)
{
fa[s]=f;
siz[s]=1;
dep[s]=dep[f]+1;
for(auto t:G[s])
if(t!=f)
{
dfs1(t,s);
siz[s]+=siz[t];
if(siz[son[s]]<siz[t])
son[s]=t;
}
}
void dfs2(int s,int f,int tp)
{
top[s]=tp;
dfn[s]=++clk;
rnk[clk]=s;
if(son[s])
dfs2(son[s],s,tp);
for(auto t:G[s])
if(t!=f&&t!=son[s])
dfs2(t,s,t);
}
int color_left[MAXN*4];
int color_right[MAXN*4];
int sum[MAXN*4];
int delay[MAXN*4];
int v_color[MAXN];
void change(int o,int l,int r,int L,int R,int c);
void push_down(int o,int l,int m,int r)
{
if(delay[o]==0) return;
change(o*2,l,m,l,m,delay[o]);
change(o*2+1,m+1,r,m+1,r,delay[o]);
delay[o]=0;
}
void change(int o,int l,int r,int L,int R,int c)
{
if(R<l||r<L) return;
if(L<=l&&r<=R)
{
delay[o]=color_left[o]=color_right[o]=c;
sum[o]=1;
return;
}
int m=(l+r)/2;
push_down(o,l,m,r);
change(o*2,l,m,L,R,c);
change(o*2+1,m+1,r,L,R,c);
sum[o]=sum[o*2]+sum[o*2+1];
color_left[o]=color_left[o*2];
color_right[o]=color_right[o*2+1];
if(sum[o*2]&&sum[o*2+1]&&color_right[o*2]==color_left[o*2+1])
sum[o]--;
}
int query_sum(int o,int l,int r,int L,int R)
{
if(R<l||r<L) return 0;
if(L<=l&&r<=R) return sum[o];
int m=(l+r)/2;
int tot=0;
push_down(o,l,m,r);
int ltot=query_sum(o*2,l,m,L,R);
int rtot=query_sum(o*2+1,m+1,r,L,R);
tot=ltot+rtot;
if(ltot!=0&&rtot!=0&&color_right[o*2]==color_left[o*2+1])
tot--;
return tot;
}
int query_color(int o,int l,int r,int idx)
{
if(delay[o]) return delay[o];
int m=(l+r)/2;
if(idx<=m) return query_color(o*2,l,m,idx);
return query_color(o*2+1,m+1,r,idx);
}
int main()
{
ios::sync_with_stdio(false);
cin>>N>>M;
for(int i=1;i<=N;i++)
cin>>v_color[i];
for(int i=1;i<=N;i++)
assert(v_color[i]!=0);
for(int i=1;i<N;i++)
{
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(1,0);
dfs2(1,0,1);
for(int i=1;i<=N;i++)
change(1,1,N,dfn[i],dfn[i],v_color[i]);
while(M--)
{
string op;
cin>>op;
if(op=="C")
{
int a,b,c;
cin>>a>>b>>c;
assert(c!=0);
while(top[a]!=top[b])
{
if(dep[top[a]]>dep[top[b]]) swap(a,b);
change(1,1,N,dfn[top[b]],dfn[b],c);
b=fa[top[b]];
}
if(dep[a]>dep[b]) swap(a,b);
change(1,1,N,dfn[a],dfn[b],c);
}
else
{
int a,b;
cin>>a>>b;
int tot=0;
int last_a=0,last_b=0;
while(top[a]!=top[b])
{
if(dep[top[a]]>dep[top[b]]) swap(a,b),swap(last_a,last_b);
tot+=query_sum(1,1,N,dfn[top[b]],dfn[b]);
if(query_color(1,1,N,dfn[b])==last_b) tot--;
last_b=query_color(1,1,N,dfn[top[b]]);
b=fa[top[b]];
}
if(dep[a]>dep[b]) swap(a,b),swap(last_a,last_b);
tot+=query_sum(1,1,N,dfn[a],dfn[b]);
if(query_color(1,1,N,dfn[b])==last_b) tot--;
if(query_color(1,1,N,dfn[a])==last_a) tot--;
cout<<tot<<endl;
}
}
}