UPC——西⽐拉先知系统(分块)

简介: UPC——西⽐拉先知系统(分块)

西⽐拉先知系统

时间限制: 2 Sec 内存限制: 128 MB

提交 状态


题目描述

西⽐拉先知系统是⼀个强⼤的⼼灵指数监测⽹絡,能以声像扫描主动监控市⺠的⼼智与精神状态。为了判定出更复杂的⼈类⼼理参数,西⽐拉系统纳⼊了不同于既存⼈类规范的超群⼈格──不会随意和他⼈产⽣共鸣,也不会感情⽤事,能以⾮⼈类的眼光来俯瞰并裁定⼈类。

被纳⼊的超群⼈格会相互影响,共同处理数据。他们之间具体的影响⽅式形如⼀张⽆向图,如果你对⼀个节点进⾏操作,和这个节点相邻的节点也会受到相同的影响。

操作有⼀种:使⼀个节点的权值加上。

同时你还希望询问⼀个节点的权值(每⼀个节点的初始权值为0)。


输入

第⼀⾏读⼊n,m,Q,表⽰节点个数和边数,以及操作和询问的总数。

接下来m⾏,每⾏两个数ui,vi表⽰ui,vi之间有连边。

接下来Q,每⾏先读⼊⼀个type

type=0表⽰⼀个询问,读⼊⼀个x,表⽰询问x节点的权值。

type=1表⽰⼀个操作,读⼊x,y,表⽰将x节点的权值加上y。(与x相邻的节点权值也要加上y)


输出

对于每⼀个询问输出⼀⾏,表⽰该节点的权值。


样例输入

4 4 4
1 2
1 3
1 4
2 3
1 1 1
0 2
1 3 3
0 2

样例输出

1
4

提示

n,m,Q≤3×105,y≤1000


题意:


给定一个无向图,两种操作,一是查询某节点的权值,二是将某节点和相邻节点的权值都加上y


思路:


好喜欢这个题可惜没思路。


学长思路 永远滴神!


之前在牛客做过一个树上修改的,但其实不大一样。


这个题就是将每个点的邻接点进行分块,记录一下每个点在他的邻接点里属于哪个块和每个点的邻接点能够被分成的块的右端点。


这样对于操作一,答案就是他本身被修改的权值和修改邻接点的权值时对他产生的贡献;对于操作二,首先要修改的就是本身的权值,对邻接点或块的权值进行修改。


代码:

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>PLL;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
#define I_int ll
#define x first
#define y second
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    //cout<<" ";
}
ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
const int inf=0x3f3f3f3f,mod=1e9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn=3e5+100,maxm=3e6+7;
const double PI = atan(1.0)*4;
vector<int>v[maxn];///存图
vector<int>g[maxn];///表示一个点对于他的邻接点来说属于哪块
vector<int>r[maxn];///一个块的右端点
ll w[maxn],add[maxn];///每个节点的权值,每个块的权值
int n,m,q;
int main(){
    n=read(),m=read(),q=read();
    int block=sqrt(m);
    for(int i=1;i<=m;i++){
        int a=read(),b=read();
        v[a].push_back(b);
        v[b].push_back(a);///存图
    }
    int cnt=1;
    for(int i=1;i<=n;i++){
        ///对每个点的邻接点进行分块(相当于按边数分)
        if(v[i].size()>=block){///这时候可以分块,小于就可以直接暴力了
            int tmp=0;
            for(int j=0;j<v[i].size();j++){///遍历每一个节点
                int u=v[i][j];
                g[u].push_back(cnt);
                tmp++;
                if(tmp%block==0){
                    ///到达某一块的右端点 存储
                    r[i].push_back(cnt++);
                }
            }
            if(tmp%block){
                ///剩余的元素不能形成一个长度为block的块,单独记录
                r[i].push_back(cnt++);
            }
        }
    }
    while(q--){
        int op=read();
        if(!op){
            ///查询某节点的权值操作
            int x=read();
            ll res=w[x];///本身的权值
            for(auto tt:g[x]) res+=add[tt];
            out(res);puts("");
        }
        else{
            ///修改操作
            int x=read(),y=read();
            w[x]+=y;///增加本身权值
            if(v[x].size()<block){
                ///直接暴力修改
                for(auto t:v[x]) w[t]+=y;
            }
            else{
                ///修改每一块
                for(auto t:r[x]) add[t]+=y;
            }
        }
    }
    return 0;
}

