P4074 [WC2013]糖果公园 树上莫队带修改

2024-04-03 17:58:40

题目链接

 

Candyland 有一座糖果公园，公园里不仅有美丽的风景、好玩的游乐项目，还有许多免费糖果的发放点，这引来了许多贪吃的小朋友来糖果公园游玩。

糖果公园的结构十分奇特，它由 nn 个游览点构成，每个游览点都有一个糖果发放处，我们可以依次将游览点编号为 11 至 nn。有 nn – 11 条双向道路连接着这些游览点，并且整个糖果公园都是连通的，即从任何一个游览点出发都可以通过这些道路到达公园里的所有其它游览点。

糖果公园所发放的糖果种类非常丰富，总共有 mm 种，它们的编号依次为 11 至 mm。每一个糖果发放处都只发放某种特定的糖果，我们用 C_iCi​ 来表示 ii 号游览点的糖果。

来到公园里游玩的游客都不喜欢走回头路，他们总是从某个特定的游览点出发前往另一个特定的游览点，并游览途中的景点，这条路线一定是唯一的。他们经过每个游览点，都可以品尝到一颗对应种类的糖果。

大家对不同类型糖果的喜爱程度都不尽相同。 根据游客们的反馈打分，我们得到了糖果的美味指数， 第 ii 种糖果的美味指数为 V_iVi​。另外，如果一位游客反复地品尝同一种类的糖果，他肯定会觉得有一些腻。根据量化统计，我们得到了游客第 ii 次品尝某类糖果的新奇指数 W_iWi​。如果一位游客第 ii 次品尝第 jj 种糖果，那么他的愉悦指数 HH 将会增加对应的美味指数与新奇指数的乘积，即 V_jVj​×W_iWi​。这位游客游览公园的愉悦指数最终将是这些乘积的和。

当然，公园中每个糖果发放点所发放的糖果种类不一定是一成不变的。有时，一些糖果点所发放的糖果种类可能会更改（也只会是 mm 种中的一种），这样的目的是能够让游客们总是感受到惊喜。

糖果公园的工作人员小 A 接到了一个任务，那就是根据公园最近的数据统计出每位游客游玩公园的愉悦指数。但数学不好的小 A 一看到密密麻麻的数字就觉得头晕，作为小 A 最好的朋友，你决定帮他一把。

输入格式

从文件 park.in 中读入数据。

第一行包含三个正整数 nn, mm, qq， 分别表示游览点个数、 糖果种类数和操作次数。

第二行包含 mm 个正整数 V_1V1​, V_2V2​, …, V_mVm​。

第三行包含 nn 个正整数 W_1W1​, W_2W2​, …, W_nWn​。

第四行到第 nn + 22 行，每行包含两个正整数 A_iAi​, B_iBi​，表示这两个游览点之间有路径可以直接到达。

第 nn + 33 行包含 nn 个正整数 C_1C1​, C_2C2​, …, C_nCn​。

接下来 qq 行， 每行包含三个整数 TypeType, xx, yy，表示一次操作：

若 TypeType 为 00，则 11 ≤ xx ≤ nn， 11 ≤ yy ≤ mm，表示将编号为 xx 的游览点发放的糖果类型改为 yy；

若 TypeType 为 11，则 11 ≤ x, yx,y ≤ nn，表示对出发点为 xx，终止点为 yy 的路线询问愉悦指数。

输出格式

输出到文件 park.out 中。

按照输入的先后顺序，对于每个 TypeType 为 11 的操作输出一行，用一个正整数表示答案。

输入输出样例

输入 #1 
4 3 5
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 1 2
1 4 2
0 2 1
1 1 2
1 4 2
输出 #1 
84
131
27
84

 

题意：

给你n个节点，m种糖果，Q次询问

后面给出m个数，代表每种糖果的值vi

后面给n个数，表示某种糖果如果吃了i次，它的新奇指数Wi

后面n-1行，给出n-1条边

