P3373 【模板】线段树 2

· · 题解

前置条件：线段树1 ， 一定的手推能力，小学数学

相比线段树1多出了乘的操作，只要在push下放中多进行一些操作便可...

好吧，详细一点

线段树进行乘法优先运算

因为不会加法优先

为神马进行乘法优先呢？因为小学数学中乘法的优先度比加法高

明显，若进行加法优先的话，很难维护乘和加两个操作.......

好吧，这里实在是解释不好，如果不明白还是看楼上大佬的吧

进行运算

很明显，每个区间在建立时乘的tag必须为1 不然进行运算时就一直是0了

进行下放操作时

tag加 = tag加 * tag父亲乘 + tag加

tag乘 = tag乘 * tag父亲乘

不明白的话自己手动模拟一下吧

计算时的公式也很容易能够推出

value = value tag乘 + tag加 该区间的范围

最后在计算时拼命模便好了

坑点

    long long

代码

指针真好写



#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 500010
#define int long long

using namespace std;

inline int read()
{
    int x=0,f=1;char c=getchar();
    while( c > '9' || c < '0' ){if( c == '-' )f = -1;c = getchar();}
    while( c <='9' && c >= '0' ){x = (x<<3) + (x<<1) + c - '0';c = getchar();}
    return x * f;
}

int a[ MAXN ] , n , m , p , cnt;

struct Node{
    int l , r , tag1 , tag2 , value;    //tag1为乘 tag2为加
    Node *left , *right;
}pool[ 2 * MAXN ];

void build( int l , int r , Node *co )
{
    co -> l = l;
    co -> r = r;
    co -> tag1 = 1;
    if( l == r )
    {
        co -> l = co -> r = l;
        co -> value = a[ l ] % p;
        co -> tag1 = 1;
        return;
    }
    co -> left = &pool[ ++ cnt ];
    co -> right = &pool[ ++ cnt ];
    int mid = ( l + r ) / 2;
    build( l , mid , co -> left );
    build( mid + 1 , r , co -> right );
    co -> value = ( co -> right -> value + co -> left -> value ) % p;
}

int get( Node *cur )
{
    return ( cur -> value * cur -> tag1 % p + cur -> tag2 * ( cur -> r - cur -> l + 1 ) % p ) % p;
}

void push( Node *cur )
{
    if( cur -> tag1 ==1 && cur -> tag2 == 0 ) return;
    cur -> value = get( cur );
    cur -> right -> tag1 = cur -> right -> tag1 * cur -> tag1 % p;
    cur -> right -> tag2 = ( cur -> right -> tag2 * cur -> tag1 % p + cur -> tag2 ) % p;
    cur -> left -> tag1 = cur -> left -> tag1 * cur -> tag1 % p;
    cur -> left -> tag2 = ( cur -> left -> tag2 * cur -> tag1 % p + cur -> tag2 ) % p;
    cur -> tag1 = 1;
    cur -> tag2 = 0;
}

int find( int l , int r , Node *cur )
{
    if(cur -> l == l && cur -> r == r )
    {
        return get( cur );
    }
    push( cur );
    int mid = ( cur -> l + cur -> r ) / 2;
    if( r <= mid ) return find( l , r , cur -> left );
    if( l > mid ) return find( l , r , cur -> right );
    return ( find( l , mid , cur -> left ) + find( mid + 1 , r , cur -> right ) ) % p;
}

void addP( int l , int r , int v , Node *cur )
{
    if( cur -> l == l && cur -> r == r )
    {
        cur -> tag2 = ( cur -> tag2 + v ) % p;
        return;
    }
    push ( cur );
    int mid = ( cur -> r + cur -> l ) / 2;
    if( r <= mid ) addP( l , r , v , cur -> left );
    else if( l > mid ) addP( l , r , v , cur -> right );
    else
    {
        addP( l , mid , v , cur -> left );
        addP( mid + 1 , r , v , cur -> right );
    }
    cur -> value = ( get( cur -> right ) + get( cur -> left ) ) % p;
}

void addT( int l , int r , int v , Node *cur )
{

    if( cur -> l == l && cur -> r == r )
    {
        cur -> tag1 = cur -> tag1 * v % p;
        cur -> tag2 = cur -> tag2 * v % p;
        return;
    }
    push ( cur );
    int mid = ( cur -> r + cur -> l ) / 2;
    if( r <= mid ) addT( l , r , v , cur -> left );
    else if( l > mid ) addT( l , r , v , cur -> right );
    else
    {
        addT( l , mid , v , cur -> left );
        addT( mid + 1 , r , v , cur -> right );
    }
    cur -> value = ( get( cur -> right ) + get( cur -> left ) ) % p;
}

signed main()
{
    n = read() , m = read() , p = read();
    for( int i = 1 ; i <= n ; i ++ )
    {
        a[ i ] = read();
    }
    build( 1 , n , pool );
    // Node* root=buildT(1,n);
    while( m -- )
    {
        int q = read() , l = read() , r = read();
        if( q == 1 )
        {
            int v = read();
            addT( l , r , v , pool );
        }
        if( q == 2 )
        {
            int v = read(); 
            addP( l , r , v , pool );
        }
        if( q == 3 )
        {
            cout << find( l , r , pool ) << endl;
        }
    }
    return 0;
}