【2018沈阳赛区网络预选赛J题】Ka Chang【分块+DFS序+线段树】
题意
给出一个有根树(根是1),有n个结点。初始的时候每个结点的值都是0.下面有q个操作,操作有两种,操作1.将深度为L的点的值全部增加X。操作2.查询以x为根的子树的结点值得和。
其中N,Q<=1e5
分析
一看这种没有办法直接用数据结构解决得问题就要考虑分块。这个题其实也不算是分块,应该是用了分块的思想进行分类而已。场上也一直在想分块但是可能是自己太菜了,赛后看了题解补的。
分块最重要的就是算时间复杂度啊。我们按照每一层的结点数进行分类。节点数>block的为第一类,节点数<=为第二类。
对于第二类,每次修改操作我们暴力修改每个结点的影响值,因为涉及线段树或者树状数组的操作,时间复杂度为O(q*block*logn)。而每次通过线段树查询都是logn的
对于第一类,当修改的时候直接记录这一层被增加了多少,O(1)修改,然后查询的时候只需要枚举第二类的每一层,然后以这个结点为根节点的子树中属于这一层的节点数*这一层增加的值。这里的时间复杂度是O(q*n/block)
我们需要预处理出每个结点的子树中属于第一类层的节点数各有多少。这里我用的办法就是直接暴力。枚举每个点,如果它所在的层是第一类,那么更新它所有的父节点。这里的时间复杂度很容易被认为是O(n^2)(所以我一直不打敢写)。但是我们仔细分析一下发现它远远小于O(n^2)。因为最多有n/block层,所以这里的时间复杂度是O(n*n/block)
先不考虑预处理,只看操作的时间复杂度是O(q*block*logn+q*n/block).根据均值不等式最小是O(q*2*sqrt(nlogn)),当且仅当block取sqrt(n/logn)。这时候预处理的时间复杂度是O(n*sqrt(n*logn))经过计算时可以承受的(因为只有单组数据)。
这种题目时间复杂度计算明白以后写起来还是很好写的
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <vector> using namespace std;
typedef long long LL;
const int maxn=+;
int head[maxn],to[maxn*],Next[*maxn],Fa[maxn];
int n,q,sz,block,maxd;
int order[maxn],R[maxn],num,belong[maxn],L[maxn],pos[maxn]; map<int,int>M[maxn];
LL addv[maxn],sumv[*maxn];
vector<int>deep[maxn];
void init(){
sz=-;
maxd=;
num=;
// for(int i=0;i<=n;i++)M[i].clear();
// for(int i=0;i<=n;i++)deep[i].clear();
memset(head,-,sizeof(head));
// memset(addv,0,sizeof(addv));
}
void add_edge(int a,int b){
++sz;
to[sz]=b;Next[sz]=head[a];head[a]=sz;
} void dfs(int u,int fa,int dep){
maxd=max(maxd,dep);
Fa[u]=fa;
num++;
order[num]=u;L[u]=num;belong[u]=dep;pos[u]=num;
deep[dep].push_back(u);
for(int i=head[u];i!=-;i=Next[i]){
int v=to[i];
if(v==fa)continue;
dfs(v,u,dep+);
}
R[u]=num;
}
int p,v;
void update(int o,int L,int R){
if(L==R){
sumv[o]+=v;
return ;
}
int M=L+(R-L)/;
if(p<=M)
update(*o,L,M);
if(p>M)
update(*o+,M+,R);
sumv[o]=sumv[*o]+sumv[*o+];
}
int ql,qr;
LL res;
void query(int o,int L,int R){
if(ql<=L&&qr>=R){
res+=sumv[o];
return ;
}
int M=L+(R-L)/;
if(ql<=M)
query(*o,L,M);
if(qr>M)
query(*o+,M+,R);
}
LL ask(int root){
LL res=;
map<int,int>::iterator it;
for(it=M[root].begin();it!=M[root].end();it++){
res+=(LL)it->second*addv[it->first];
}
return res;
}
int main(){
scanf("%d%d",&n,&q);
init();
int a,b,c;
for(int i=;i<n;i++){
scanf("%d%d",&a,&b);
add_edge(a,b);
}
dfs(,-,);
block=sqrt(n/log(n));
num=;
for(int i=;i<=n;i++){
if(deep[belong[i]].size()>block){
int u=i;
while(u!=-){
if(!M[u].count(belong[i]))
M[u][belong[i]]=;
else
M[u][belong[i]]++;
u=Fa[u];
}
}
}
for(int i=;i<=q;i++){
scanf("%d",&a);
if(a==){
scanf("%d%d",&b,&c);
if(deep[b].size()>block){
addv[b]+=c;
}else{
for(int j=;j<deep[b].size();j++){
int u=deep[b][j];
p=pos[u],v=c;
update(,,n);
}
}
}else{
scanf("%d",&b);
res=;
ql=L[b],qr=R[b];
query(,,n);
LL ans=res+ask(b);
printf("%lld\n",ans);
}
} return ;
}
最新文章
- MyBatis的resultMap
- svg学习(五)ellipse
- UVa 673 Parentheses Balance【栈】
- Math.random();函数 随机数
- shell复习笔记----用户管理
- 实现方法 C# button快捷键
- JS编码解码详解
- JTextPane 的 undo 、 redo
- 私人定制javascript中函数小知识点
- 3. MariaDB设置主从复制
- 【Qt编程】基于Qt的词典开发系列<;十四>;自动补全功能
- 四、Java多人博客系统-2.0版本
- MySQL 数据库应用程序编程
- python3 kmp 字符串匹配
- RabbitMQ 汇总
- Hyper-V 虚拟机连网
- Spark介绍及安装部署
- (转)搭建本地 8.8 W 乌云漏洞库
- sublime text 全局搜索快捷键
- CA证书的办理
热门文章
- jsTree 是一个基于Javascript,支持多浏览器的Tree view jQuery插件。
- Linux环境下安装Websphere8.5.5
- 笔记:NPM 无限需要依赖问题解决
- 15.Python实现识别登录验证码(入门)
- 2.Python输入pip命令出现Unknown or unsupported command &#39;install&#39;问题解决
- [转]C#在WinForm下使用HttpWebRequest上传文件并显示进度
- c# 数据库通用类DbUtility
- CentOS部署NetCore - 2. 安装NetCore SDK On CentOS
- NoClassDefFoundError: org/apache/juli/logging/LogFactory
- windows7下怎样安装whl文件(python)