题目大意

有 $n$ 个城市构成一棵树，$m$ 个游客初始分布在各个城市。需要处理三种操作：

1. 移动操作 (t l r c)：编号 $l$ 到 $r$ 的游客移动到城市 $c$，移动距离会减少满意度
2. 活动操作 (e c d)：在城市 $c$ 举办活动，该城市所有游客满意度增加 $d$
3. 查询操作 (q v)：查询第 $v$ 个游客当前的满意度

算法思路

核心思想

使用区间维护 + 树上距离计算来高效处理大量游客的移动和查询。

关键技术

1. 区间合并与分裂

• 使用 set 维护连续的游客区间，每个区间记录所在城市
• 当移动操作覆盖部分区间时，进行区间分裂和合并
• 保证区间不重叠且覆盖所有游客

2. 满意度计算

• 树状数组记录每个游客的"基础满意度"
• tot数组记录每个城市的"活动累积满意度"
• 最终满意度 = 基础满意度 + 所在城市的累积满意度

3. 树上距离计算

• 使用DFS序 + ST表求LCA
• 通过LCA计算树上两点间距离：$dep[u] + dep[v] - 2 \times dep[lca]$

代码详解

数据结构定义

struct BIT{
    ll val[N];
    void upd(int x,ll v){  // 树状数组区间更新
        ++x;
        while(x<N){
            val[x]+=v;
            x+=x&(-x);
        }
    }
    ll qry(int x){  // 单点查询
        ll ret=0;
        ++x;
        while(x){
            ret+=val[x];
            x-=x&(-x);
        }
        return ret;
    }
}bit;

set<pair<pair<int,int>,int> > rgs;  // 维护区间: {{l, r}, 城市}
ll tot[N];  // 每个城市的累积活动满意度

树的预处理

void dfs(int x,int lst){
    dfn[x]=++dcnt;        // DFS序
    f[0][dcnt]=lst;       // 父节点
    for(auto &y:vt[x]) if(y!=lst){
        dep[y]=dep[x]+1;  // 深度
        dfs(y,x);
    }
}

// ST表预处理LCA
for(int i=1;i<18;i++) for(int j=2;j+(1<<i)-1<=n;j++){
    f[i][j]=(dfn[f[i-1][j]]<dfn[f[i-1][j+(1<<(i-1))]]?f[i-1][j]:f[i-1][j+(1<<(i-1))]);
}

移动操作处理

if(o=='t'){
    int l,r,c;
    cin>>l>>r>>c;
    l--,r--,c--;
    
    // 分裂被覆盖的区间
    while(true){
        auto it=rgs.lower_bound(make_pair(make_pair(r+1,-1),-1));
        if(it==rgs.begin()||prev(it)->F.S<l) break;
        it--;
        auto [tl,tr]=it->F;
        int x=it->S;
        rgs.erase(it);
        
        // 处理区间边界
        if(tr>r) rgs.insert(make_pair(make_pair(r+1,tr),x)),tr=r;
        if(tl<l) rgs.insert(make_pair(make_pair(tl,l-1),x)),tl=l;
        
        // 更新满意度：减去原城市累积值，加上移动距离
        bit.upd(tl,tot[x]-getdis(x,c));
        bit.upd(tr+1,-tot[x]+getdis(x,c));
    }
    
    // 插入新区间
    rgs.insert(make_pair(make_pair(l,r),c));
    bit.upd(l,-tot[c]);      // 加上新城市累积值
    bit.upd(r+1,tot[c]);
}

活动操作

else if(o=='e'){
    int x,w;
    cin>>x>>w;
    x--;
    tot[x]+=w;  // 增加该城市的累积满意度
}

查询操作

else{
    int x;
    cin>>x;
    x--;
    // 找到游客所在区间和城市
    int id=prev(rgs.lower_bound(make_pair(make_pair(x+1,-1),-1)))->S;
    // 基础满意度 + 城市累积满意度
    cout<<bit.qry(x)+tot[id]<<'\n';
}

关键点分析

1. 区间维护

• 使用set维护区间，保证$O(\log m)$的查询和更新
• 每次移动操作最多分裂2个区间，均摊复杂度优秀

2. 满意度分离计算

• 基础满意度：通过树状数组维护，记录移动带来的变化
• 城市累积满意度：直接记录，查询时实时相加
• 避免每次活动操作都更新所有相关游客

3. 树上距离高效计算

• 预处理$O(n \log n)$，每次查询$O(1)$
• 支持快速计算任意两点间距离

复杂度分析

• 预处理：DFS $O(n)$，ST表 $O(n \log n)$
• 移动操作：均摊 $O(\log m)$ 次区间操作，每次 $O(\log m)$
• 活动操作：$O(1)$
• 查询操作：$O(\log m)$

总体复杂度：$O((n+q) \log n)$