洛谷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;
}