bzoj5334（线段树裸题）

Description
小豆现在有一个数x，初始值为1. 小豆有Q次操作，操作有两种类型:
1 m: x = x * m ，输出 x%mod;
2 pos: x = x / 第pos次操作所乘的数（保证第pos次操作一定为类型1，对于每一个类型1 的操作至多会被除一次），输出x%mod
Input
一共有t组输入（t ≤ 5）
对于每一组输入，第一行是两个数字Q, mod(Q ≤ 100000, mod ≤ 1000000000);
接下来Q行，每一行为操作类型op，操作编号或所乘的数字m（保证所有的输入都是合法的）.
1 ≤ Q ≤ 100000
Output
对于每一个操作，输出一行，包含操作执行后的x%mod的值
Sample Input
1
10 1000000000
1 2
2 1
1 2
1 10
2 3
2 4
1 6
1 7
1 12
2 7
Sample Output
2
1
2
20
10
1
6
42
504
84

裸的线段树题。
只要你发现这道题不是线性的做法，你会线段树那这道题就水水水水了。
暴力维护一下区间的乘积即可。

#include<bits/stdc++.h>
using namespace std; 
#define ll long long 
int Q , Mod ;
int t1 , tot;
ll tr[401000];
int read()
{
    int sum = 0;char c = getchar();bool flag = true;
    while( c < '0' || c > '9' ) {if(c == '-') flag = false;c = getchar();}
    while( c >= '0' && c <= '9' ) sum = sum * 10 + c - 48 , c = getchar();
    if(flag)  return sum;
     else return -sum;
} 
void make(int root,int l,int r,int pos,int v)
{
    if(l == r){
        tr[root] = v;
        return;
    }
    int mid = (l + r)>>1;
    pos <= mid ? make(root*2,l,mid,pos,v) : make(root*2+1,mid + 1,r,pos,v);
    tr[root] = tr[root*2] * tr[root * 2 + 1] % Mod;
    return;
}
void build(int root,int l,int r)
{
    tr[root] = 1;
    if(l == r) return;
    int mid = (l + r)>>1;
    build(root * 2,l,mid);
    build(root * 2 + 1,mid + 1,r);
    return;
} 
void work()
{
    Q = read();Mod = read();
    build(1,1,Q);
    for(int i = 1;i <= Q;++i)
    {
        int k = read() , x = read();
        if(k == 1)
            make(1,1,Q,i,x);
        if(k == 2)
            make(1,1,Q,x,1);
        printf("%lldn",tr[1]);
    }   
    return;
}
int main()
{
    int T = read();
    while(T--) 
        work();
    return 0;
}

最后

以上就是聪明康乃馨为你收集整理的bzoj5334（线段树裸题）的全部内容，希望文章能够帮你解决bzoj5334（线段树裸题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。