Master of GCD HDU - 6273 （区间更新，线段树）

Hakase has n numbers in a line. At first, they are all equal to 1. Besides, Hakase is interested inprimes. She will choose a continuous subsequence [l, r] and a prime parameter x each time and forevery l ≤ i ≤ r, she will change aiinto ai ∗ x. To simplify the problem, x will be 2 or 3. After moperations, Hakase wants to know what is the greatest common divisor of all the numbers.InputThe first line contains an integer T (1 ≤ T ≤ 10) representing the number of test cases.For each test case, the first line contains two integers n (1 ≤ n ≤ 100000) and m (1 ≤ m ≤ 100000),where n refers to the length of the whole sequence and m means there are m operations.The following m lines, each line contains three integers li (1 ≤ li ≤ n), ri (1 ≤ ri ≤ n), xi (xi ∈ {2, 3}),which are referred above.OutputFor each test case, print an integer in one line, representing the greatest common divisor of thesequence. Due to the answer might be very large, print the answer modulo 998244353.

题意：输入t，为有t组数据，每组数据先输入 n，m表示有n个点，m个操作，下面有m行，每行有三个数，前两个为一个区间，把这个区间中的 每个数都乘以最后一个数，最后一个数只能是 2,3；求，最后这个n个数的最大公倍数，刚开始这n个数都是1

思路：由于数据问题，所以要用到线段树，求n个数的最大公倍数，就是看看有几个2和几个3 全部在 n个数中；

一定要记住：当这个区间有延迟标记时，同时这个区间中的值也被更新了，同时性；只剩下向下传延迟标记； 

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

#define Max 100010
#define mod 998244353
struct node
{
	int x;    //
	int y;
	int nnode2;	
	int nnode3;
}stu[Max*4];
int n,m;


void build(int root,int star,int end)
{
	stu[root].nnode2 = 0;
	stu[root].nnode3 = 0;
	stu[root].x = 0;
	stu[root].y = 0;
	if(star==end)
		return ;
	int mid = (star+end)/2;
	build(2*root,star,mid);
	build(2*root+1,mid+1,end);
}

void updet(int root,int star,int end,int l,int r,int val)
{
	
	if(l>end||r<star)
		return;
	if(l<=star&&end<=r)
	{
		if(val==2)
		{
			//printf("root==%d\n",root);
			stu[root].nnode2++;     // 延迟标记，一定要记住这个区间有延迟标记时，同时这个区间的值也被更新过了 
			stu[root].x++;
		}
		else
		{
			stu[root].y++;
			stu[root].nnode3++;
		} 
		return ;
	}
	
	if(stu[root].nnode2)
	{
		stu[root*2].nnode2 += stu[root].nnode2;
		stu[root*2+1].nnode2 += stu[root].nnode2;
		stu[root*2].x += stu[root].nnode2;
		stu[root*2+1].x +=stu[root].nnode2;
		stu[root].nnode2 = 0;		
	}
	if(stu[root].nnode3)
	{
		stu[root*2].nnode3 += stu[root].nnode3;
		stu[root*2+1].nnode3 += stu[root].nnode3;
		stu[root*2].y += stu[root].nnode3;
		stu[root*2+1].y +=stu[root].nnode3;
		stu[root].nnode3 = 0;
	}
	int mid = (star+end)/2;
	if(l<=mid) updet(root*2,star,mid,l,r,val);
	if(r>mid) updet(root*2+1,mid+1,end,l,r,val);
	
	stu[root].x = min(stu[root*2].x,stu[root*2+1].x);
	stu[root].y = min(stu[root*2].y,stu[root*2+1].y);
}
int main()
{
	int i,j,t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		build(1,1,n);
		//printf("n==%d\n",n);
		int x,y,val;
		for(i = 0;i<m;i++)
		{
			scanf("%d%d%d",&x,&y,&val);
			updet(1,1,n,x,y,val);			
		}
		long long sum = 1;
		for(i = 0;i<stu[1].x;i++)
		{
			sum= (sum*2)%mod;
		}
		for(i = 0;i<stu[1].y;i++)
		{
			sum = sum*3%mod;
		}
		printf("%lld\n",sum);
	}
	return 0;
}