結果

問題 No.3507 RangeSum RangeUpdate RangeSqrt
コンテスト
ユーザー Ryan Shaw
提出日時 2026-04-17 23:20:40
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 180 ms / 2,000 ms
コード長 4,588 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,055 ms
コンパイル使用メモリ 270,488 KB
実行使用メモリ 23,040 KB
最終ジャッジ日時 2026-04-17 23:20:48
合計ジャッジ時間 6,989 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void initcatalan(long long int)':
main.cpp:85:59: warning: iteration 1000002 invokes undefined behavior [-Waggressive-loop-optimizations]
   85 |         for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
      |                                                   ~~~~~~~~^
main.cpp:85:24: note: within this loop
   85 |         for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
      |                       ~^~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <fstream> 
using namespace std;

#define int long long
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back

const int MOD = 998244353;//
const int FACTMAX = 2000005;//
const int CATALANMAX = 1000005;//

int fact[FACTMAX], invfact[FACTMAX], cat[CATALANMAX];

int expo(int a, int b){
	int res=1;
	a%=MOD;
	while (b){
		if (b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}

int inv(int num){
	return expo(num, MOD-2);
}

void initfact(){
	fact[0]=1;
	for (int i=1; i<FACTMAX; ++i)fact[i]=(fact[i-1]*i)%MOD;
	invfact[FACTMAX-1]=inv(fact[FACTMAX-1]);
	for (int i=FACTMAX-2; i>=0; --i)invfact[i]=(invfact[i+1]*(i+1))%MOD;
}
 
int ncr(int n, int r){
	if (n<r||r<0)return 0;
	return (((fact[n]*invfact[r])%MOD)*invfact[n-r])%MOD;
}

int gcd(int a, int b){
	while (b){
		int t=a%b;
		a=b;
		b=t;
	}
	return a;
}

int lcm(int a, int b){
	int temp=gcd(a, b);
	a/=temp;
	b/=temp;
	return a*b*temp;
}

void initcatalan(int k){
	cat[0]=1;
	for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
}

int isqrtll(int x){
	int r = sqrtl((long double)x);
	while ((r+1)*(r+1) <= x) ++r;
	while (r*r > x) --r;
	return r;
}

struct node{
	int s, e, m, val, mn, mx, lazyset, lazyadd;
	node *l, *r;
	void create(){
		if (l==nullptr && s!=e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void pull(){
		val = l->val + r->val;
		mn = min(l->mn, r->mn);
		mx = max(l->mx, r->mx);
	}
	void propagate(){
		if (lazyset!=-1){
			val = lazyset*(e-s+1);
			mn = mx = lazyset;
		}
		if (lazyadd){
			val += lazyadd*(e-s+1);
			mn += lazyadd;
			mx += lazyadd;
		}
		if (s!=e){
			create();
			if (lazyset!=-1){
				l->lazyset = lazyset;
				r->lazyset = lazyset;
				l->lazyadd = r->lazyadd = 0;
			}
			if (lazyadd){
				l->lazyadd += lazyadd;
				r->lazyadd += lazyadd;
			}
		}
		lazyset=-1;
		lazyadd=0;
	}
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val = mn = mx = lazyadd = 0;
		lazyset = -1;
		l = r = nullptr;
	}
	void build(vector<int> &a){
		if (s==e){
			val = mn = mx = a[s];
			return;
		}
		create();
		l->build(a);
		r->build(a);
		pull();
	}
	void upset(int left, int right, int v){
		propagate();
		if (s==left && e==right)lazyadd=0, lazyset=v;
		else{
			create();
			if (right<=m)l->upset(left, right, v);
			else if (left>m)r->upset(left, right, v);
			else l->upset(left, m, v), r->upset(m+1, right, v);
			r->propagate(), l->propagate();
			pull();
		}
	}
	void upadd(int left, int right, int v){
		propagate();
		if (s==left && e==right)lazyadd+=v;
		else{
			create();
			if (right<=m)l->upadd(left, right, v);
			else if (left>m)r->upadd(left, right, v);
			else l->upadd(left, m, v), r->upadd(m+1, right, v);
			r->propagate(), l->propagate();
			pull();
		}
	}
	void upsqrt(int left, int right){
		propagate();
		if (mx<=1)return;
		if (s==left && e==right){
			int smn = isqrtll(mn);
			int smx = isqrtll(mx);
			if (smn==smx){
				lazyset = smn;
				propagate();
				return;
			}
			int dmn = smn - mn;
			int dmx = smx - mx;
			if (dmn==dmx){
				lazyadd = dmn;
				propagate();
				return;
			}
			if (s==e){
				lazyset = smn;
				propagate();
				return;
			}
		}
		create();
		if (right<=m)l->upsqrt(left, right);
		else if (left>m)r->upsqrt(left, right);
		else l->upsqrt(left, m), r->upsqrt(m+1, right);
		r->propagate(), l->propagate();
		pull();
	}
	int query(int left, int right){
		propagate();
		if (s==left && e==right)return val;
		create();
		if (right<=m)return l->query(left, right);
		else if (left>m)return r->query(left, right);
		else return l->query(left, m)+r->query(m+1, right);
	}
}*st;

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	//cin>>t;
	while (t--){
		int n, q, t, l, r, x;
		cin>>n>>q;
		vector<int> a(n);
		for (int i=0; i<n; ++i)cin>>a[i];
		st = new node(0, n-1);
		st->build(a);
		while (q--){
			cin >> t;
			if (t==0){
				cin>>l>>r;
				if (l==r)cout<<"0\n";
				else cout<<st->query(l, r-1)<<"\n";
			}
			else if (t==1){
				cin>>l>>r>>x;
				if (l!=r)st->upset(l, r-1, x);
			}
			else{
				cin>>l>>r;
				if (l!=r)st->upsqrt(l, r-1);
			}
		}
	}
}
0