HDU 6273.Master of GCD-差分数组 (2017中国大学生程序设计竞赛-杭州站-重现赛（感谢浙江理工))

Super-palindrome

题面地址:http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf

这道题是差分数组的题目，线段树也可以写，但是代码太长没必要。

代码:

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<queue>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 const int inf=0x3f3f3f3f;

 const int mod=;

 ll kuaisumi(ll a,ll b){

     ll ans=;

     while(b!=){

         if(b%==)

             ans=ans*a%mod;

         a=a*a%mod;

         b/=;

     }

     return ans;

 }

 ll a[maxn],b[maxn],na[maxn],nb[maxn];

 int main(){

     int t;

     ios::sync_with_stdio(false);cin.tie();cout.tie();

     cin>>t;

     while(t--){

         memset(a,,sizeof(a));

         memset(b,,sizeof(b));

         memset(na,,sizeof(na));

         memset(nb,,sizeof(nb));

         int n,m;

         cin>>n>>m;

         a[]=;b[]=;

         for(int i=;i<m;i++){

             int l,r,x;

             cin>>l>>r>>x;

             if(x==){a[l-]++,a[r]--;}

             else{b[l-]++,b[r]--;}

         }

         na[]=a[],nb[]=b[];

         ll mina=a[],minb=b[];

         for(int i=;i<n;i++){

             na[i]=na[i-]+a[i];mina=min(mina,na[i]);

             nb[i]=nb[i-]+b[i];minb=min(minb,nb[i]);

         }

         ll ans=(kuaisumi(,mina)*kuaisumi(,minb))%mod;

         cout<<ans<<endl;

     }

 }