hdu5475(线段树单点修改，统计区间乘积)

题目意思：

给定a*b*c*d*e*f*....,可以在某一步去掉前面的一个因子，每次回答乘积。

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cmath>

#define LL long long

using namespace std;

LL Q,MOD;

//线段树

//区间每点增值，求区间和

const int maxN = ;

struct node

{

    int lt, rt;

    LL val;

}tree[*maxN];

//向上更新

void pushUp(int id)

{

    tree[id].val = (tree[id<<].val * tree[id<<|].val)%MOD;

}

//建立线段树

void build(int lt, int rt, int id)

{

    tree[id].lt = lt;

    tree[id].rt = rt;

    tree[id].val = ;//每段的初值，根据题目要求

    if (lt == rt)

    {

        tree[id].val=;

        return;

    }

    int mid = (lt+rt)>>;

    build(lt, mid, id<<);

    build(mid+, rt, id<<|);

    pushUp(id);

}

//增加区间内每个点固定的值

void add(int lt, int rt, int id, int pls)

{

    if (lt <= tree[id].lt && rt >= tree[id].rt)

    {

        if(pls!=-)

        {

          tree[id].val *= pls;

          tree[id].val %= MOD;

        }

        if(pls==-)

          tree[id].val =;

        return;

    }

    int mid = (tree[id].lt+tree[id].rt)>>;

    if (lt <= mid)

        add(lt, rt, id<<, pls);

    if (rt > mid)

        add(lt, rt, id<<|, pls);

    pushUp(id);

}

//查询某段区间内的和

LL query(int lt, int rt, int id)

{

    if (lt <= tree[id].lt && rt >= tree[id].rt)

        return tree[id].val;

    int mid = (tree[id].lt+tree[id].rt)>>;

    LL ans = ;

    if (lt <= mid)

        ans = (ans * query(lt, rt, id<<) ) %MOD;

    if (rt > mid)

        ans = (ans * query(lt, rt, id<<|) ) %MOD;

    return ans;

}

int main()

{

    //freopen("test.txt","r",stdin);

    int t;

    scanf("%d",&t);

    int Case=;

    while(t--)

    {

        scanf("%I64d%I64d",&Q,&MOD);

        build(,Q,);

        printf("Case #%d:\n",++Case);

        for(int i=;i<=Q;i++)

        {

            LL x,m;

            scanf("%I64d%I64d",&x,&m);

            if(x==)

              add(i,i,,m);

            else if(x==)

              add(m,m,,-);

            printf("%I64d\n",tree[].val);

        }

    }

    return ;

}