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

http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf
解析线段树区间延迟更新或差分数组两个数统计2和3的最少的个数乘一下
差分数组https://blog.csdn.net/yao166164474/article/details/52675613
AC代码
  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<map>
  5 #include<algorithm>
  6 #include<cmath>
  7 #define ll long long
  8 #define PI acos(-1.0)
  9 const int inf = 0x3f3f3f3f,mod=998244353;
 10 using namespace std;
 11 struct node
 12 {
 13     ll l,r;
 14     ll add;
 15     ll sum;
 16 } tree1[600005],tree2[600005];
 17 void pushup(ll root,node tree[])
 18 {
 19     tree[root].sum=min(tree[root<<1].sum,tree[root<<1|1].sum);
 20 }
 21 void  buildtree(ll root,ll left,ll right,node tree[])
 22 {
 23     tree[root].l=left;
 24     tree[root].r=right;
 25     tree[root].add=0;//wa点 所有的延迟标记都要初始化
 26     if(left==right)//不能放到下面的if中
 27     {
 28         tree[root].sum=0;
 29         return ;
 30     }
 31     ll mid=(left+right)>>1;
 32     buildtree(root<<1,left,mid,tree);
 33     buildtree(root<<1|1,mid+1,right,tree);
 34     pushup(root,tree);
 35 }
 36 void pushdown(ll root,node tree[])
 37 {
 38     if(tree[root].add==0) return ;
 39     tree[root<<1].add+=tree[root].add;//wa点 这里是增加而不是赋值
 40     tree[root<<1|1].add+=tree[root].add;
 41     tree[root<<1].sum+=tree[root].add;
 42     tree[root<<1|1].sum+=tree[root].add;
 43     tree[root].add=0;
 44 }
 45 void updata(ll root,ll left,ll right,ll c,node tree[])
 46 {
 47     if(tree[root].l==left&&tree[root].r==right)
 48     {
 49         tree[root].add+=c;//wa点 这里是增加而不是赋值
 50         tree[root].sum+=c;
 51         return ;
 52     }
 53      pushdown(root,tree);
 54     ll mid=(tree[root].l+tree[root].r)>>1;
 55     if(right<=mid)
 56         updata(root<<1,left,right,c,tree);
 57     else
 58     {
 59         if(left>mid)
 60             updata(root<<1|1,left,right,c,tree);
 61         else
 62         {
 63             updata(root<<1,left,mid,c,tree);
 64             updata(root<<1|1,mid+1,right,c,tree);
 65         }
 66     }
 67     pushup(root,tree);
 68 }
 69 ll poww(ll n,ll m)
 70 {
 71     ll ans = 1;
 72     while(m > 0)
 73     {
 74         if(m & 1)ans = (ans * n) % mod;
 75         m = m >> 1;
 76         n = (n * n) % mod;
 77     }
 78     return ans%mod;
 79 }
 80 ll n,q;
 81 char what;
 82 ll l1,r1,ad;
 83 int main()
 84 {
 85     int t;
 86     cin>>t;
 87     while(t--)
 88     {
 89         scanf("%lld %lld",&n,&q);
 90         buildtree(1,1,n,tree1);
 91         buildtree(1,1,n,tree2);
 92         while(q--)
 93         {
 94             scanf("%lld %lld %lld",&l1,&r1,&ad);
 95             if(ad==2)
 96             {
 97                 updata(1,l1,r1,1,tree1);
 98             }
 99             else if(ad==3)
100             {
101                 updata(1,l1,r1,1,tree2);
102             }
103         }
104         cout<<poww(2,tree1[1].sum)*poww(3,tree2[1].sum)%mod<<endl;
105     }
106     return 0;
107 }