結果
問題 | No.924 紲星 |
ユーザー | f1b_maxbl00d |
提出日時 | 2022-07-02 06:02:23 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2,932 ms / 4,000 ms |
コード長 | 15,306 bytes |
コンパイル時間 | 2,992 ms |
コンパイル使用メモリ | 187,872 KB |
実行使用メモリ | 268,780 KB |
最終ジャッジ日時 | 2024-05-05 00:47:13 |
合計ジャッジ時間 | 26,671 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 5 ms
5,376 KB |
testcase_06 | AC | 4 ms
5,376 KB |
testcase_07 | AC | 3 ms
5,376 KB |
testcase_08 | AC | 2,932 ms
268,780 KB |
testcase_09 | AC | 2,811 ms
255,444 KB |
testcase_10 | AC | 2,849 ms
260,492 KB |
testcase_11 | AC | 2,876 ms
268,780 KB |
testcase_12 | AC | 2,809 ms
255,572 KB |
testcase_13 | AC | 1,075 ms
99,964 KB |
testcase_14 | AC | 912 ms
54,644 KB |
testcase_15 | AC | 908 ms
76,972 KB |
testcase_16 | AC | 1,387 ms
222,940 KB |
testcase_17 | AC | 1,485 ms
101,868 KB |
testcase_18 | AC | 2 ms
5,376 KB |
ソースコード
//#pragma warning(disable:4996) //#include <Windows.h> #include <iostream> #include <vector> #include <limits.h> #include <algorithm> #include <string> #include <math.h> #include <limits.h> #include <queue> #include <map> #include <set> #include <iomanip> #include <bitset> #include <cassert> #include <random> #include <functional> #include <stack> #include <iomanip> #include <cassert> //#include <boost/multiprecision/cpp_int.hpp> #include <complex> #include <cstdio> #include <list> #include <bitset> //#include <stdio.h> //< in.txt > out.txt using namespace std; //std::ios::sync_with_stdio(false); //std::cin.tie(0); const long long MOD = 1e9 + 7; const long long INF = 1e18; typedef long long LL; typedef long double LD; typedef unsigned long long ULL; //typedef boost::multiprecision::cpp_int bigint; typedef pair<LL, LL> PLL; typedef pair<int, int> PI; typedef pair<LD, LL> pdl; typedef pair<LD, LD> pdd; typedef vector<LL> VLL; typedef vector<VLL> VVLL; typedef vector<int> VI; typedef vector<vector<int>> VVI; typedef unsigned long long ULL; template<class T> using pqueue = priority_queue<T, vector<T>, function<bool(T, T)>>; string alphabet = "abcdefghijklmnopqrstuvwxyz"; template<class T> inline void chmin(T& a, T b) { a = min(a, b); } template<class T> inline void chmax(T& a, T b) { a = max(a, b); } //y/xのfloorを求める LL floor_(LL y, LL x) { if (x < 0) { x *= -1; y *= -1; } if (y >= 0) { return y / x; } else { if ((-y) % x == 0) { return y / x; } else { return -((-y) / x) - 1; } } } inline LL mod(LL a, LL m) { LL res = a % m; return res >= 0 ? res : res + m; } void input(); void solve(); void daminput(); void naive(); void outputinput(); int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); cout << fixed << setprecision(12); input(); //daminput(); solve(); //naive(); //outputinput(); return 0; } ////////////////////////////////////////////////// ////////////////////////////////////////////////// template<class T> class CPSegmentTree { public: CPSegmentTree() {} CPSegmentTree(int n, function<T(T, T)> tt, T t0) { build(n, tt, t0); } CPSegmentTree(vector<T>& ar0, function<T(T, T)> tt, T t0) { build(ar0, tt, t0); } void build(int n, function<T(T, T)> tt, T t0) { TT = tt; T0 = t0; height = 1; //2の累乗化 int rn = 1; while (rn < n) { rn *= 2; height++; } N = rn; ar.resize(2 * N - 1, t0); cl.resize(2 * N - 1, -1); cr.resize(2 * N - 1, -1); time.resize(2 * N - 1, 0); for (int n = 0; n < N - 1; n++) { cl[n] = 2 * n + 1; cr[n] = 2 * n + 2; } roots.push_back(0); } void build(vector<T>& ar0, function<T(T, T)> tt, T t0) { TT = tt; T0 = t0; N = ar0.size(); int rn = 1; while (rn < N) { rn *= 2; height++; } N = rn; cl.resize(2 * N - 1, -1); cr.resize(2 * N - 1, -1); time.resize(2 * N - 1, 0); for (int n = 0; n < N - 1; n++) { cl[n] = 2 * n + 1; cr[n] = 2 * n + 2; } ar.resize(2 * N - 1, t0); for (int n = 0; n < ar0.size(); n++) { ar[N - 1 + n] = ar0[n]; } for (int n = N - 2; n >= 0; n--) { ar[n] = TT(ar[cl[n]], ar[cr[n]]); } roots.push_back(0); } //時間tの木のコピーを作る この木を表す時間を返す //(コピー元の木をこの後いじると壊れる) int copy(int t) { int oldr = roots[t]; int newt = roots.size(); roots.push_back(ar.size()); ar.push_back(ar[oldr]); cl.push_back(cl[oldr]); cr.push_back(cr[oldr]); time.push_back(newt); return newt; } //時間tの頂点nをxに更新 void set(int t, int n, T x) { set_node(t, roots[t], 0, N, n, x); } //時間tの頂点nにxを左からかける void addl(int t, int n, T x) { T old = get(t, n); set(t, n, TT(x, old)); } //時間tの頂点nにxを右からかける void addr(int t, int n, T x) { T old = get(t, n); set(t, n, TT(old, x)); } //時刻tにおける、[l,r)の範囲の積を返す T get(int t, int l, int r) { return get_node(l, r, roots[t], 0, N); } //時間tにおける、葉nの値 T get(int t, int n) { return get(t, n, n + 1); } private: template<class U> friend class StaticRectangleSum; //要素数(2の累乗化済み) int N; //要素 vector<T> ar; //左右の子は何か VI cl, cr; //積 function<T(T, T)> TT; //単位元 T T0; //時刻tにおける根のid(はじめの時刻は0) VI roots; //この木の高さ int height; //各頂点の属する時間 VI time; //時間tの頂点pに対する更新処理 //範囲[l,r)を持つ //更新処理をした結果の自分の頂点番号を返す(新しく時間tに頂点を登録した場合) int set_node(int t, int p, int l, int r, int n, T x) { //頂点pが時間tの頂点でなければ、新しい頂点を作ったうえで変更 if (time[p] != t) { int newp = ar.size(); ar.push_back(ar[p]); cl.push_back(cl[p]); cr.push_back(cr[p]); time.push_back(t); p = newp; } //この頂点が頂点n自身の場合 if (l == n && r == n + 1) { ar[p] = x; return p; } //左の子は[l,m)、右の子は[m,r)を持つ int m = (r - l) / 2 + l; //頂点nが左の子に含まれる場合 if (n < m) { cl[p] = set_node(t, cl[p], l, m, n, x); } //頂点nが右の子に含まれる場合 else { cr[p] = set_node(t, cr[p], m, r, n, x); } ar[p] = TT(ar[cl[p]], ar[cr[p]]); return p; } //再帰用 n:=見る頂点、頂点nの表す範囲は[s,e) T get_node(int l, int r, int n, int s, int e) { if (l <= s && e <= r) { return ar[n]; } //左の子は[s,m)、右の子は[m,e)を持つ int m = (e - s) / 2 + s; T res = T0; //左の子が[l,r)とかぶる if (r > s && m > l) { res = get_node(l, r, cl[n], s, m); } //右の子が[l,r)とかぶる if (r > m && e > l) { res = TT(res, get_node(l, r, cr[n], m, e)); } return res; } int size() { return N; } }; //二次元領域[0,W)×[0,H)のアーベル群重み付き格子点の範囲和、x座標方向のupper/lower boundを求める //need CPSegmentTree template<class T> class StaticRectangleSum { private: int W, H; CPSegmentTree<T> seg; //Tの演算 function<T(T, T)> tt; //逆元 function<T(T)> neg; //単位元 T t0; public: StaticRectangleSum() :W(0), H(0) {} StaticRectangleSum(int w, int h, vector<tuple<int, int, T>> points, T t0_ = T(0), function<T(T, T)> tt_ = [](T a, T b) {return a + b; }, function<T(T)> neg_ = [](T a) {return -a; }) { build(w, h, points, t0_, tt_, neg_); } //points:(x座標,y座標,重み)の配列 0≦x座標<W、0≦y座標<Hである必要がある void build(int w, int h, vector<tuple<int, int, T>> points, T t0_ = T(0), function<T(T, T)> tt_ = [](T a, T b) {return a + b; }, function<T(T)> neg_ = [](T a) {return -a; }) { W = w; H = h; tt = tt_; neg = neg_; t0 = t0_; seg.build(W, tt, t0); //upper/lower boundのために、時間tをy座標H-yと同一視 sort(points.begin(), points.end(), [](tuple<int, int, T>& p1, tuple<int, int, T>& p2) { return (std::get<1>(p1) > std::get<1>(p2)); }); //今見てる時間t(y=H-t) int curt = 0; for (tuple<int, int, T>& p : points) { int x, y; T w; tie(x, y, w) = p; while (H - curt != y) { seg.copy(curt++); } seg.addl(curt, x, w); } while (H - curt != 0) { seg.copy(curt++); } } //[x=l,r)×[y=b,u)の範囲の重み和を求める T get(int l, int r, int b, int u) { //y座標[b,u)を時間(u,b]に変換 b = H - b; u = H - u; T sum = seg.get(b, l, r); sum = tt(sum, neg(seg.get(u, l, r))); return sum; } //[l,e-1)×[d,u)の和 < x <= [l,e)×[d,u)の和となるe(l<=e<=W+1)を求める(単調増加性を仮定) //less(a,b) := a<bならばtrue int lower_bound(int l, int d, int u, T x, function<bool(T, T)> less = [](T a, T b) {return a < b; }) { //y座標を[d,u)から時間(u,d]に変換 d = H - d; u = H - u; struct nodebfs { //時間u,dにおける見てる頂点 int nu, nd; //頂点nは[a,b)を表す int a, b; }; //[l,W)を覆うようなノードの集合 vector<nodebfs> nodes; queue<nodebfs> nodebfsq; int RN = seg.size(); nodebfsq.push({ seg.roots[u],seg.roots[d],0,RN }); while (!nodebfsq.empty()) { int nu = nodebfsq.front().nu; int nd = nodebfsq.front().nd; int a = nodebfsq.front().a; int b = nodebfsq.front().b; nodebfsq.pop(); if (W <= a || b <= l) { continue; } if (l <= a && b <= W) { nodes.push_back({ nu,nd,a,b }); } else { nodebfsq.push({ seg.cl[nu],seg.cl[nd],a,(a + b) / 2 }); nodebfsq.push({ seg.cr[nu],seg.cr[nd],(a + b) / 2,b }); } } //nodes[0,nn]の和 < x <= nodes[0,nn + 1]の和 int nn = -1; //nodes[0,nn]の和 T sum = t0; while (nn + 1 < nodes.size()) { T next = tt(seg.ar[nodes[nn + 1].nd], neg(seg.ar[nodes[nn + 1].nu])); next = tt(sum, next); //nodes[0,nn+1]の和 >= xのとき if (!less(next, x)) { break; } else { nn++; sum = next; } } //全部とっても<x if (nn == nodes.size() - 1 && less(sum, x)) { return W; } nn++; //nodes[nn]をバラす //[l,r) < x int r = l; if (nn - 1 >= 0) { r = nodes[nn - 1].b; } nodebfs cur = nodes[nn]; int a = nodes[nn].a; int b = nodes[nn].b; while (b - a > 1) { //左の子の和 int chl_d = seg.cl[cur.nd]; int chl_u = seg.cl[cur.nu]; T suml = tt(seg.ar[chl_d], neg(seg.ar[chl_u])); if (!less(tt(sum, suml), x)) { b = (a + b) / 2; cur = { chl_u,chl_d,a,b }; } else { sum = tt(sum, suml); int chr_d = seg.cr[cur.nd]; int chr_u = seg.cr[cur.nu]; r = (a + b) / 2; a = (a + b) / 2; cur = { chr_u,chr_d,a,b }; } } return r + 1; } //[l,e-1)×[d,u)の和 <= x < [l,e)×[d,u)の和となるe(l<=e<=W+1)を求める(単調増加性を仮定) //less(a,b) := a<bならばtrue int upper_bound(int l, int d, int u, T x, function<bool(T, T)> less = [](T a, T b) {return a < b; }) { //y座標を[d,u)から時間(u,d]に変換 d = H - d; u = H - u; struct nodebfs { //時間u,dにおける見てる頂点 int nu, nd; //頂点nは[a,b)を表す int a, b; }; //[l,W)を覆うようなノードの集合 vector<nodebfs> nodes; queue<nodebfs> nodebfsq; int RN = seg.size(); nodebfsq.push({ seg.roots[u],seg.roots[d],0,RN }); while (!nodebfsq.empty()) { int nu = nodebfsq.front().nu; int nd = nodebfsq.front().nd; int a = nodebfsq.front().a; int b = nodebfsq.front().b; nodebfsq.pop(); if (W <= a || b <= l) { continue; } if (l <= a && b <= W) { nodes.push_back({ nu,nd,a,b }); } else { nodebfsq.push({ seg.cl[nu],seg.cl[nd],a,(a + b) / 2 }); nodebfsq.push({ seg.cr[nu],seg.cr[nd],(a + b) / 2,b }); } } //nodes[0,nn]の和 <= x < nodes[0,nn + 1]の和 int nn = -1; //nodes[0,nn]の和 T sum = t0; while (nn + 1 < nodes.size()) { T next = tt(seg.ar[nodes[nn + 1].nd], neg(seg.ar[nodes[nn + 1].nu])); next = tt(sum, next); //nodes[0,nn+1]の和 > xのとき if (less(x, next)) { break; } else { nn++; sum = next; } } //全部とっても<=x if (nn == nodes.size() - 1 && !less(x, sum)) { return W; } nn++; //nodes[nn]をバラす //[l,r) <= x int r = l; if (nn - 1 >= 0) { r = nodes[nn - 1].b; } nodebfs cur = nodes[nn]; int a = nodes[nn].a; int b = nodes[nn].b; while (b - a > 1) { //左の子の和 int chl_d = seg.cl[cur.nd]; int chl_u = seg.cl[cur.nu]; T suml = tt(seg.ar[chl_d], neg(seg.ar[chl_u])); if (less(x, tt(sum, suml))) { b = (a + b) / 2; cur = { chl_u,chl_d,a,b }; } else { sum = tt(sum, suml); int chr_d = seg.cr[cur.nd]; int chr_u = seg.cr[cur.nu]; r = (a + b) / 2; a = (a + b) / 2; cur = { chr_u,chr_d,a,b }; } } return r + 1; } }; //各項が0以上M未満の静的整数列のRange Kth SmallestやRange Countを求める //(x座標が要素、y座標は添え字) class CPSegSequence { private: StaticRectangleSum<LL> rec; int N; int M; public: CPSegSequence() {}; CPSegSequence(int m, VLL& seq) { build(m, seq); } void build(int m, VLL& seq) { M = m; N = seq.size(); vector<tuple<int, int, LL>> points; points.reserve(N); for (int n = 0; n < N; n++) { points.emplace_back(seq[n], n, 1); } rec.build(M, N, points); } //A[l]からA[r-1]のうち、s以上e未満の要素の数を求める int get(int l, int r, int s, int e) { return rec.get(max(s, 0), min(e, M), l, r); } //A[l]からA[r-1]のうち、[d,u-1)の要素の数 < x <= [d,u)の要素の数なるuを求める int lower_bound(int l, int r, int d, int x) { return rec.lower_bound(d, l, r, x); } //A[l]からA[r-1]のうち、[d,u-1)の要素の数 <= x < [d,u)の要素の数なるuを求める int upper_bound(int l, int r, int d, int x) { return rec.upper_bound(d, l, r, x); } //A[l]からA[r-1]のうち、k番目(1-indexed)に小さい数を求める int kthnumber(int l, int r, int k) { return rec.lower_bound(0, l, r, k) - 1; } }; //座圧 class CoordComp { public: int N; VI new2old; map<LL, int> old2new; CoordComp() :N(0) {}; CoordComp(VLL& v) { build(v); } //vに含まれる数に昇順で添え字(0-index)を設定する(vは変更しない) void build(VLL& v) { set<LL> all; for (LL t : v) { all.insert(t); } N = all.size(); new2old.reserve(N); int i = 0; for (LL t : all) { old2new.insert(pair<LL, int>(t, i++)); new2old.push_back(t); } } //tを圧縮した座標を返す LL conv(int t) { return old2new[t]; } //[l,r)が含む登録点の集合を変換後の座標の区間[s,e)で返す(登録点が存在しなければ[-1,-1)を返す) PI conv(LL l, LL r) { int s = lower_bound(l); int e = lower_bound(r); return PI(s, e); } //revconv(e-1) <= x < revconv(e)なるeを返す int upper_bound(LL x) { int s = -1, e = N; while (e - s > 1) { int m = (e + s) / 2; if (new2old[m] <= x) { s = m; } else { e = m; } } return e; } //revconv(e-1) < x <= revconv(e)なるeを返す int lower_bound(LL x) { int s = -1, e = N; while (e - s > 1) { int m = (e + s) / 2; if (new2old[m] < x) { s = m; } else { e = m; } } return e; } //圧縮済みの座標から、元の数を返す LL revconv(int i) { return new2old[i]; } //登録点の個数 int size() { return N; } }; int N, Q; VLL A; void input() { cin >> N >> Q; A.resize(N); for (int n = 0; n < N; n++) { cin >> A[n]; } } void daminput() { } void solve() { CoordComp coord(A); VLL ord(N); for (int n = 0; n < N; n++) { ord[n] = coord.conv(A[n]); } CPSegSequence seq(coord.size(),ord); vector<tuple<int, int, LL>> points; points.reserve(N); for (int n = 0; n < N; n++) { points.emplace_back(ord[n], n, A[n]); } StaticRectangleSum<LL> recsum(coord.size(), N, points); for (int q = 0; q < Q; q++) { int l, r; cin >> l >> r; l--; r--; int d = (r - l) / 2 + 1; LL x = seq.kthnumber(l, r + 1, d); int c = seq.get(l, r + 1, 0, x + 1); LL sum = coord.revconv(x) * c - recsum.get(0, x + 1, l, r + 1); sum += recsum.get(x + 1, coord.size(), l, r + 1) - coord.revconv(x) * (r - l + 1 - c); cout << sum << "\n"; } } void naive() { } void outputinput() { }