【线段树】BZOJ 5334 数学计算

题目内容

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

1 m：\(x=x×m\)，输出\(x\ mod\ M\)；

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

输入格式

一共有\(t\)组输入。

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

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

输出格式

对于每一个操作，输出一行，包含操作执行后的\(x\ mod\ M\)的值

数据范围

对于\(20\%\)的数据，\(1≤Q≤500\)；

对于\(100\%\)的数据，\(1≤Q≤105\),\(t≤5\),\(M≤109\)。

样例

1

10 1000000000

1 2

2 1

1 2

1 10

2 3

2 4

1 6

1 7

1 12

2 7

样例输出

2

1

2

20

10

1

6

42

504

84

思路

线段树+单点修改。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=1e5+10;

int Mod;

ll ans[maxn<<2];

void build(int x,int l,int r){

    ans[x]=1ll;

    if(l==r) return;

    int mid=l+r>>1;

    build(x<<1,l,mid);

    build(x<<1|1,mid+1,r);

}

void modify(int x,int l,int r,int p,int q){

    if(l==r){

        ans[x]=(ll)q%Mod;

        return;

    }

    int mid=l+r>>1;

    if(p<=mid)modify(x<<1,l,mid,p,q);

    else modify(x<<1|1,mid+1,r,p,q);

    ans[x]=ans[x<<1]*ans[x<<1|1]%Mod;

}

int main(){

    int T,q,p,x;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&q,&Mod);

        build(1,1,q);

        for(int i=1;i<=q;i++){

            scanf("%d%d",&p,&x);

            if(p==1)modify(1,1,q,i,x);

            else modify(1,1,q,x,1);

            printf("%lld\n",ans[1]);

        }

    }

    return 0;

}

巴特西