P4588 [TJOI2018]数学计算

题意简述

小豆现在有一个数 \(x\)，初始值为 \(1\)。小豆有 \(Q\) 次操作，操作有两种类型：

1 m：将 \(x\) 变为 \(x \times m\)，并输出 \(x \bmod M\)

2 pos：将 \(x\) 变为 \(x\) 除以第 \(pos\) 次操作所乘的数（保证第 \(pos\) 次操作一定为类型 \(1\)，对于每一个类型 \(1\) 的操作至多会被除一次），并输出 \(x \bmod M\)

---

解题思路

第一眼看到题目，发现这全是对一个数的修改，心想”这不就是简单模拟嘛“，但是多模拟一会儿就会发现

如果前面来很多个 1 操作不就爆 long long 了？所以这种简单模拟是肯定不行的

手玩样例后发现，其实操作可以表示为这样的形式：

\(1*2/2*4*5/4\)

那我们不就可以把 \(x\) 分解一下，用线段树存每次 \(1\) 操作后的 \(m\) 了吗？

如果是 \(2\) 操作就把那个结点改为 \(1\) 就行了

---

\(Code\)

#include <bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
const int N=4e5+10;
struct node{
    int dat;
}tree[N];
int m,mod,tot;
void upd(int p,int l,int r,int x,int y,int k){
    if(l==r){
	tree[p].dat=k;
	return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) upd(ls,l,mid,x,y,k);
    if(y>mid) upd(rs,mid+1,r,x,y,k);
    tree[p].dat=(tree[ls].dat*tree[rs].dat)%mod;
}
void build(int p,int l,int r){
    if(l==r){tree[p].dat=1;return;}
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    tree[p].dat=(tree[ls].dat*tree[rs].dat)%mod;
}
signed main(){
    int T=read();
    while(T--){
	m=read();mod=read();
	build(1,1,m);
	for(int i=1;i<=m;++i){
	    int op,k;
	    op=read();k=read();
	    if(op==1){upd(1,1,m,i,i,k);cout<<tree[1].dat%mod<<endl;}
	    else{upd(1,1,m,k,k,1);cout<<tree[1].dat%mod<<endl;}
	}
    }
    return 0;
}

\(Experience\)

本来想着定义一个 \(tot\) ，在每次 \(1\) 操作后就新增加一个点

	for(int i=1;i<=m;++i){
	    int op=read();
	    ++tot;
	    if(op==1){int k=read();upd(1,1,tot,i,i,k);cout<<tree[1].dat%mod<<endl;}
	    else{int pos=read();upd(1,1,tot,pos,pos,1);cout<<tree[1].dat%mod<<endl;}
	}

像这样，但是交上去就全 WA 了，应为线段树的全部的区间应该是一开始就定好了的，一开始是 \(1\)~\(m\)

的区间，但是 upd\(1\)~\(m\) 后就发现没有这个区间，线段树就会乱套了