upc组队赛2 Master of GCD 【线段树区间更新 || 差分】
Master of GCD
题目描述
Hakase has n numbers in a line. At fi rst, they are all equal to 1. Besides, Hakase is interested in primes. She will choose a continuous subsequence [l, r] and a prime parameter x each time and for every l≤i≤r, she will change ai into ai*x. To simplify the problem, x will be 2 or 3. After m operations, Hakase wants to know what is the greatest common divisor of all the numbers.
输入
The first line contains an integer T (1≤T≤10) representing the number of test cases.
For each test case, the fi rst 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.
输出
For each test case, print an integer in one line, representing the greatest common divisor of the sequence. Due to the answer might be very large, print the answer modulo 998244353.
样例输入
2
5 3
1 3 2
3 5 2
1 5 3
6 3
1 2 2
5 6 2
1 6 2
样例输出
6
2
提示
For the first test case, after all operations, the numbers will be [6,6,12,6,6]. So the greatest common divisor is 6.
题解
只需要求出【1,n】中乘2 和 乘3的最少次数
比赛的时候写的线段树 结束了学弟说用差分可以很快解决,给跪了orz
差分代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define memset(x,y) memset(x,y,sizeof(x))
#define memcpy(x,y) memcpy(x,y,sizeof(y))
#define all(x) x.begin(),x.end()
#define readc(x) scanf("%c",&x)
#define read(x) scanf("%d",&x)
#define read2(x,y) scanf("%d%d",&x,&y)
#define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define print(x) printf("%d\n",x)
#define lowbit(x) x&-x
#define lson(x) x<<1
#define rson(x) x<<1|1
#define pb push_back
#define mp make_pair
typedef pair<int,int> P;
typedef long long LL;
typedef long long ll;
const double eps=1e-8;
const double PI = acos(1.0);
const int INF = 0x3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9+7;
const ll mod = 998244353;
const int MAXN = 1e6+7;
const int maxm = 1;
const int maxn = 100000+10;
int T;
int n,m;
int a,b,x;
int cnt2[maxn],cnt3[maxn];
int tot2[maxn],tot3[maxn];
int main(){
read(T);
while(T--){
memset(cnt2,0);
memset(cnt3,0);
memset(tot2,0);
memset(tot3,0);
read2(n,m) ;
while(m--){
read3(a,b,x);
if(x == 2) {
cnt2[a]++,cnt2[b+1]--;
}
else {
cnt3[a]++,cnt3[b+1]--;
}
}
int min2,min3;
min2 = min3 = inf;
for(int i = 1; i<= n ;i ++){
tot2[i] = tot2[i-1] + cnt2[i];
tot3[i] = tot3[i-1] + cnt3[i];
min2 = min(min2,tot2[i]);
min3 = min(min3,tot3[i]);
}
ll ans = 1;
for(int i = 0 ; i < min2 ;i ++){
ans = ans * 2 % mod;
}
for(int i = 0 ; i < min3 ;i ++){
ans = ans * 3 % mod;
}
cout << ans <<endl;
}
}
线段树代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define memset(x,y) memset(x,y,sizeof(x))
#define memcpy(x,y) memcpy(x,y,sizeof(y))
#define all(x) x.begin(),x.end()
#define readc(x) scanf("%c",&x)
#define read(x) scanf("%d",&x)
#define read2(x,y) scanf("%d%d",&x,&y)
#define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define print(x) printf("%d\n",x)
#define lowbit(x) x&-x
#define lson(x) x<<1
#define rson(x) x<<1|1
#define pb push_back
#define mp make_pair
typedef pair<int,int> P;
typedef long long LL;
typedef long long ll;
const double eps=1e-8;
const double PI = acos(1.0);
const int INF = 0x3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int MOD = 1e9+7;
const ll mod = 998244353;
const int MAXN = 1e6+7;
const int maxm = 1;
const int maxn = 100000+10;
int T;
int n,m;
struct node {
ll l, r;
int lazy2,lazy3;
ll t;
ll cnt2,cnt3;
}tree[maxn << 2];
int a,b,x;
void pushup(int k){
tree[k].cnt2 = min(tree[k<<1].cnt2,tree[k<<1|1].cnt2);
tree[k].cnt3 = min(tree[k<<1].cnt3,tree[k<<1|1].cnt3);
}
void pushdown(int k)
{
if(tree[k].lazy2)
{
tree[k<<1].cnt2 += tree[k].lazy2;
tree[k<<1|1].cnt2 += tree[k].lazy2;
tree[k<<1].lazy2 += tree[k].lazy2;
tree[k<<1|1].lazy2 += tree[k].lazy2;
tree[k].lazy2 = 0;
}
if(tree[k].lazy3)
{
tree[k<<1].cnt3 += tree[k].lazy3;
tree[k<<1|1].cnt3 += tree[k].lazy3;;
tree[k<<1].lazy3 += tree[k].lazy3;
tree[k<<1|1].lazy3 += tree[k].lazy3;
tree[k].lazy3 = 0;
}
}
void build(int l,int r,int k){
tree[k].l = l;
tree[k].r = r;
tree[k].lazy2 = 0;
tree[k].lazy3 = 0;
tree[k].cnt2 = 0;
tree[k].cnt3 = 0;
if(l == r){
// tree[k].t = 1 ;
return ;
}
int mid = (r + l) >> 1 ;
build(l, mid, k << 1);
build(mid + 1,r , k << 1|1);
pushup(k);
}
void updata(int a,int b,int k,int x){
if(tree[k].l == tree[k].r)
{
if(x == 2)
tree[k].cnt2 ++;
if(x == 3)
tree[k].cnt3 ++;
return ;
}
if(a <= tree[k].l && b >= tree[k].r )
{
if(x == 2){
tree[k].cnt2 ++;
tree[k].lazy2 ++;
}
if(x == 3){
tree[k].cnt3 ++;
tree[k].lazy3 ++;
}
return ;
}
pushdown(k);
int mid = (tree[k].l + tree[k].r) >> 1;
if(a <= mid){
updata(a,b,k<<1,x);
}
if(b > mid){
updata(a,b,k<<1|1,x);
}
pushup(k);
}
int main(){
read(T);
while(T--){
read2(n,m);
build(1,n,1);
while(m--){
read3(a,b,x);
updata(a,b,1,x);
}
ll ans = 1;
for(int i = 0 ; i < tree[1].cnt2 ;i ++){
ans = ans * 2 % mod;
}
for(int i = 0 ; i < tree[1].cnt3 ;i ++){
ans = ans * 3 % mod;
}
printf("%lld\n",ans % mod);
}
}
最新文章
- .NET应用架构设计—表模块模式与事务脚本模式的代码编写
- 连接列值 mysql CONCAT函数
- 数据库SQLite
- 鸟哥的linux私房菜学习记录之认识系统服务(daemons)
- SpringMVC(一)
- 每天进步一点点——Linux系统时间来处理
- IP分类地址——a,b,c 类是如何划分的
- 敏感字符串加密处理(PHP实现)
- linux通过history查看命令执行时间
- WKWebView和WebView与JS的交互方式
- JavaMail API 概述
- AI学习---特征工程【特征抽取、特征预处理、特征降维】
- unicode解码
- sleep,yield,join,notify,wait,notifyAll区别
- chrome flash插件地址
- Ubuntu14.04下hadoop-2.6.0单机配置和伪分布式配置
- 暴搜 - Codeforces Round #327 (Div. 2) E. Three States
- springmvc将处理后的数据通过get方法传给页面时,可能会出现乱码。下面对于get请求中文参数出现乱码提出解决办法。
- Django:学习笔记(9)——视图
- .NET的那些事儿(9)——C# 2.0 中用iTextSharp制作PDF(基础篇) .