提出 b2b60715-a17f-4bd7-b38f-6d4ddba5299a

コード

今日のH問のざっくりとした解説を載せておきます
・配列のある区間に同じ値を足す
・配列のある区間の最大値を求める
この2つの操作がしたいです
これは「遅延セグ木」というデータ構造を使えばできる事が知られています
遅延セグ木を自分で書くのは少しダルいんですが、AtsuoCoderにはAC Libraryという物が入っているので、それを使えば楽にこの問題を解けます
AC Libraryの遅延セグ木で区間加算&区間maxを行うには、この記事が参考になります
https://betrue12.hateblo.jp/entry/2020/09/23/005940#%E5%8C%BA%E9%96%93%E5%8A%A0%E7%AE%97%E5%8C%BA%E9%96%93%E6%9C%80%E5%A4%A7%E5%80%A4%E5%8F%96%E5%BE%97
```c++
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
const ll inf=1e18;
ll op(ll a,ll b){
	return max(a,b);
}
ll e(){
	return -inf;
}
ll mapping(ll f,ll x){
	return f+x;
}
ll composition(ll f,ll g){
	return f+g;
}
ll id(){
	return 0;
}
int main(){
	int n,h,d,l,r,x,a,b;
	cin>>n;
	lazy_segtree<ll,op,e,ll,mapping,composition,id>lseg(n);
	for(int i=0;i<n;i++){
		cin>>h;
		lseg.set(i,h);
	}
	cin>>d;
	for(int i=0;i<d;i++){
		cin>>l>>r>>x>>a>>b;
		l--,a--;
		lseg.apply(l,r,x);
		cout<<lseg.prod(a,b)<<endl;
	}
}
```
I問の解説
ぶっちゃけ検索力です、「CRT 競プロ」でググると色々情報が出てきます

```c++
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
const ll MAX=(1ll<<31)-1;
using P=pair<ll,ll>;
P op(P a,P b){
	P p=crt({a.first,b.first},{a.second,b.second});
	if(p.first>MAX||p.second==0){
		p.first=MAX+1;
		p.second=MAX+2;
	}
	if(p.second>MAX+2)
		p.second=MAX+2;
	return p;
}
P e(){
	return P(1,1);
}
int main(){
	int n,a,b,q,l,r;
	cin>>n;
	segtree<P,op,e>seg(n);
	for(int i=0;i<n;i++){
		cin>>a>>b;
		seg.set(i,P(a,b));
	}
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>l>>r;
		l--;
		P p=seg.prod(l,r);
		if(p.first==0)
		    p.first=p.second;
		if(p.first>MAX)
		    cout<<-1<<endl;
		else
		    cout<<p.first<<endl;
	}
}
```
結果

問題	点数	言語	結果	実行時間	メモリ
I. Segment CRT	0	C++ (gcc)	IE	0 ms	0 KiB