P4681 [THUSC 2015] 平方运算 Solution
Description
给定序列 a = ( a 1 , a 2 , ⋯ , a n ) a=(a_1,a_2,\cdots,a_n) a=(a1,a2,⋯,an) 和常数 p p p ,有 m m m 个操作,分以下两种:
- modify ( l , r ) \operatorname{modify}(l,r) modify(l,r):对每个 i ∈ [ l , r ] i \in [l,r] i∈[l,r] 执行 a i ← a i 2 m o d p a_i \leftarrow a_i^2 \bmod p ai←ai2modp.
- query ( l , r ) \operatorname{query}(l,r) query(l,r):求 ∑ i = l r a i \sum\limits_{i=l}^r a_i i=l∑rai.
Limitations
1 ≤ n , m ≤ 1 0 5 1 \le n,m \le 10^5 1≤n,m≤105
0 ≤ a i < p \textcolor{red}{0} \le a_i < p 0≤ai<p
p ∈ { 233 , 2332 , 5 , 8192 , 23 , 45 , 37 , 4185 , 5850 , 2975 , 2542 , 2015 , 2003 , 2010 , 4593 , 4562 , 1034 , 5831 , 9905 , 9977 } p \in {\{233,2332,5,8192,23,45,37,4185,5850,2975,2542,2015,2003,2010,4593,4562,1034,5831,9905,9977\}} p∈{233,2332,5,8192,23,45,37,4185,5850,2975,2542,2015,2003,2010,4593,4562,1034,5831,9905,9977}
2 s , 250 MB 2\text{s},250\text{MB} 2s,250MB
Solution
modify \operatorname{modify} modify 操作不能直接标记,也不能直接暴力改.
但是模意义下的平方运算显然是有周期性的,打表发现,在 p p p 取给定数时,所有数的周期的 lcm \operatorname{lcm} lcm 不大于 60 60 60,并且每个数平方不超过 11 11 11 次就会进入循环节.
考虑在线段树上维护:
- c y c l e cycle cycle:这个区间内的数是否全部进入循环节.
- s u m i sum_i sumi:全部进入循环节的情况下,每个数平方 i i i 次后的和.
- n o w now now:当前区间的和在循环节的第几个位置.
- t a g tag tag:标记,表示儿子需要平方几次.
特别地,如果没有全部进入循环节,则用 s u m 0 sum_0 sum0 来记录和.
然后进入循环节的直接跳,没有的就暴力改(因为不超过 11 11 11 次).
注意当一个数进入循环节时,需要将 s u m i sum_i sumi 全部算出.
剩下就没什么了,一开始时把每个数平方的周期长度全算一遍即可.
Code
4.27 KB , 9.45 s , 193.55 MB (in total, C++ 20 with O2) 4.27\text{KB},9.45\text{s},193.55\text{MB}\;\texttt{(in total, C++ 20 with O2)} 4.27KB,9.45s,193.55MB(in total, C++ 20 with O2)
// Problem: P4681 [THUSC 2015] 平方运算
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4681
// Memory Limit: 250 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}struct Node {int l, r;bool cycle;int now, tag;array<i64, 60> sum;
};
inline int ls(int u) { return 2 * u + 1; }
inline int rs(int u) { return 2 * u + 2; }struct SegTree {vector<Node> tr;vector<int> P, vis;int M, mod;inline SegTree() {}inline SegTree(const vector<int>& a, int _mod):P(_mod), vis(_mod, -1), M(1), mod(_mod) {for (int i = 0; i < mod; i++) get_loop(i);for (int i = 0; i < mod; i++)if (P[i] != 0) M = lcm(M, P[i]);const int n = a.size();tr.resize(n << 2);build(0, 0, n - 1, a);}inline void get_loop(int x) {for (int i = 0, y = x; ; i++, y = y * y % mod) {if (vis[y] != -1) {P[y] = i - vis[y];break;}else vis[y] = i;}for (int y = x; vis[y] != -1; y = y * y % mod) vis[y] = -1;}inline void upd(int u) {if (P[tr[u].sum[0]] != 0) {for (int i = 1; i < M; i++) tr[u].sum[i] = tr[u].sum[i - 1] * tr[u].sum[i - 1] % mod;tr[u].now = 0;tr[u].cycle = 1;}else tr[u].now = tr[u].cycle = 0;}inline void apply(int u, int k) {tr[u].tag = (tr[u].tag + k) % M;tr[u].now = (tr[u].now + k) % M;}inline void pushup(int u) {tr[u].cycle = tr[ls(u)].cycle && tr[rs(u)].cycle;tr[u].now = 0;if (!tr[u].cycle)tr[u].sum[0] = tr[ls(u)].sum[tr[ls(u)].now] + tr[rs(u)].sum[tr[rs(u)].now];else {int nowL = tr[ls(u)].now, nowR = tr[rs(u)].now;for (int i = 0; i < M; i++) {tr[u].sum[i] = tr[ls(u)].sum[nowL] + tr[rs(u)].sum[nowR];nowL = (nowL + 1) % M;nowR = (nowR + 1) % M;}}}inline void pushdown(int u) {if (tr[u].tag) {apply(ls(u), tr[u].tag);apply(rs(u), tr[u].tag);tr[u].tag = 0;}}inline void build(int u, int l, int r, const vector<int>& a) {tr[u].l = l;tr[u].r = r;if (l == r) {tr[u].sum[0] = a[l];tr[u].tag = 0;return upd(u);}const int mid = (l + r) >> 1;build(ls(u), l, mid, a);build(rs(u), mid + 1, r, a);pushup(u);}inline void square(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r && tr[u].cycle) return apply(u, 1);if (tr[u].l == tr[u].r) {tr[u].sum[0] = tr[u].sum[0] * tr[u].sum[0] % mod;return upd(u);}const int mid = (tr[u].l + tr[u].r) >> 1;pushdown(u);if (l <= mid) square(ls(u), l, r);if (r > mid) square(rs(u), l, r);pushup(u);}inline i64 query(int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum[tr[u].now];const int mid = (tr[u].l + tr[u].r) >> 1;i64 res = 0;pushdown(u);if (l <= mid) res += query(ls(u), l, r);if (r > mid) res += query(rs(u), l, r);return res;}
};signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m, p;scanf("%d %d %d", &n, &m, &p);vector<int> a(n);for (int i = 0; i < n; i++) scanf("%d", &a[i]);SegTree seg(a, p);for (int i = 0, op, l, r; i < m; i++) {scanf("%d %d %d", &op, &l, &r);l--, r--;if (op == 1) seg.square(0, l, r);else printf("%lld\n", seg.query(0, l, r));}return 0;
}
相关文章:
P4681 [THUSC 2015] 平方运算 Solution
Description 给定序列 a ( a 1 , a 2 , ⋯ , a n ) a(a_1,a_2,\cdots,a_n) a(a1,a2,⋯,an) 和常数 p p p ,有 m m m 个操作,分以下两种: modify ( l , r ) \operatorname{modify}(l,r) modify(l,r):对每个 i ∈ [ …...
【apt源】RK3588 平台ubuntu20.04更换apt源
RK3588芯片使用的是aarch64架构,因此在Ubuntu 20.04上更换apt源时需要使用针对aarch64架构的源地址。以下是针对RK3588芯片在Ubuntu 20.04上更换apt源到清华源的正确步骤: 步骤一:打开终端 在Ubuntu 20.04中,按下Ctrl Alt T打…...
Angular 2 表单深度解析
Angular 2 表单深度解析 引言 Angular 2作为现代前端开发的框架之一,以其灵活性和强大的功能赢得了众多开发者的青睐。在Angular 2中,表单处理是其中一个重要且复杂的部分。本文将深入解析Angular 2的表单,从基础知识到高级应用,旨在帮助开发者更好地理解和运用Angular 2…...
PHP 7 新特性
PHP 7 新特性 引言 PHP 作为一种广泛使用的服务器端脚本语言,自1995年诞生以来,已经经历了多个版本的迭代。PHP 7 是 PHP 的发展历程中的一个重要里程碑,它带来了许多新特性和改进,旨在提高性能、增强安全性和简化开发过程。本文将详细介绍 PHP 7 的新特性,帮助开发者更…...
vim如何解决‘’文件非法关闭后,遗留交换文件‘’的问题
过程描述: 由于我修改文件时(一定得修改了文件,不做任何修改不会产生这个问题)的非法关闭,比如直接关闭虚拟机,或者直接断开远程工具的远程连接,产生了以下遗留交换文件的问题: 点击…...
【练习】树形dp
G. Group Homework time limit per test: 3 s memory limit per test: 512 MB input: standard input output: standard output No, we don’t want group homework. It’s the place where KaTeX parse error: Expected EOF, got & at position 7: 1 1 &̲lt; 1 …...
Mybatis是如何进行分页的?
大家好,我是锋哥。今天分享关于【Mybatis是如何进行分页的?】面试题。希望对大家有帮助; Mybatis是如何进行分页的? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 MyBatis 实现分页的方式有很多种,最常见…...
【新春特辑】2025年春节技术展望:蛇年里的科技创新与趋势预测
🔥【新春特辑】2025年春节技术展望:蛇年里的科技创新与趋势预测 📅 发布日期:2025年01月29日(大年初一) 在这个辞旧迎新的美好时刻,我们迎来了充满希望的2025年,也是十二生肖中的蛇…...
论文笔记(六十三)Understanding Diffusion Models: A Unified Perspective(五)
Understanding Diffusion Models: A Unified Perspective(五) 文章概括基于得分的生成模型(Score-based Generative Models) 文章概括 引用: article{luo2022understanding,title{Understanding diffusion models: A…...
C++并发:C++内存模型和原子操作
C11引入了新的线程感知内存模型。内存模型精确定义了基础构建单元应当如何被运转。 1 内存模型基础 内存模型牵涉两个方面:基本结构和并发。 基本结构关系到整个程序在内存中的布局。 1.1 对象和内存区域 C的数据包括: 内建基本类型:int&…...
JavaScript函数中this的指向
总结:谁调用我,我就指向谁(es6箭头函数不算) 一、ES6之前 每一个函数内部都有一个关键字是 this ,可以直接使用 重点: 函数内部的 this 只和函数的调用方式有关系,和函数的定义方式没有关系 …...
【java学习笔记】@Autowired注解 使用方法和作用 | 配合@Component注解使用 | IOC控制反转
原本在类中,要用什么对象,就直接new一个对象。这种原始的方式 是由应用本身去控制实例的。 用了Autowired注解后,就相当于把实例(对象)的控制权 交给外部容器来统一管理(降低耦合)。(…...
数论问题76一一容斥原理
容斥原理是一种计数方法,用于计算多个集合的并集中元素的个数,以避免重复计算。以下是其基本内容及相关公式: 两个集合的容斥原理 若有集合A和集合B,那么A与B的并集中元素的个数等于A集合元素个数加上B集合元素个数,再…...
python-leetcode-从中序与后序遍历序列构造二叉树
106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode) # Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right r…...
【Oracle篇】使用Hint对优化器的执行计划进行干预(含单表、多表、查询块、声明四大类Hint干预)
💫《博主介绍》:✨又是一天没白过,我是奈斯,从事IT领域✨ 💫《擅长领域》:✌️擅长阿里云AnalyticDB for MySQL(分布式数据仓库)、Oracle、MySQL、Linux、prometheus监控;并对SQLserver、NoSQL(…...
设置jmeter外观颜色
设置jmeter外观颜色 方法: 步骤一、点击顶部选项 ->外观,这里提供了不同的主题,可选自己喜欢的风格。 步骤二、选择后,弹框提示点击Yes。...
计算机网络 IP 网络层 2 (重置版)
IP的简介: IP 地址是互联网协议地址(Internet Protocol Address)的简称,是分配给连接到互联网的设备的唯一标识符,用于在网络中定位和通信。 IP编制的历史阶段: 1,分类的IP地址: …...
神经网络和深度学习
应用 类型 为什么近几年飞速发展 数据增长,算力增长,算法革新 逻辑回归 向量化 浅层神经网络(Shallow neural network) 单条训练数据前向传播计算表达式 batch训练数据前向传播计算表达式 反向传播计算表达式 参数随机初始化 不能全部设为0 原因是同一…...
MySQL 基础学习(3):排序查询和条件查询
MySQL 查询与条件操作:详解与技巧 在本文中,我们将探讨 MySQL 中的查询操作及其相关功能,包括别名、去重、排序查询和条件查询等,并总结一些最佳实践和注意事项。 一、使用别名(AS) 在查询中,…...
webAPI -DOM 相关知识点总结(非常细)
title: WebAPI语法 date: 2025-01-28 12:00:00 tags:- 前端 categories:- 前端WEB API 了解DOM的结构并掌握其基本的操作,体验 DOM 在开发中的作用 API简介 就是使用js来操作html和浏览器 什么是DOM? 就是一个文档对象模型,是用来呈现预计于任意htm…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建
【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
