[TJOI2018] 数学计算 - 线段树

Description

维护一个大数 \(x\)，初始为 \(1\)，有 \(q\) 次操作，每次要么给定一个数 \(m\)，将 \(x\) 变为 \(mx\)，要么给定一个操作编号 \(pos\)，将 \(x\) 变为 \(x/p\)，其中 \(p\) 是第 \(pos\) 次操作（保证一定为乘法操作）的 \(m\)，且这种除法对于每个乘法操作只会进行一次。在每次操作后输出 \(x \bmod mod\)

Solution

用线段树维护区间模乘积，对于第 \(i\) 次操作，如果是乘法操作，就将 \(a[i]\) 设置为 \(m\)；如果是除法操作，就将 \(a[pos]\) 设置为 \(1\)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1000005;

int n,mod,op,m,a[N];

void build(int p,int l,int r) {
    a[p]=1;
    if(l<r) {
        build(p*2,l,(l+r)/2);
        build(p*2+1,(l+r)/2+1,r);
    }
}

void modify(int p,int l,int r,int pos,int key) {
    if(l==r) {
        a[p]=key;
    }
    else {
        if(pos<=(l+r)/2) modify(p*2,l,(l+r)/2,pos,key);
        else modify(p*2+1,(l+r)/2+1,r,pos,key);
        a[p]=a[p*2]*a[p*2+1]%mod;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--) {
        cin>>n>>mod;
        build(1,1,n);
        for(int i=1;i<=n;i++) {
            cin>>op>>m;
            if(op==1) {
                modify(1,1,n,i,m);
            }
            else {
                modify(1,1,n,m,1);
            }
            cout<<a[1]<<endl;
        }
    }
}

[TJOI2018] 数学计算 - 线段树

原文：https://www.cnblogs.com/mollnn/p/12877071.html