洛谷P4588 [TJOI2018]数学计算 题解

题目链接：P4588 [TJOI2018]数学计算

题意：

cxy 现在有一个数 $x$，初始值为 $1$。cxy 有 $Q$ 次操作，操作有两种类型：

1 m：将 $x$ 变为 $x \times m$，并输出 $x \bmod M$ 。

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

输入格式：

一共有 $t$ 组输入。

对于每一组输入，第一行是两个数字 $Q,M$。

接下来 $Q$ 行，每一行为操作类型 $\mathtt{op}$，操作编号或所乘的数字 $m$（保证所有的输入都是合法的）。

输出格式：

对于每一个操作，输出一行，包含操作执行后的 $x \bmod M$ 的值。

数据范围：

对于 $100\%$ 的数据，$1 \le Q \le 10^5$，$t \le 5, M \le 10^9$，$0 < m \leq 10^9$。

直接模拟是不行的。因为如果你要记录乘积，中间模过以后就不好搞除法了

逆元？不行，因为 $M$ 没有保证是质数，所以可能不存在逆元。

如果记录每个数，那每次直接乘过去就是暴力了，显然不可行。

考虑优化暴力。众所周知 $x \times 1 = x$

因此我们还是可以维护这样的序列，对于每个除法操作，我们只要把对应位置的数改成 $1$ 就好了

那这就是一个单点修改+区间查询乘积，线段树维护（我感觉树状数组也可以）

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

#define ls(at) (at << 1)
#define rs(at) (at << 1 | 1)

int n,mod,ans[N * 4];
void push_up(int at)
{ ans[at] = ans[ls(at)] * ans[rs(at)] % mod; }
void build(int l,int r,int at)
{
    if(l == r) { return ans[at] = 1, void(0); }
    int mid = (l+r) >> 1;
    build(l,mid,ls(at)); build(mid+1,r,rs(at));
    push_up(at);
}
void modify(int x,int k,int l=1,int r=n,int at=1)
{
    if(l == r) { return ans[at] = k, void(0); }
    int mid = (l+r) >> 1;
    if(x <= mid) modify(x,k,l,mid,ls(at));
    else modify(x,k,mid+1,r,rs(at));
    push_up(at);
}
void solve()
{
    cin >> n >> mod; build(1,n,1);
    for(int i=1,op,p; i<=n; i++)
    {
        cin >> op >> p;
        if(op & 1) { modify(i,p); }
        else { modify(p,1); }
        cout << ans[1] << '\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}