結果
問題 | No.1270 Range Arrange Query |
ユーザー |
|
提出日時 | 2020-10-29 00:02:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 738 ms / 7,000 ms |
コード長 | 6,762 bytes |
コンパイル時間 | 1,530 ms |
コンパイル使用メモリ | 146,264 KB |
最終ジャッジ日時 | 2025-01-15 16:18:25 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include <iostream>#include <string>#include <sstream>#include <stack>#include <algorithm>#include <cmath>#include <queue>#include <bitset>#include <iomanip>#include <limits>#include <chrono>#include <random>#include <array>#include <unordered_map>#include <functional>#include <complex>#include <numeric>#include <cctype>#include <map>#include <set>#include <cstdlib>#include <bitset>#include <tuple>#include <assert.h>#include <deque>#include <utility>#include <fstream>using namespace std;typedef long long ll;using ull = unsigned long long;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; }template<typename T> T gcd(T a, T b) { a = abs(a), b = abs(b); while (b > 0) { tie(a, b) = make_pair(b, a % b); } return a; }mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());constexpr long long INF = 1LL << 60;constexpr int inf = 1000000007;//constexpr long long mod = 1000000007LL;constexpr long long mod = 998244353;constexpr int MAX = 1100000;struct Mo {int n;vector<pair<int, int>> lr;Mo(int n) :n(n) {}//[l, r)void add(int l, int r) {lr.emplace_back(l, r);}template<typename AL, typename AR, typename EL, typename ER, typename O>void build(const AL& add_left, const AR& add_right, const EL& erase_left, const ER& erase_right, const O& out) {int query_size = lr.size();int bs = n / min(n, (int)sqrt(query_size));vector<int> ord(query_size);iota(ord.begin(), ord.end(), 0);sort(ord.begin(), ord.end(), [&](auto a, auto b) {int a_block_index = lr[a].first / bs;int b_block_index = lr[b].first / bs;if (a_block_index != b_block_index) return a_block_index < b_block_index;else return (a_block_index & 1) ? lr[a].second > lr[b].second : lr[a].second < lr[b].second;});int l = 0, r = 0;for (auto idx : ord) {while (l > lr[idx].first) add_left(--l);while (r < lr[idx].second) add_right(r++);while (l < lr[idx].first) erase_left(l++);while (r > lr[idx].second) erase_right(--r);out(idx);}}template<typename A, typename E, typename O>void build(const A& add, const E& erase, const O& out) {build(add, add, erase, erase, out);}};template<typename T>struct BIT {int n;vector<T> bit;BIT() :n(0) {}BIT(int _n) :n(_n) { bit = vector<T>(n + 1); }void add1(int idx, T val) {for (int i = idx; i <= n; i += i & -i) bit[i] += val;}T sum1(int idx) {T res = 0;for (int i = idx; i > 0; i -= i & -i) res += bit[i];return res;}//0-indexedvoid add(int idx, T val) { add1(idx + 1, val); }//0-indexed [left, right)T sum(int left, int right) { return sum1(right) - sum1(left); }int lower_bound(T x) {int res = 0;int k = 1;while (2 * k <= n) k <<= 1;for (; k > 0; k >>= 1) {if (res + k <= n and bit[res + k] < x) {x -= bit[res + k];res += k;}}return res;}};/*** @brief Lazy-Segment-Tree(遅延伝搬セグメント木)* @docs docs/lazy-segment-tree.md*/template< typename Monoid, typename OperatorMonoid, typename F, typename G, typename H >struct LazySegmentTree {int sz, height;vector< Monoid > data;vector< OperatorMonoid > lazy;const F f;const G g;const H h;const Monoid M1;const OperatorMonoid OM0;LazySegmentTree(int n, const F f, const G g, const H h,const Monoid& M1, const OperatorMonoid OM0): f(f), g(g), h(h), M1(M1), OM0(OM0) {sz = 1;height = 0;while (sz < n) sz <<= 1, height++;data.assign(2 * sz, M1);lazy.assign(2 * sz, OM0);}void set(int k, const Monoid& x) {data[k + sz] = x;}void build() {for (int k = sz - 1; k > 0; k--) {data[k] = f(data[2 * k + 0], data[2 * k + 1]);}}inline void propagate(int k) {if (lazy[k] != OM0) {lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);data[k] = apply(k);lazy[k] = OM0;}}inline Monoid apply(int k) {return lazy[k] == OM0 ? data[k] : g(data[k], lazy[k]);}inline void recalc(int k) {while (k >>= 1) data[k] = f(apply(2 * k + 0), apply(2 * k + 1));}inline void thrust(int k) {for (int i = height; i > 0; i--) propagate(k >> i);}void update(int a, int b, const OperatorMonoid& x) {if (a >= b) return;thrust(a += sz);thrust(b += sz - 1);for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {if (l & 1) lazy[l] = h(lazy[l], x), ++l;if (r & 1) --r, lazy[r] = h(lazy[r], x);}recalc(a);recalc(b);}Monoid query(int a, int b) {if (a >= b) return M1;thrust(a += sz);thrust(b += sz - 1);Monoid L = M1, R = M1;for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {if (l & 1) L = f(L, apply(l++));if (r & 1) R = f(apply(--r), R);}return f(L, R);}Monoid operator[](const int& k) {return query(k, k + 1);}};template< typename Monoid, typename OperatorMonoid, typename F, typename G, typename H >LazySegmentTree< Monoid, OperatorMonoid, F, G, H > get_lazy_segment_tree(int N, const F& f, const G& g, const H& h, const Monoid& M1, const OperatorMonoid& OM0) {return { N, f, g, h, M1, OM0 };}int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n, Q; cin >> n >> Q;BIT<ll> b1(n), b2(n);ll inv = 0;vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i], a[i] -= 1;for (int i = 0; i < n; i++) {inv += b2.sum(a[i] + 1, n);b2.add(a[i], 1);}Mo mo(n);for (int i = 0; i < Q; i++) {int l, r; cin >> l >> r;l--;mo.add(l, r);}auto f = [&](ll a, ll b)->ll {return min(a, b);};auto g = [&](ll a, ll b)->ll {return a + b;};auto lsg = get_lazy_segment_tree(n, f, g, g, INF, 0);for (int i = 0; i < n; i++) lsg.set(i, 0); lsg.build();for (int i = 0; i < n; i++) {lsg.update(a[i] + 1, n, 1);}vector<ll> res(Q);auto add_left = [&](int idx)->void {b1.add(a[idx], -1);inv -= b1.sum(a[idx] + 1, n) + b2.sum(0, a[idx]);lsg.update(0, a[idx], -1);};auto add_right = [&](int idx)->void {b2.add(a[idx], -1);inv -= b1.sum(a[idx] + 1, n) + b2.sum(0, a[idx]);lsg.update(a[idx] + 1, n, -1);};auto erase_left = [&](int idx)->void {b1.add(a[idx], 1);inv += b1.sum(a[idx] + 1, n) + b2.sum(0, a[idx]);lsg.update(0, a[idx], 1);};auto erase_right = [&](int idx)->void {b2.add(a[idx], 1);inv += b1.sum(a[idx] + 1, n) + b2.sum(0, a[idx]);lsg.update(a[idx] + 1, n, 1);};auto out = [&](int idx)->void {ll len = mo.lr[idx].second - mo.lr[idx].first;ll mn = lsg.query(0, n);res[idx] = inv + mn * len;};mo.build(add_left, add_right, erase_left, erase_right, out);for (int i = 0; i < res.size(); i++) cout << res[i] << "\n";}