結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-06-26 22:11:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 306 ms / 2,000 ms |
コード長 | 5,605 bytes |
コンパイル時間 | 2,104 ms |
コンパイル使用メモリ | 135,412 KB |
最終ジャッジ日時 | 2025-01-11 11:35:29 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#line 1 "main.cpp"#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <cctype>#include <cstdint>#include <cstdlib>#include <cmath>#include <complex>#include <chrono>#include <deque>#include <functional>#include <iomanip>#include <iostream>#include <map>#include <memory>#include <numeric>#include <queue>#include <set>#include <stack>#include <string>#include <unordered_map>#include <vector>#include <random>#include <utility>#include <limits>#include <list>#include <type_traits>/* template start */#define rep(i, a, b) for (long long i = (a); (i) < (b); (i)++)#define all(i) i.begin(), i.end()#ifdef LOCAL#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)#else#define debug(...)#endifvoid debug_out(){std::cerr<<std::endl;}template<typename Head,typename... Tail>void debug_out(Head h,Tail... t){std::cerr<<" "<<h;if(sizeof...(t)>0)std::cout<<" :";debug_out(t...);}template <typename T1, typename T2>std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {return os << pa.first << " " << pa.second;}template <typename T>std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");return os;}template<typename T1,typename T2>inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}template<typename T1,typename T2>inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}template<typename Num>constexpr Num mypow(Num a, long long b) {if(b==0)return 1;if (a==0)return 0;Num x = 1;while (b > 0) {if(b & 1)x*=a;a*=a;b >>= 1;}return x;}/* template end */using ll = long long;#line 2 "/mnt/c/Users/Imperi/Documents/cp-library/lib/SegmentTree/LazySegmentTree.hpp"#line 5 "/mnt/c/Users/Imperi/Documents/cp-library/lib/SegmentTree/LazySegmentTree.hpp"//Lazy// type value_t// type lazy_t// static value_t id_val// static value_t id_lazy// static (value_t,value_t) -> value_t f// static (value_t,lazy_t) -> value_t g// static (lazy_t,lazy_t) -> lazy_t h// static (lazy_t,size_t) -> lazy_t p/* Lazy templatestruct Lazy{using value_t= ~~ ;using lazy_t= ~~ ;static constexpr value_t id_val= ~~ ;static constexpr lazy_t id_lazy= ~~ ;static value_t f(value_t a,value_t b){return ~~ ;}static value_t g(value_t a,lazy_t b){return ~~ ;}static lazy_t h(lazy_t a,lazy_t b){return ~~ ;}static lazy_t p(lazy_t a,std::size_t n){return ~~ ;}};*/template<typename Lazy>class LazySegmentTree{public:using value_t=typename Lazy::value_t;using lazy_t=typename Lazy::lazy_t;using size_t=std::size_t;private:size_t n,n0;std::vector<value_t> val;std::vector<lazy_t> lazy;value_t update(size_t a,size_t b,lazy_t laz,size_t l,size_t r,size_t k){if(lazy[k]!=Lazy::id_lazy){if(k<n0-1){lazy[2*k+1]=Lazy::h(lazy[2*k+1],lazy[k]);lazy[2*k+2]=Lazy::h(lazy[2*k+2],lazy[k]);}val[k]=Lazy::g(val[k],Lazy::p(lazy[k],r-l));lazy[k]=Lazy::id_lazy;}if(r<=a||b<=l)return val[k];if(a<=l&&r<=b){lazy[k]=Lazy::h(lazy[k],laz);return Lazy::g(val[k],Lazy::p(lazy[k],r-l));}return val[k]=Lazy::f(update(a,b,laz,l,l+(r-l)/2,2*k+1),update(a,b,laz,l+(r-l)/2,r,2*k+2));}value_t fold(size_t a,size_t b,size_t l,size_t r,size_t k){if(lazy[k]!=Lazy::id_lazy){if(k<n0-1){lazy[2*k+1]=Lazy::h(lazy[2*k+1],lazy[k]);lazy[2*k+2]=Lazy::h(lazy[2*k+2],lazy[k]);}val[k]=Lazy::g(val[k],Lazy::p(lazy[k],r-l));lazy[k]=Lazy::id_lazy;}if(r<=a||b<=l)return Lazy::id_val;if(a<=l&&r<=b)return val[k];return Lazy::f(fold(a,b,l,l+(r-l)/2,2*k+1),fold(a,b,l+(r-l)/2,r,2*k+2));}inline size_t beki(size_t n_){size_t ret=1;while(ret<n_)ret<<=1;return ret;}public:LazySegmentTree(size_t n_):n(n_),n0(beki(n)),val(2*n0-1,Lazy::id_val),lazy(2*n0-1,Lazy::id_lazy){}LazySegmentTree(std::vector<value_t> val_):n(val_.size()),n0(beki(n)),val(2*n0-1,Lazy::id_val),lazy(2*n0-1,Lazy::id_lazy){for(size_t i=0;i<n;i++)val[i+n0-1]=val_[i];for(long long i=n0-2;i>=0;i--)val[i]=Lazy::f(val[2*i+1],val[2*i+2]);}void update(size_t a,size_t b,lazy_t laz){update(a,b,laz,0,n0,0);}value_t fold(size_t a,size_t b){return fold(a,b,0,n0,0);}};#line 85 "main.cpp"struct Sum{ll two,one,size;};struct Lazy{using value_t= Sum;using lazy_t= ll ;static constexpr value_t id_val= {0,0,1} ;static constexpr lazy_t id_lazy= 0 ;static value_t f(value_t a,value_t b){return {a.two+b.two,a.one+b.one,a.size+b.size};}static value_t g(value_t a,lazy_t b){return {a.two+2*b*a.one+a.size*b*b,a.one+a.size*b,a.size};}static lazy_t h(lazy_t a,lazy_t b){return a+b ;}static lazy_t p(lazy_t a,std::size_t n){return a;}};int main() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);ll n;std::cin>>n;std::vector<Sum> dat(n);rep(i,0,n){ll a;std::cin>>a;dat[i]={a*a,a,1};}LazySegmentTree<Lazy> seg(dat);ll q;std::cin>>q;while(q--){ll mode;std::cin>>mode;if(mode==1){ll l,r,x;std::cin>>l>>r>>x;l--;seg.update(l,r,x);}else{ll l,r;std::cin>>l>>r;l--;std::cout<<seg.fold(l,r).two<<"\n";}}return 0;}