本文共 2657 字，大约阅读时间需要 8 分钟。

线段树多lazy-tag（两个）

题意：有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式：

(1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。 解题思路： 结构体定义：

typdef long long ll;struct Node{    int l,r;    ll sum;    ll mul,add;}tree[4*MAXN];

用两个lazy-tag标记： mul , add ，其中mul初始化为1，add初始化为0

由于要进行的lazy-tag标记很多，于是我们对它们设定优先级别，很明显乘法的优先级高于加法，于是我们便可以这样处理，例如 对于某个区间我们如果先对它进行加x然后再乘y的操作就可以化为 ( [a,b] + x ) * y = [a,b] * y + x * y 对于某个区间我们如果先对它进行乘x然后加y的操作就是 ( [a,b] * x ) + y = [a,b] * x + y 所以 (1)当对某个区间进行乘v时

tree[node].mul = ( tree[node].mul * v ) % p;tree[node].add = ( tree[node].add * v ) % p;tree[node].sum = ( tree[node].sum * v ) % p;

(2)当对某个区间进行加v时

tree[node].add = ( tree[node].add + v ) % p;tree[node].sum = ( tree[node].sum + v * ( tree[node].r - tree[node].l + 1 ) ) % p;

(3)PushDown操作（先传递乘，再传递加）

void PushDown(int node){    if (tree[node].mul==1 && tree[node].add==0)        return;     tree[node*2].mul=(tree[node*2].mul*tree[node].mul)%p;     tree[node*2+1].mul=(tree[node*2+1].mul*tree[node].mul)%p;    tree[node*2].add=(tree[node*2].add*tree[node].mul+tree[node].add)%p;    tree[node*2+1].add=(tree[node*2+1].add*tree[node].mul+tree[node].add)%p;    tree[node*2].sum=(tree[node*2].sum*tree[node].mul+tree[node].add*(tree[node*2].r-tree[node*2].l+1))%p;    tree[node*2+1].sum=(tree[node*2+1].sum*tree[node].mul+tree[node].add*(tree[node*2+1].r-tree[node*2+1].l+1))%p;    tree[node].mul=1;    tree[node].add=0;}

参考代码：

#include 
   
    #include 
    
     using namespace std;typedef long long ll;const int MAXN = 100000+5;ll p;struct Node{    int l,r;    ll sum;    ll mul,add;}tree[4*MAXN];void build(int node,int l,int r){    tree[node].l=l,tree[node].r=r;    tree[node].mul=1,tree[node].add=0;    if (l==r){        scanf("%lld",&tree[node].sum);        tree[node].sum%=p;  //1        return;    }    int mid=(l+r)/2;    build(node*2,l,mid);    build(node*2+1,mid+1,r);    tree[node].sum=(tree[node*2].sum+tree[node*2+1].sum)%p;}void PushDown(int node){    if (tree[node].mul==1 && tree[node].add==0)        return;    tree[node*2].mul=(tree[node*2].mul*tree[node].mul)%p;    tree[node*2+1].mul=(tree[node*2+1].mul*tree[node].mul)%p;    tree[node*2].add=(tree[node*2].add*tree[node].mul+tree[node].add)%p;    tree[node*2+1].add=(tree[node*2+1].add*tree[node].mul+tree[node].add)%p;    tree[node*2].sum=(tree[node*2].sum*tree[node].mul+tree[node].add*(tree[node*2].r-tree[node*2].l+1))%p;    tree[node*2+1].sum=(tree[node*2+1].sum*tree[node].mul+tree[node].add*(tree[node*2+1].r-tree[node*2+1].l+1))%p;    tree[node].mul=1;    tree[node].add=0;}void Add(int node,int l,int r,ll v){    if (l>tree[node].r || r
     
      tree[node].r || r
      
       tree[node].r || r
      
     
    
   

转载地址：http://ibbqb.baihongyu.com/