結果
問題 | No.1099 Range Square Sum |
ユーザー |
|
提出日時 | 2022-07-17 14:00:55 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 303 ms / 2,000 ms |
コード長 | 4,844 bytes |
コンパイル時間 | 5,376 ms |
コンパイル使用メモリ | 314,828 KB |
実行使用メモリ | 23,936 KB |
最終ジャッジ日時 | 2024-06-29 15:04:48 |
合計ジャッジ時間 | 10,649 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#if !__INCLUDE_LEVEL__#include __FILE__//デフォは区間加算、区間最小using F = long long;struct S{ll a2;ll ax;ll size;};/*struct F{ll tmp;};*/S op(S a, S b){ return {a.a2+b.a2,a.ax+b.ax,a.size+b.size};}S e(){ return {0,0,0}; }S mapping(F f, S x){ return {x.a2+2*x.ax*f+x.size*f*f,x.ax+f*x.size,x.size};}F composition(F f, F g){ return f+g; }F id(){ return 0; }//構築//lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);//メソッド//seg.set(i,x);A[i]=x//seg.get(i);A[i]を取得//seg.prod(l,r);op(A[l]~A[r-1])を取得//seg.all_prod();op(A[0]~A[N-1])を取得//l=seg.min_left<fmin>(i);0~iでにぶたん//r=seg.max_right<fmin>(i);i~Nでにぶたん//seg.apply(l,r,F f);fの値を参照にA[l]~A[r~1]を区間更新int main(){ll N;cin >> N;vl A(N);rep(i,N)cin >> A[i];vector<S> As(N);rep(i,N){As[i] = {A[i]*A[i],A[i],1};}lazy_segtree<S, op, e, F, mapping, composition, id> seg(As);ll Q;cin >> Q;rep(q,Q){int t,l,r;cin >> t >> l >> r;l-=1;if(t==1){ll x;cin >> x;seg.apply(l,r,x);}else if(t==2){S a = seg.prod(l,r);cout << a.a2 << endl;}}}#else#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;#define rep(i, n) for(int i = 0; i < n; i++)#define rrep(i, n) for(int i = n-1; i >= 0; i--)#define range(i, m, n) for(int i = m; i < n; i++)#define fore(i,a) for(auto &i:a)#define all(v) v.begin(), v.end()#define rall(v) v.rbegin(), v.rend()#define Sum(v) accumulate(all(v),ll(0))#define minv(v) *min_element(all(v))#define maxv(v) *max_element(all(v))typedef long long ll;typedef vector<ll> vl;typedef vector<vector<ll>> vvl;const ll INF = 1e16;const ll MOD1 = 1000000007;const ll MOD2 = 998244353;template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }ll SN(char s){return ll(s-'0');}ll SN(string s){return stoll(s);}int alpN(char s){return int(s-'a');}int AlpN(char s){return int(s-'A');}using Graph = vector<vector<ll>>;using GraphCost = vector<vector<pair<ll,ll>>>;using mint = modint;using mint1 = modint1000000007;using mint2 = modint998244353;using pll = pair<long long, long long>;template <class T>ostream &operator<<(ostream &o,const vector<T>&v){for(int i=0;i<(int)v.size();i++)o<<(i>0?" ":"")<<v[i];return o;}//vector空白区切り出力ostream& operator<<(ostream& os, const mint1& N) {return os << N.val();}//mint出力。デフォはmint1ostream& operator<<(ostream& os, const mint2& N) {return os << N.val();}template<class T> bool contain(const std::string& s, const T& v) {return s.find(v) != std::string::npos;}ll max(int x,ll y){return max((ll)x,y);}ll max(ll x,int y){return max(x,(ll)y);}ll min(int x,ll y){return min((ll)x,y);}ll min(ll x,int y){return min(x,(ll)y);}template <typename T>struct edge {int src, to;T cost;edge(int to, T cost) : src(-1), to(to), cost(cost) {}edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}edge& operator=(const int& x) {to = x;return *this;}operator int() const { return to; }};template <typename T>using Edges = vector<edge<T> >;template <typename T>using WeightedGraph = vector<Edges<T> >;using UnWeightedGraph = vector<vector<int> >;template <typename T>using Matrix = vector<vector<T> >;//unorderd_mapの拡張…https://qiita.com/hamamu/items/4d081751b69aa3bb3557template<class T> size_t HashCombine(const size_t seed,const T &v){return seed^(std::hash<T>()(v)+0x9e3779b9+(seed<<6)+(seed>>2));}/* pair用 */template<class T,class S> struct std::hash<std::pair<T,S>>{size_t operator()(const std::pair<T,S> &keyval) const noexcept {return HashCombine(std::hash<T>()(keyval.first), keyval.second);}};/* vector用 */template<class T> struct std::hash<std::vector<T>>{size_t operator()(const std::vector<T> &keyval) const noexcept {size_t s=0;for (auto&& v: keyval) s=HashCombine(s,v);return s;}};/* tuple用 */template<int N> struct HashTupleCore{template<class Tuple> size_t operator()(const Tuple &keyval) const noexcept{size_t s=HashTupleCore<N-1>()(keyval);return HashCombine(s,std::get<N-1>(keyval));}};template <> struct HashTupleCore<0>{template<class Tuple> size_t operator()(const Tuple &keyval) const noexcept{ return 0; }};template<class... Args> struct std::hash<std::tuple<Args...>>{size_t operator()(const tuple<Args...> &keyval) const noexcept {return HashTupleCore<tuple_size<tuple<Args...>>::value>()(keyval);}};#endif