2017 CCPC 杭州 HDU6273J 区间修改(线段树&差分数组）

http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf

解析 线段树区间延迟更新 或 差分数组 两个数   统计2和3的最少的个数  乘一下

差分数组https://blog.csdn.net/yao166164474/article/details/52675613

AC代码

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<map>

 #include<algorithm>

 #include<cmath>

 #define ll long long

 #define PI acos(-1.0)

 const int inf = 0x3f3f3f3f,mod=;

 using namespace std;

 struct node

 {

     ll l,r;

     ll add;

     ll sum;

 } tree1[],tree2[];

 void pushup(ll root,node tree[])

 {

     tree[root].sum=min(tree[root<<].sum,tree[root<<|].sum);

 }

 void  buildtree(ll root,ll left,ll right,node tree[])

 {

     tree[root].l=left;

     tree[root].r=right;

     tree[root].add=;//wa点 所有的延迟标记都要初始化

     if(left==right)//不能放到下面的if中

     {

         tree[root].sum=;

         return ;

     }

     ll mid=(left+right)>>;

     buildtree(root<<,left,mid,tree);

     buildtree(root<<|,mid+,right,tree);

     pushup(root,tree);

 }

 void pushdown(ll root,node tree[])

 {

     if(tree[root].add==) return ;

     tree[root<<].add+=tree[root].add;//wa点 这里是增加而不是赋值

     tree[root<<|].add+=tree[root].add;

     tree[root<<].sum+=tree[root].add;

     tree[root<<|].sum+=tree[root].add;

     tree[root].add=;

 }

 void updata(ll root,ll left,ll right,ll c,node tree[])

 {

     if(tree[root].l==left&&tree[root].r==right)

     {

         tree[root].add+=c;//wa点 这里是增加而不是赋值

         tree[root].sum+=c;

         return ;

     }

      pushdown(root,tree);

     ll mid=(tree[root].l+tree[root].r)>>;

     if(right<=mid)

         updata(root<<,left,right,c,tree);

     else

     {

         if(left>mid)

             updata(root<<|,left,right,c,tree);

         else

         {

             updata(root<<,left,mid,c,tree);

             updata(root<<|,mid+,right,c,tree);

         }

     }

     pushup(root,tree);

 }

 ll poww(ll n,ll m)

 {

     ll ans = ;

     while(m > )

     {

         if(m & )ans = (ans * n) % mod;

         m = m >> ;

         n = (n * n) % mod;

     }

     return ans%mod;

 }

 ll n,q;

 char what;

 ll l1,r1,ad;

 int main()

 {

     int t;

     cin>>t;

     while(t--)

     {

         scanf("%lld %lld",&n,&q);

         buildtree(,,n,tree1);

         buildtree(,,n,tree2);

         while(q--)

         {

             scanf("%lld %lld %lld",&l1,&r1,&ad);

             if(ad==)

             {

                 updata(,l1,r1,,tree1);

             }

             else if(ad==)

             {

                 updata(,l1,r1,,tree2);

             }

         }

         cout<<poww(,tree1[].sum)*poww(,tree2[].sum)%mod<<endl;

     }

     return ;

 }