Super-palindrome
题面地址:http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf
这道题是差分数组的题目，线段树也可以写，但是代码太长没必要。
代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 typedef long long ll; 9 const int maxn=1e5+10; 10 const int inf=0x3f3f3f3f; 11 const int mod=998244353; 12 ll kuaisumi(ll a,ll b){ 13 ll ans=1; 14 while(b!=0){ 15 if(b%2==1) 16 ans=ans*a%mod; 17 a=a*a%mod; 18 b/=2; 19 } 20 return ans; 21 } 22 ll a[maxn],b[maxn],na[maxn],nb[maxn]; 23 int main(){ 24 int t; 25 ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 26 cin>>t; 27 while(t--){ 28 memset(a,0,sizeof(a)); 29 memset(b,0,sizeof(b)); 30 memset(na,0,sizeof(na)); 31 memset(nb,0,sizeof(nb)); 32 int n,m; 33 cin>>n>>m; 34 a[0]=0;b[0]=0; 35 for(int i=0;i<m;i++){ 36 int l,r,x; 37 cin>>l>>r>>x; 38 if(x==2){a[l-1]++,a[r]--;} 39 else{b[l-1]++,b[r]--;} 40 } 41 na[0]=a[0],nb[0]=b[0]; 42 ll mina=a[0],minb=b[0]; 43 for(int i=1;i<n;i++){ 44 na[i]=na[i-1]+a[i];mina=min(mina,na[i]); 45 nb[i]=nb[i-1]+b[i];minb=min(minb,nb[i]); 46 } 47 ll ans=(kuaisumi(2,mina)*kuaisumi(3,minb))%mod; 48 cout<<ans<<endl; 49 } 50 }