后面再给出n个值ci，表示每一个节点最初是哪种糖果

后面就是Q次询问。每次询问如果Type=0，那么就把把x这个位置糖果种类改成y。如果Type=1，那就输出[x,y]区间的所有愉悦数的和

愉悦数就是vi*wi

 

题解：

这就是树上莫队加普通带修改莫队

SP10707 COT2 - Count on a tree II 树上莫队

P1903 [国家集训队]数颜色 / 维护队列 带修改莫队 

 

我们通过欧拉序就可以转换成一个普通莫队

然后我们知道带修改莫队就是加了一个记录当前的时间变量time，如果现在的时间小于当前询问区间值得时间，那我们就需要把一些Modify操作执行，然后才是正确的结果

    for(ll i=1; i<=Q; ++i)
    {
        ll start = node[i].l, last = node[i].r, time = node[i].time, lca = node[i].lca;
        while(l < start) work(ord[l++]);
        while(l > start) work(ord[--l]);
        while(r < last) work(ord[++r]);
        while(r > last) work(ord[r--]);
        while(t < time) modify(++t);  //判断当前时间有没有遇到更新内容
        while(t > time) modify(t--);
        if(lca) work(lca);
        ans[node[i].id] = now;
        if(lca) work(lca);
    }

 

对于修改操作，我们需要判断当前需要修改的位置有没有影响到现在这个区间的答案，如果影响到了执行

if(vis[que[x].pos])  //如果vis数组值为1，就表示这个位置的值为答案做了贡献
    {                    //，所以如果这个位置改变就会影响答案
        work(que[x].pos);
        swap(val[que[x].pos], que[x].val);
        work(que[x].pos);
    }

 

否则就修改一下这个位置的值就可以了

swap(val[que[x].pos], que[x].val);

 

代码：

