// https://github.com/yuki-4869/Algorithm/blob/main/template.cpp #include #include using namespace std; using namespace atcoder; using ll=long long; using LL=__int128; using mint=modint998244353; using ld = long double; using pll=pair; using tu=tuple; using tu4 = tuple;using vl=vector; using vb=vector; using vvb=vector; using vvl=vector; using vs=vector; using vld=vector; using vc=vector; using vmi=vector; using vp = vector; using vt = vector;using graph = vvl; using Graph = vector; template auto vec2(ll n,ll m,T x=T()){return vector(n,vector(m,x));} template auto vec3(ll n,ll m,ll l,T x=T()){return vector(n,vector(m,vector(l,x)));} template auto vec4(ll a,ll b,ll c,ll d,T x=T()){return vector(a,vector(b,vector(c,vector(d,x))));} template using rpq=priority_queue,greater>; // 小さい順priority_queue using inverse_priority_queue=rpq; const ll Inf=2147483647LL, Inf9=1000000000LL, inf=9223372036854775807LL, inf18=1000000000000000000LL, mod=998244353LL; #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define Re(n) for(ll i = 0; i<(ll)(n);i++) #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--) #define rep1(i,n) for(ll i=1;i<=(ll)(n);i++) #define rep3(i,s,t) for(ll i=(ll)(s);i<(ll)(t);i++) #define pb push_back #define p(s) cout<<(s)<<'\n' #define p2(s,t) cout<<(s)<<" "<<(t)<<'\n' #define p3(s,t,u) cout<<(s)<<" "<<(t)<<" "<<(u)<<'\n' #define p4(s,t,u,v) cout<<(s)<<" "<<(t)<<" "<<(u)<<" "<<(v)<<'\n' #define pe(s) cout<<(s)<std::ostream&{auto flags=std::cout.flags();auto precision=std::cout.precision();std::cout<(values)),...);std::cout<<'\n';std::cout.flags(flags);std::cout.precision(precision);return std::cout;}(__VA_ARGS__)) #define pld2(s,t) pld((s),(t)) #define pld3(s,t,u) pld((s),(t),(u)) #define pld4(s,t,u,v) pld((s),(t),(u),(v)) #define pe2(s,t) cout<<(s)<<" "<<(t)< inline ll sz(const T& x){return (ll)x.size();} // サイズ取得 ostream& operator<<(ostream& os,const mint& x){return os<>(istream& is,mint& x){ll v; is>>v; x=mint(v); return is;} // mint入力 template inline bool chmin(T& a,const T& b){if(a>b){a=b; return true;} return false;} // 最小値更新 template inline bool chmax(T& a,const T& b){if(a ll LB(const vector& v,const U& a){return lower_bound(all(v),a)-v.begin();} // lower_boundのindex template ll UB(const vector& v,const U& a){return upper_bound(all(v),a)-v.begin();} // upper_boundのindex template T vec_min(const vector& v){do { if (!(!v.empty())) std::abort(); } while (false); return *min_element(all(v));} // vectorの最小値 template T vec_max(const vector& v){do { if (!(!v.empty())) std::abort(); } while (false); return *max_element(all(v));} // vectorの最大値 template T vec_sum(const vector& v){T res=T(0); for(const auto& x:v) res+=x; return res;} // vectorの総和 template vector cin_vl(ll n){vector ret(n); rep(i,n) cin>>ret[i]; return ret;} // vector入力、型省略時ll template vector> cin_vvl(ll h,ll w){vector> ret(h,vector(w)); rep(i,h) rep(j,w) cin>>ret[i][j]; return ret;} // h*w入力、型省略時ll template pair,vector> cin_xy(ll n){vector x(n),y(n); rep(i,n) cin>>x[i]>>y[i]; return {x,y};} // x,y入力、型省略時ll template tuple,vector,vector> cin_xyz(ll n){vector x(n),y(n),z(n); rep(i,n) cin>>x[i]>>y[i]>>z[i]; return {x,y,z};} // x,y,z入力、型省略時ll template vector> Cin_vl(ll n,ll k){vector> ret(k,vector(n)); rep(i,n) rep(j,k) cin>>ret[j][i]; return ret;} // n行k列入力を列ごと保持、型省略時ll template vector> cin_pairs(ll n){vector> ret(n); rep(i,n) cin>>ret[i].first>>ret[i].second; return ret;} // pair列入力、型省略時ll template vector> cin_tuples(ll n){vector> ret(n); rep(i,n){T a,b,c; cin>>a>>b>>c; ret[i]={a,b,c};} return ret;} // 3要素tuple列入力、型省略時ll template void cout_vl(const vector& a,char sep=' ',char end='\n'){rep(i,sz(a)){if(i) cout< void cout_ver(const vector& a){for(const auto& value:a) cout< void Cout_vl(const vector& a,const vector& b){rep(i,sz(a)) cout< void cout_vvl(const vector>& a){for(const auto& e:a) cout_vl(e);} // 2次元vector出力 template void Swap(vector>& v,ll& h,ll& w){vector> ret(w,vector(h));rep(i,h) rep(j,w) ret[j][i]=v[i][j];v.swap(ret);swap(h,w);} // h*w行列をw*h行列に変換 hとwを自動でswap ll ceil_div(ll a,ll b){do { if (!(b!=0)) std::abort(); } while (false); if(b<0) a=-a,b=-b; if(a>=0) return (a+b-1)/b; return -((-a)/b);} // 切り上げ除算 ll floor_div(ll a,ll b){do { if (!(b!=0)) std::abort(); } while (false); if(b<0) a=-a,b=-b; if(a>=0) return a/b; return -((-a+b-1)/b);} // 切り下げ除算 ll isqrt(ll n){ll x=sqrtl(n); while((LL)(x+1)*(x+1)<=n) x++; while((LL)x*x>n) x--; return x;} // floor(sqrt(n)) template vector sort_unique_vec(vector v){sort(all(v)); v.erase(unique(all(v)),v.end()); return v;} // sortして重複削除した新vector template vector compress(const vector& v){auto xs=sort_unique_vec(v); vector ret; for(auto& x:v) ret.pb(LB(xs,x)); return ret;} // 座標圧縮後のindex列 template vector prefix_sum(const vector& v){vector s(sz(v)+1,0); rep(i,sz(v)) s[i+1]=s[i]+v[i]; return s;} // 1次元累積和 template vector> prefix_sum2(const vector>& a){int h=sz(a),w=sz(a[0]); vector> s(h+1,vector(w+1,0)); rep(i,h)rep(j,w)s[i+1][j+1]=s[i+1][j]+s[i][j+1]-s[i][j]+a[i][j]; return s;} // 2次元累積和 template T range_sum(const vector& s,ll l,ll r){return s[r]-s[l];} // 累積和から[l,r)の和 template vector> run_length(const vector& v){vector> ret; for(auto& x:v){if(ret.empty()||ret.back().first!=x) ret.pb({x,1}); else ret.back().second++;} return ret;} // ランレングス圧縮 vector> run_length(const string& s){vector> ret; for(char c:s){if(ret.empty()||ret.back().first!=c) ret.pb({c,1}); else ret.back().second++;} return ret;} // 文字列ランレングス圧縮 template ll argmin(const vector& v){do { if (!(!v.empty())) std::abort(); } while (false); return min_element(all(v))-v.begin();} // 最小値のindex template ll argmax(const vector& v){do { if (!(!v.empty())) std::abort(); } while (false); return max_element(all(v))-v.begin();} // 最大値のindex template bool in_vec(const vector& v,const T& x){return binary_search(all(v),x);} // sort済vectorに存在するか bool even(ll x){return x%2==0;} bool odd(ll x){return x%2!=0;} ll grid_id(ll x,ll y,ll w){return x*w+y;} // 座標からGridのID pll grid_xy(ll id,ll w){return {id/w,id%w};} // GridのIDから座標 ll gcd(ll a,ll b){if(b==0) return abs(a); return gcd(b,a%b);} // 最大公約数 ll lcm(ll a,ll b){return a/gcd(a,b)*b;} // 最小公倍数 ll Exp(ll x,ll y){ll cnt=-1; while(x>0) x/=y,cnt++; return cnt;} // y進桁数-1 ll powmod(ll x,ll k,ll m){if(k==0) return 1%m; ll r=powmod(x,k/2,m); r=(LL)r*r%m; if(k&1) r=(LL)r*x%m; return r;} // mod累乗 template T square(T x){return x*x;} // 二乗 template void Uni_erase(vector& v){sort(all(v)); v.erase(unique(all(v)),v.end());} // sortして重複削除 inline bool OutIn(ll x,ll n){return 0<=x&&x dist(l,r-1); return dist(rng);} // [l,r)乱数 void YesNo(bool x){x?p_yes():p_no();} // Yes/No出力 vl vl_n(ll n){vl ret(n); rep(i,n) ret[i]=i; return ret;} // 0..n-1のvector生成 vl vl_N(ll n){vl ret(n); rep(i,n) ret[i]=i+1; return ret;} // 1..nのvector生成 vl dijkstra(const graph& g,const vl& starts){ vl dist(g.size(),inf); queue q; for(ll s:starts) if(dist[s]==inf){dist[s]=0; q.push(s);} while(!q.empty()){ ll v=q.front(); q.pop(); for(ll to:g[v]) if(dist[to]==inf){dist[to]=dist[v]+1; q.push(to);} } return dist; } vl dijkstra(const graph& g,ll s){return dijkstra(g,vl{s});} vl dijkstra(const graph& g,initializer_list starts){return dijkstra(g,vl(starts));} vl dijkstra(const Graph& g,const vl& starts){ vl dist(g.size(),inf); rpq q; for(ll s:starts) if(dist[s]==inf){dist[s]=0; q.push({0,s});} while(!q.empty()){ auto [d,v]=q.top(); q.pop(); if(d!=dist[v]) continue; for(auto [to,w]:g[v]){ if(w>=inf-d) continue; ll nd=d+w; if(nd starts){return dijkstra(g,vl(starts));} const vl Pow2={1LL,2LL,4LL,8LL,16LL,32LL,64LL,128LL,256LL,512LL,1024LL,2048LL,4096LL,8192LL,16384LL,32768LL,65536LL,131072LL,262144LL,524288LL,1048576LL,2097152LL,4194304LL,8388608LL,16777216LL,33554432LL,67108864LL,134217728LL,268435456LL,536870912LL,1073741824LL,2147483648LL,4294967296LL,8589934592LL,17179869184LL,34359738368LL,68719476736LL,137438953472LL,274877906944LL,549755813888LL,1099511627776LL,2199023255552LL,4398046511104LL,8796093022208LL,17592186044416LL,35184372088832LL,70368744177664LL,140737488355328LL,281474976710656LL,562949953421312LL,1125899906842624LL,2251799813685248LL,4503599627370496LL,9007199254740992LL,18014398509481984LL,36028797018963968LL,72057594037927936LL,144115188075855872LL,288230376151711744LL,576460752303423488LL,1152921504606846976LL}; vl dx={0,1,0,-1}, dy={1,0,-1,0}; vl dx8={1,1,0,-1,-1,-1,0,1}, dy8={0,1,1,1,0,-1,-1,-1}; // 8近傍 vector fac,finv,pow2; void factorial(ll N=1000000LL){ll M=N+100; fac.assign(M+1,1); finv.assign(M+1,1); pow2.assign(M+1,1); rep1(i,M) fac[i]=fac[i-1]*i; finv[M]=fac[M].inv(); for(ll i=M;i>=1;i--) finv[i-1]=finv[i]*i; rep1(i,M) pow2[i]=pow2[i-1]*2;} // N+100まで階乗・逆階乗・2の累乗前計算 void ensure_factorial(ll N){if((ll)fac.size()>N) return; factorial(N);} // 階乗表の不足分確保 mint nCr(ll N,ll r){if(N<0||r<0||N class RangeSet { static_assert(std::is_integral_v && std::is_signed_v && sizeof(T) <= 8); static_assert((std::is_integral_v && !std::is_same_v && sizeof(Count) <= 8) || std::is_same_v); public: using value_type = T; using count_type = Count; using ptt = std::pair; using const_iterator = typename std::map::const_iterator; static constexpr T TINF = std::numeric_limits::max() / 2; private: using wide_type = __int128_t; std::map ranges_; Count total_ = 0; static wide_type length(T l, T r) { return static_cast(r) - static_cast(l); } static Count checked_count(wide_type value) { if (value > static_cast(std::numeric_limits::max())) std::abort(); return static_cast(value); } public: RangeSet() = default; RangeSet(std::initializer_list ranges) { for (auto [l, r] : ranges) insert(l, r); } RangeSet(const RangeSet&) = default; RangeSet& operator=(const RangeSet&) = default; RangeSet(RangeSet&& other) noexcept : ranges_(std::move(other.ranges_)), total_(std::exchange(other.total_, 0)) { other.ranges_.clear(); } RangeSet& operator=(RangeSet&& other) noexcept { if (this != &other) { ranges_ = std::move(other.ranges_); total_ = std::exchange(other.total_, 0); other.ranges_.clear(); } return *this; } std::optional covering_interval(T x) const { auto it = ranges_.upper_bound(x); if (it == ranges_.begin()) return std::nullopt; --it; if (x < it->second) return ptt{it->first, it->second}; return std::nullopt; } std::optional covering_interval(T l, T r) const { if (l >= r) return ptt{l, l}; auto interval = covering_interval(l); if (interval && r <= interval->second) return interval; return std::nullopt; } bool covered(T l, T r) const { return covering_interval(l, r).has_value(); } bool covered(T x) const { return covering_interval(x).has_value(); } bool contains(T x) const { return covered(x); } ptt covered_by(T l, T r) const { if (l >= r) return {0, 0}; return covering_interval(l, r).value_or(ptt{-TINF, -TINF}); } bool overlaps(T l, T r) const { if (l >= r) return false; auto it = ranges_.lower_bound(l); if (it != ranges_.end() && it->first < r) return true; return it != ranges_.begin() && std::prev(it)->second > l; } Count insert(T l, T r) { if (l >= r) return 0; auto first = ranges_.lower_bound(l); if (first != ranges_.begin() && std::prev(first)->second >= l) --first; auto last = first; T merged_l = l, merged_r = r; wide_type old_length = 0; while (last != ranges_.end() && last->first <= merged_r) { merged_l = std::min(merged_l, last->first); merged_r = std::max(merged_r, last->second); old_length += length(last->first, last->second); ++last; } const wide_type added = length(merged_l, merged_r) - old_length; const Count next_total = checked_count(static_cast(total_) + added); if (first == last) { ranges_.emplace_hint(last, merged_l, merged_r); } else { auto rest = std::next(first); auto node = ranges_.extract(first); ranges_.erase(rest, last); node.key() = merged_l; node.mapped() = merged_r; ranges_.insert(last, std::move(node)); } total_ = next_total; return static_cast(added); } Count insert(T x) { if (x == std::numeric_limits::max()) std::abort(); return insert(x, static_cast(x + 1)); } Count erase(T l, T r) { if (l >= r) return 0; auto it = ranges_.lower_bound(l); if (it != ranges_.begin() && std::prev(it)->second > l) --it; wide_type removed = 0; while (it != ranges_.end() && it->first < r) { const T a = it->first, b = it->second; removed += length(std::max(a, l), std::min(b, r)); if (a < l) { if (r < b) { ranges_.emplace(r, b); it->second = l; break; } it->second = l; ++it; } else if (b <= r) { it = ranges_.erase(it); } else { auto next = std::next(it); auto node = ranges_.extract(it); node.key() = r; ranges_.insert(next, std::move(node)); break; } } total_ = static_cast(static_cast(total_) - removed); return static_cast(removed); } Count erase(T x) { if (x == std::numeric_limits::max()) return 0; return erase(x, static_cast(x + 1)); } T mex(T x = 0) const { auto interval = covering_interval(x); return interval ? interval->second : x; } Count count_covered(T l, T r) const { if (l >= r) return 0; auto it = ranges_.lower_bound(l); if (it != ranges_.begin() && std::prev(it)->second > l) --it; wide_type count = 0; while (it != ranges_.end() && it->first < r) { count += length(std::max(l, it->first), std::min(r, it->second)); ++it; } return static_cast(count); } Count cover_length() const { return total_; } std::size_t size() const { return ranges_.size(); } bool empty() const { return ranges_.empty(); } void clear() { ranges_.clear(); total_ = 0; } void swap(RangeSet& other) noexcept { ranges_.swap(other.ranges_); std::swap(total_, other.total_); } std::vector intervals() const { return {ranges_.begin(), ranges_.end()}; } const_iterator begin() const { return ranges_.cbegin(); } const_iterator end() const { return ranges_.cend(); } void output() const { std::cout << "RangeSet: "; for (auto [l, r] : ranges_) std::cout << '[' << +l << ',' << +r << ") "; std::cout << '\n'; } }; /* 細かい注意点 整数座標の集合。区間は半開区間[l,r)。Tは座標、Countは個数の型(既定long long)。 ptt=pair。K/K2はrs/otherの操作前の区間数、Mは初期区間数、Dは走査・統合・削除する区間数。 Tは64bit以下の符号付き整数。Countはbool以外の64bit以下の整数または__int128_t。 Tの最大値は格納不可。insert(最大値)や総被覆数のCount超過はメッセージなしで停止。 erase(最大値)は0。大きな被覆数にはRangeSetを使う。 l>=rではinsert/erase/count_coveredは0、coveredはtrue、overlapsはfalse。 空区間のcovering_interval(l,r)は{l,l}、covered_by(l,r)は{0,0}。 size()は保持区間数、cover_length()は被覆された整数の個数。 列挙は左端昇順の読み取り専用。走査中に集合を更新しない。intervals()は独立なコピー。 TINFはcovered_byの互換返り値用。座標制限や内部番兵ではない。 空ならbegin()==end()。解放O(K)。output()は明示呼び出し時だけ標準出力する。 使える関数一覧 // 構築・コピー・ムーブ(コンストラクタには返り値はない) RangeSet rs; // 空集合で初期化 O(1) RangeSet rs{{a,b},{c,d}}; // M個の区間から構築、重複・隣接を統合 O(M log M) RangeSet rs(other); // 独立なコピーを構築 O(K2) RangeSet rs(std::move(other)); // 集合を移し、otherを空にする O(1) rs = other; // RangeSet&: rsへの参照。独立なコピーで上書き O(K+K2) rs = std::move(other); // RangeSet&: rsへの参照。集合を移し、otherを空にする O(K) // 追加・削除 rs.insert(l,r); // Count: [l,r)を追加し、新たに被覆した個数を返す O(log K+D) rs.insert(x); // Count: 1点xを追加し、新たに被覆した個数(0か1)を返す O(log K) rs.erase(l,r); // Count: [l,r)を削除し、実際に削除した個数を返す O(log K+D) rs.erase(x); // Count: 1点xを削除し、実際に削除した個数(0か1)を返す O(log K) // 被覆・重なりの判定 rs.covered(l,r); // bool: [l,r)全体が被覆されていればtrue O(log K) rs.covered(x); // bool: 1点xが被覆されていればtrue O(log K) rs.contains(x); // bool: covered(x)と同じ O(log K) rs.overlaps(l,r); // bool: [l,r)に被覆された整数が1つ以上あればtrue O(log K) // 保持区間の取得 rs.covering_interval(x); // optional: xを含む保持区間、なければnullopt O(log K) rs.covering_interval(l,r); // optional: [l,r)全体を含む保持区間、なければnullopt O(log K) rs.covered_by(l,r); // ptt: 包含する保持区間、なければ{-TINF,-TINF} O(log K) // mex・個数・状態 rs.mex(x); // T: x以上の未被覆の整数のうち最小のものを返す O(log K) rs.mex(); // T: 0以上の未被覆の整数のうち最小のものを返す O(log K) rs.count_covered(l,r); // Count: [l,r)内で被覆された整数の個数を返す O(log K+D)、最悪O(K) rs.cover_length(); // Count: 集合全体で被覆された整数の個数を返す O(1) rs.size(); // size_t: 保持する区間数を返す(整数の個数ではない) O(1) rs.empty(); // bool: 空集合ならtrue O(1) rs.clear(); // void: 全区間を削除し、総被覆数も0にする O(K) rs.swap(other); // void: otherと区間集合・総被覆数を交換 O(1) // 区間の列挙・表示 rs.intervals(); // vector: 左端の昇順で全保持区間のコピーを返す O(K)、追加メモリO(K) rs.begin(); // const_iterator: 最初の区間を指すイテレータを返す O(1) rs.end(); // const_iterator: 最後の区間の次を指すイテレータを返す O(1) for (auto [l,r] : rs) { ... } // 読み取り専用で全区間を左端の昇順に走査 O(K) rs.output(); // void: "RangeSet: [l,r) ..."形式で全区間を標準出力 O(K) 基本の関数 RangeSet rs; // 空集合 rs.insert(1,10); // [1,10)を追加 rs.erase(3,7); // [3,7)を削除 auto covered = rs.covered(1,3); // true auto mex = rs.mex(1); // 3 auto count = rs.cover_length(); // 5 */ signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n; cin >> n; auto a = cin_vl(n); ll ans = 0; RangeSet rs; rep(i,n){ if(rs.covered(a[i])){ auto itr = rs.covered_by(a[i],a[i]+1); auto[l,r] = itr; //p2(l,r); ans += (a[i]-l+1)*(r-a[i]); ll y = l+r-1-a[i]; rs.erase(l,r); rs.insert(l-1,y); rs.insert(y+1,r+1); } else rs.insert(a[i],a[i]+1); } p(ans); }