You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
115 lines
2.3 KiB
C++
115 lines
2.3 KiB
C++
#include <cstdio>
|
|
#include <cstring>
|
|
#include <utility>
|
|
#include <algorithm>
|
|
using namespace std;
|
|
const int maxn = 200050;
|
|
|
|
long long qpow(long long a,long long b)
|
|
{
|
|
long long ans=1;
|
|
for(;b;b>>=1){
|
|
if(b&1)
|
|
ans=ans*a%998244353;
|
|
a=a*a%998244353;
|
|
}
|
|
return ans;
|
|
}
|
|
|
|
struct Tr
|
|
{
|
|
int left,right;
|
|
int _2,_3;
|
|
int add_2,add_3;
|
|
};
|
|
|
|
Tr Tree[maxn<<2];
|
|
|
|
void UP(int root)
|
|
{
|
|
int L = root<<1, R = (root<<1)+1;
|
|
Tree[root]._2 = min(Tree[L]._2, Tree[R]._2);
|
|
Tree[root]._3 = min(Tree[L]._3, Tree[R]._3);
|
|
}
|
|
|
|
void Down(int root)
|
|
{
|
|
int L = root<<1, R = (root<<1)+1;
|
|
|
|
if(Tree[root].add_2)
|
|
{
|
|
Tree[L]._2 += Tree[root].add_2;
|
|
Tree[R]._2 += Tree[root].add_2;
|
|
Tree[root].add_2 = 0;
|
|
}
|
|
|
|
if(Tree[root].add_3)
|
|
{
|
|
Tree[L]._3 += Tree[root].add_3;
|
|
Tree[R]._3 += Tree[root].add_3;
|
|
Tree[root].add_3 = 0;
|
|
}
|
|
}
|
|
|
|
void build(int L,int R,int root)
|
|
{
|
|
Tree[root].left = L;
|
|
Tree[root].right = R;
|
|
if(Tree[root].left == Tree[root].right)
|
|
{
|
|
Tree[root].add_2 = Tree[root].add_3 = Tree[root]._2 = Tree[root]._3 = 0;
|
|
return;
|
|
}
|
|
int mid = (L+R)>>1;
|
|
build(L,mid,root<<1);
|
|
build(mid + 1,R,(root<<1)+1);
|
|
UP(root);
|
|
}
|
|
|
|
void update(int L, int R, bool _2, int root)
|
|
{
|
|
if(L <= Tree[root].left && R >= Tree[root].right)
|
|
{
|
|
if(_2)
|
|
{
|
|
Tree[root]._2++;
|
|
Tree[root].add_2++;
|
|
}
|
|
else
|
|
{
|
|
Tree[root]._3++;
|
|
Tree[root].add_3++;
|
|
}
|
|
return;
|
|
}
|
|
Down(root);
|
|
int mid = (Tree[root].left + Tree[root].right)>>1;
|
|
if(L <= mid)update(L,R,_2,root<<1);
|
|
if(R > mid) update(L,R,_2,(root<<1)+1);
|
|
UP(root);
|
|
}
|
|
|
|
int main()
|
|
{
|
|
int t;
|
|
scanf("%d",&t);
|
|
while(t--)
|
|
{
|
|
memset(Tree,0,sizeof Tree);
|
|
int n,m,l,r,item;
|
|
scanf("%d %d",&n,&m);
|
|
build(1,n,1);
|
|
while(m--)
|
|
{
|
|
scanf("%d %d %d",&l,&r,&item);
|
|
update(l,r,item == 2, 1);
|
|
|
|
pair<int,int> p(Tree[1]._2,Tree[1]._3);
|
|
printf("%d %d\n",p.first,p.second);
|
|
}
|
|
|
|
pair<int,int> p(Tree[1]._2,Tree[1]._3);
|
|
printf("%lld\n",qpow(2,p.first)*qpow(3,p.second)%998244353);
|
|
}
|
|
}
|