#include <map>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <cmath>
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5+10;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926;
const long long N = 1000006;
const double eps = 1e-10;
typedef long long ll;
#define mem(A, B) memset(A, B, sizeof(A))
#define lson rt<<1 , L, mid
#define rson rt<<1|1 , mid + 1, R
#define ls rt<<1
#define rs rt<<1|1
#define SIS std::ios::sync_with_stdiget_mod_new(z-x)o(false), cin.tie(0), cout.tie(0)
#define pll pair<long long, long long>
#define lowbit(abcd) (abcd & (-abcd))
#define max(a, b) ((a > b) ? (a) : (b))
#define min(a, b) ((a < b) ? (a) : (b))
inline ll read()    //读取整数
{
    ll res = 0;
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) res = (res << 1) + (res << 3) + (c ^ 48), c = getchar();
    return res;
}
ll arr[maxn],cnt[maxn],first[maxn],second[maxn],ans[maxn],belong[maxn];
ll cnte,vis[maxn],sizes,new_size,len,now,n,m,typ[maxn],que_len; //莫队相关
ll ord[maxn],val[maxn],head[maxn],depth[maxn],fa[maxn][30],nod_len;
//ord保存的是欧拉序
struct edge
{
    ll to,next;
} e[maxn];
struct Node
{
    ll l,r,lca,id,time;
} node[maxn];
struct query
{
    ll pos,val;
} que[maxn];
ll cmp(Node a, Node b)
{
    return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.r] ^ belong[b.r]) ? belong[a.r] < belong[b.r] : a.time < b.time );
}
void add_edge(ll x,ll y)
{
    e[++cnte]=(edge)
    {
        y,head[x]
    };
    head[x]=cnte;
    e[++cnte]=(edge)
    {
        x,head[y]
    };
    head[y]=cnte;
}
void dfs(ll x)  //求欧拉序，顺便为求lca做准备
{
    ord[++len]=x;
    first[x]=len;
    for(ll i=head[x]; i; i=e[i].next)
    {
        ll to=e[i].to;
        if(to==fa[x][0]) continue;
        depth[to]=depth[x]+1;
        fa[to][0]=x;
        for(ll j=1; (1<<j)<=depth[to]; ++j)
        {
            fa[to][j]=fa[fa[to][j-1]][j-1];
        }
        dfs(to);
    }
    ord[++len]=x;
    second[x]=len;
}
ll get_lca(ll u,ll v) //使用倍增lca
{
    if(depth[u] < depth[v])
        swap(u, v);
    for(ll i = 20; i + 1; --i)
        if(depth[u] - (1 << i) >= depth[v])
            u = fa[u][i];
    if(u == v)
        return u;
    for(ll i = 20; i + 1; --i)
        if(fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}
inline void add(ll pos)
{
    now += 1ll * typ[val[pos]] * arr[++cnt[val[pos]]];
}
inline void del(ll pos)
{
    now -= 1ll * typ[val[pos]] * arr[cnt[val[pos]]--];
}
inline void work(ll pos)
{
    vis[pos] ? del(pos) : add(pos);
    vis[pos] ^= 1;
}
void modify(ll x)
{
    if(vis[que[x].pos])  //如果vis数组值为1，就表示这个位置的值为答案做了贡献
    {                    //，所以如果这个位置改变就会影响答案
        work(que[x].pos);
        swap(val[que[x].pos], que[x].val);
        work(que[x].pos);
    }  //否则的话就不需要改变答案
    else swap(val[que[x].pos], que[x].val);
}
int main()
{
    //scanf("%d%d",&n,&m);
    ll Q;
    n=read();
    m=read();
    Q=read();
    for(ll i=1;i<=m;++i)
    {
        typ[i]=read();
    }
    for(ll i=1; i<=n; ++i)
    {
        //scanf("%d",&val[i]);
        arr[i]=read();
    }
    for(ll i=1; i<n; ++i)
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        add_edge(x,y);
    }
    for(ll i=1;i<=n;++i)
        val[i]=read();
    depth[1]=1;
    dfs(1);
    sizes=pow(len, 2.0 / 3.0);  //注意，这个分块才是最优
    new_size=ceil((double)len/sizes);
    for(ll i=1; i<=new_size; ++i)
    {
        for(ll j=(i-1)*sizes+1; j<=i*sizes; ++j)
        {
            belong[j]=i;
        }
    }
    //printf("*****\n");
    for(ll i=1; i<=Q; ++i)  //处理两种操作
    {
        ll opt,x,y,z;
        opt=read();
        x=read();
        y=read();
        //scanf("%lld%lld",&x,&y);
        if(opt)
        {
            z=get_lca(x,y);
            node[++nod_len].time=que_len;
            if(first[x]>first[y]) swap(x,y);
            if(x==z)
            {
                node[nod_len].l=first[x];
                node[nod_len].r=first[y];
            }
            else
            {
                node[nod_len].l=second[x];
                node[nod_len].r=first[y];
                node[nod_len].lca=z;
            }
            node[nod_len].id=nod_len;
        }
        else
        {
            que[++que_len].pos=x;
            que[que_len].val=y;
        }
    }
    //printf("**\n");
    sort(node+1,node+1+nod_len,cmp);
    ll l=1,r=0,t=0;
    for(ll i=1; i<=Q; ++i)
    {
        ll start = node[i].l, last = node[i].r, time = node[i].time, lca = node[i].lca;
        while(l < start) work(ord[l++]);
        while(l > start) work(ord[--l]);
        while(r < last) work(ord[++r]);
        while(r > last) work(ord[r--]);
        while(t < time) modify(++t);  //判断当前时间有没有遇到更新内容
        while(t > time) modify(t--);
        if(lca) work(lca);
        ans[node[i].id] = now;
        if(lca) work(lca);
    }
    for(ll i=1; i<=nod_len; ++i)
        printf("%lld\n",ans[i]);
    return 0;
}

 

上一篇：Elasticsearch7.X 入门学习第二课笔记----基本api操作和CRUD


下一篇：ACM模板