【题解】Luogu P4588 [TJOI2018]数学计算
2024-10-20 03:18:30
原题传送门
这题是线段树的模板题
显而易见,直接模拟是不好模拟的(取模后就不好再除了)
我们按照时间来建一颗线段树
线段树初始值都为1,用来维护乘积
第一种操作就在当前时间所对应的节点上把乘数改成m
第二种操作就是把第pos个节点的乘数该回1
每次询问的答案就是线段树根节点维护的数值(pushup时要取模)
#include <bits/stdc++.h>
#define N 100005
#define ll long long
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ll read()
{
register ll x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register int x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
int n;
ll mod;
struct SegmentTree{
ll mul[N<<3];
inline void init(register int x,register int l,register int r)
{
mul[x]=1;
if(l==r)
return;
int mid=l+r>>1;
init(x<<1,l,mid);
init(x<<1|1,mid+1,r);
}
inline void pushup(register int x)
{
mul[x]=mul[x<<1]*mul[x<<1|1]%mod;
}
inline void update(register int x,register int l,register int r,register int pos,register int v)
{
if(l==r)
{
mul[x]=v;
return;
}
int mid=l+r>>1;
if(pos<=mid)
update(x<<1,l,mid,pos,v);
else
update(x<<1|1,mid+1,r,pos,v);
pushup(x);
}
}tr;
int main()
{
int T=read();
while(T--)
{
n=read(),mod=read();
tr.init(1,1,n);
for(register int i=1;i<=n;++i)
{
int opt=read();
ll x=read();
if(opt==1)
tr.update(1,1,n,i,x);
else
tr.update(1,1,n,x,1);
write(tr.mul[1]),puts("");
}
}
return 0;
}
最新文章
- [C#] Socket 通讯,一个简单的聊天窗口小程序
- ASP.net的文件扩展名
- JavaScript学习笔记——BOM_window对象
- android一键分享功能不使用任何第三方sdk
- angularJS中ng-if的用法
- chrome调试js工具的使用
- unity项目实现“再按一次退出程序”提示功能
- iOS CAShapeLayer精讲
- H5 APP开发必读,20个你不知道的Html5新特征和窍门
- phpcms v9二次开发之数据模型类
- isArray
- Git使用汇总
- 笨方法学python--数字和数学计算
- 掌握sklearn系列——1 学会加载数据
- 使用npm安装依赖,尽量别使用cnpm,会漏掉很多依赖的
- Django中Form的基本使用
- Linux中使用export命令设置环境变量
- 玩转spring MVC(九)---Spring Data JPA
- Linux 文本去重 之 命令sort 与 uniq
- 多线程爬虫爬取详情页HTML
热门文章
- hdu 4486 Pen Counts
- 网站SEO优化问答精选【转载】
- HTML02单词
- yum命令查看某个命令是由那个包提供的
- Python------mysql数据库
- TypeError: object() takes no parameters
- 前端paging分页,前端设置每页多少条和当前页面的索引,传给后端,数据显示出来
- VB调用C# dll
- 建立请求号 request
- 【Assembly】NO.70.EBook.7.Assembly.1.001-【汇编语言 第3版 张爽】- 基础知识