后记:

学长的写法是将块的个数从n+1开始,这样就可以跟单点的权值使用同一个数组,节约空间,属实被秀到了。而且之前做分块也仅限于对数组的操作,这次突然在图上操作,确实思维被限制了,没想到。

目录
相关文章
|
2月前
|
存储 前端开发 算法
太平洋大西洋水流问题如何解决?一文了解图在前端中的应用
该文章深入探讨了图数据结构的基本概念及其在前端领域的多种应用,包括图的不同表示方法(邻接矩阵与邻接表)和经典的图算法(如深度优先搜索与广度优先搜索),并通过具体实例讲解了如何使用JavaScript来解决图相关的编程问题,如太平洋大西洋水流问题。
太平洋大西洋水流问题如何解决?一文了解图在前端中的应用
|
存储 区块链 数据库
普瑞缇Protradex系统开发(案例详细)丨Protradex普瑞缇系统开发(源码方案)/玩法规则
 什么是DAPP?DAPP是Decentralized Application的缩写,中文叫分布式应用/去中心化应用。通常来说,不同的DAPP会采用不同的底层技术开发平台和共识机制,或者自行发布代币
|
人工智能
UPC——2020年春混合个人训练第二十四场(DEFG)
UPC——2020年春混合个人训练第二十四场(DEFG)
117 0
UPC——2020年春混合个人训练第二十四场(DEFG)
upc2021个人训练赛第22场A. 联通数(思维)
upc2021个人训练赛第22场A. 联通数(思维)
55 0
|
人工智能
upc2021个人训练赛第23场M: 紫罗兰(dsu)
upc2021个人训练赛第23场M: 紫罗兰(dsu)
95 0
|
分布式计算 数据安全/隐私保护
2021-07-21训练日记upc联通数(思维)|赛博朋克(唯一分解)
A. 联通数 题目描述 数学高手小G最近发现了一种新型的数! 他首先在草稿纸写下任意长度的数字串kkkkkkkkkkk…(1≤k≤9)并在其中间添加加号,且相邻两个加号之间至少含有两个数字k (默认数字串第一个数字前与最后一个数字后也有两个加号),然后对其进行求和得出一个新的数。像这样得出的数他将其定义为 “k联通数 ” 。 小G对于他的发现感到非常的自豪, 像数字854就能表示为77+777,因此854是7联通数。 小G现在非常好奇, 究竟有哪些数可以是k联通数呢?他想考验一下你。 询问T次,每次给定两个数n,k,判断 n是否为k联通数, 如果是,输出 YES,否则出 NO。
162 0
2021-07-21训练日记upc联通数(思维)|赛博朋克(唯一分解)
|
机器学习/深度学习
UPC组队训练-补题记录(上)
Game on a Tree 时间限制: 1 Sec 内存限制: 1024 MB 题目描述 Alice and Bob play a game on a tree. Initially, all nodes are white. Alice is the first to move. She chooses any node and put a chip on it. The node becomes black. After that players take turns.
135 0
UPC组队训练-补题记录(上)
|
网络架构
UPC组队训练-补题记录(下)
Eggfruit Cake 时间限制: 1 Sec 内存限制: 128 MB 题目描述 Today is Jaime’s birthday and, to celebrate, his friends ordered a cake decorated with eggfruits and persimmons. When the cake arrived, to their surprise, they noticed that the bakery didn’t use equal amounts of eggfruits and persimmons,
105 0