专栏文章

题解：P11287 [COTS 2017] 影响 Utjecaj

EEityDawn
P11287题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir2pzw0
此快照首次捕获于
2025/12/04 14:47
3 个月前
此快照最后确认于
2025/12/04 14:47
3 个月前
查看原文

思路：

注：分析默认 nn，mm，qq 同阶。
假设从图中删去关键节点，那么图将被划分成若干个联通块。如果有关键点与联通块相连，那么这个联通块内的点都是可达的。
所以考虑将联通块打包，缩成一个点，断开关键节点之间的边。
那么一个点的影响力就是所有与之直接相连的点和自身的权值之和。
那么问题转化为了：
  1. 对点 xx 和直接相连的点加上一个值。
  2. 查询点 xx 和直接相连的点的权值和。
直接做是 O(n∑degi)O(n\sum deg_i)，degideg_i 是点 ii 的出度。
考虑根号分治。我们设立一个阈值 BB，初始时先将点 xx 和直接相连的点的权值和预处理出来。对于修改操作，若 degx≤Bdeg_x\le B，直接暴力修改，反之，我们对 xx 打上标记。询问时，我们再在权值和的基础加上与 xx 相连的且出度 >B>B 的点上的标记。修改操作是 O(B)O(B)，而对于询问，默认 ∑degi≤2×n\sum deg_i \le 2\times n，那么出度 >B> B 的点不超过 nB{n}\over B，询问复杂度为 O(nB)O({n\over B})。
BB 取 n\sqrt n 时复杂度最优，为 O(nn)O(n\sqrt n)。

code

CPP
#include<bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define mset(x,y) memset((x),(y),sizeof((x)))
#define mcpy(x,y) memcpy((x),(y),sizeof((y)))
#define FileIn(x) freopen(""#x".in","r",stdin)
#define FileOut(x) freopen(""#x".out","w",stdout)
#define debug(x) cerr<<""#x" = "<<(x)<<'\n'
#define Assert(x) if(!(x)) cerr<<"Failed: "#x" at line "<<__LINE__,exit(1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 Int;
const int N=2e5+10,B=400;
bool StM;
int c[N],a[N],n,m,k,q;
int in[N],Be[N];
ll b[N],sum[N],tag[N];
vector<int>G[N],E[N],H[N],Fa[N];
map<int,bool>Cenect[N];
map<pair<int,int>,bool>edge;
void dfs(int now)
{
    Be[now]=k,b[k]+=a[now];
    for(int to:E[now])
        if(!Be[to]) dfs(to);
    return;
}
void Main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1,x,y;i<=m;i++)
    {
        cin>>x>>y;
        if(x>y) swap(x,y);
        if(edge.count({x,y})) continue;
        edge[{x,y}]=1;
        G[x].push_back(y);
        G[y].push_back(x);
        if(c[x]|c[y]) continue;
        E[x].push_back(y);
        E[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(!Be[i]) ++k,dfs(i);
    for(int now=1;now<=n;now++)
    {
        if(c[now]){
            for(int to:G[now])
                if(Be[to]^Be[now]&&!c[to])
                {
                    if(Cenect[Be[now]].count(Be[to])) continue;
                    H[Be[now]].push_back(Be[to]),++in[Be[to]];
                    Cenect[Be[now]][Be[to]]=1;
                } 
        }
        else{
            for(int to:G[now])
                if(Be[to]^Be[now])
                {
                    if(Cenect[Be[now]].count(Be[to])) continue;
                    H[Be[now]].push_back(Be[to]),++in[Be[to]];
                    Cenect[Be[now]][Be[to]]=1;
                }
        }
    }
    for(int now=1;now<=k;now++)
    {
        sum[now]=b[now];
        for(int to:H[now]) sum[now]+=b[to];
        if(in[now]>B)
            for(int to:H[now]) Fa[to].push_back(now);
    }
    cin>>q;
    int op,x,y,now;
    while(q--)
    {
        cin>>op>>x;
        if(op==1){
            cin>>y;now=Be[x];
            int val=y-a[x];
            a[x]=y,b[now]+=val,sum[now]+=val;
            if(in[now]>B)
                tag[now]+=val;
            else for(int to:H[now]) sum[to]+=val;
        }
        else{
            ll delta=0;now=Be[x];
            for(int to:Fa[now])
                delta+=tag[to];
            cout<<sum[now]+delta<<'\n';
        }
    }
}
bool EdM;
int main()
{
    cerr<<fabs(&StM-&EdM)/1024.0/1024.0<<" MB\n";
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int StT=clock();
    int T=1;
    while(T--) Main();
    int EdT=clock();
    cerr<<1e3*(EdT-StT)/CLOCKS_PER_SEC<<" ms\n";
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...