热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

CF633G

题目大意:给你一棵树,根节点为1有2种操作,第一种是给u节点所在的子树的所有节点的权值x第二种是询问,假设v是子树u中的节点

题目大意:

给你一棵树,根节点为1

有2种操作,第一种是给u节点所在的子树的所有节点的权值+x

第二种是询问,假设v是子树u中的节点,有多少种质数p满足av = p + m·k

做法:维护子树信息显然dfs序,考虑用线段树维护一个区间内有哪些值

每个区间用一个bitset维护

这里有一个小技巧&#xff0c;bitset都&#43;x然后%m&#xff0c;可以bt2[k]&#61;(bt2[k]<>(m-y));

然后求出区间的bitset&#xff0c;和质数的bitset&一下&#xff0c;求1的个数即可

代码&#xff1a;

#include
#define N 500005
using namespace std;bool vis[N];
int n,m,Q,x,y,opt,tim1,kk,tot,head[N],a[N],dfn[N],sz[N],pr[N];
bitset<1005>bt1,bt2[N],bt3;int ee[N],reall[N];
struct Tree{int nxt,to;}e[N];
inline void link(int x,int y){e[&#43;&#43;kk].nxt&#61;head[x];e[kk].to&#61;y;head[x]&#61;kk;}
inline void init(){for (int i&#61;2;i&#61;m) break;vis[i*pr[j]]&#61;true;if (i%pr[j]&#61;&#61;0) break;}}
}
void dfs(int u,int fa){sz[u]&#61;1;dfn[u]&#61;&#43;&#43;tim1;reall[tim1]&#61;a[u];for (int i&#61;head[u];i;i&#61;e[i].nxt){int v&#61;e[i].to;if (v&#61;&#61;fa) continue;dfs(v,u);sz[u]&#43;&#61;sz[v];}
}
void build(int k,int l,int r){if (l&#61;&#61;r){bt2[k][reall[l]]&#61;1;return;}int mid&#61;(l&#43;r)>>1;build(k*2,l,mid);build(k*2&#43;1,mid&#43;1,r);bt2[k]&#61;bt2[k*2]|bt2[k*2&#43;1];
}
void update(int k,int y){y%&#61;m;bt2[k]&#61;(bt2[k]<>(m-y));}
inline void pushdown(int k){if (!ee[k]) return;ee[k*2]&#61;(ee[k*2]&#43;ee[k])%m;ee[k*2&#43;1]&#61;(ee[k*2&#43;1]&#43;ee[k])%m;update(k*2,ee[k]);update(k*2&#43;1,ee[k]);ee[k]&#61;0;
}
void add(int k,int l,int r,int x,int y,int z){if (l!&#61;r) pushdown(k);if (x<&#61;l&&y>&#61;r){update(k,z);ee[k]&#61;(ee[k]&#43;z)%m;return;}int mid&#61;(l&#43;r)>>1;if (y<&#61;mid) add(k*2,l,mid,x,y,z);else if (x>mid) add(k*2&#43;1,mid&#43;1,r,x,y,z);else add(k*2,l,mid,x,mid,z),add(k*2&#43;1,mid&#43;1,r,mid&#43;1,y,z);bt2[k]&#61;bt2[k*2]|bt2[k*2&#43;1];
}
void query(int k,int l,int r,int x,int y){if (l!&#61;r) pushdown(k);if (x<&#61;l&&y>&#61;r){bt3&#61;bt3|bt2[k];return;}int mid&#61;(l&#43;r)>>1;if (y<&#61;mid) query(k*2,l,mid,x,y);else if (x>mid) query(k*2&#43;1,mid&#43;1,r,x,y);else query(k*2,l,mid,x,mid),query(k*2&#43;1,mid&#43;1,r,mid&#43;1,y);
}
int main(){scanf("%d%d",&n,&m);for (int i&#61;1;i<&#61;n;i&#43;&#43;) scanf("%d",&a[i]),a[i]%&#61;m;for (int i&#61;1;i}

  

转:https://www.cnblogs.com/ckr1225/p/9033262.html



推荐阅读
  • Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]
  • 火星商店问题:线段树分治与持久化Trie树的应用
    本题涉及编号为1至n的火星商店,每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品,以及查询某段时间内某些商店中所有商品(含永久商品)与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]
  • 本文探讨了如何在模运算下高效计算组合数C(n, m),并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元,从而实现除法取余的计算。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • golang常用库:配置文件解析库/管理工具viper使用
    golang常用库:配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库,是由大神SteveFrancia开发,他在google领导着golang的 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • 数据库内核开发入门 | 搭建研发环境的初步指南
    本课程将带你从零开始,逐步掌握数据库内核开发的基础知识和实践技能,重点介绍如何搭建OceanBase的开发环境。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • This document outlines the recommended naming conventions for HTML attributes in Fast Components, focusing on readability and consistency with existing standards. ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • ImmutableX Poised to Pioneer Web3 Gaming Revolution
    ImmutableX is set to spearhead the evolution of Web3 gaming, with its innovative technologies and strategic partnerships driving significant advancements in the industry. ... [详细]
  • 本教程涵盖OpenGL基础操作及直线光栅化技术,包括点的绘制、简单图形绘制、直线绘制以及DDA和中点画线算法。通过逐步实践,帮助读者掌握OpenGL的基本使用方法。 ... [详细]
author-avatar
老鼠也偷腥
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有