結果
| 問題 |
No.925 紲星 Extra
|
| コンテスト | |
| ユーザー |
 lumc_
|
| 提出日時 | 2019-09-17 19:17:43 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 12,510 bytes |
| コンパイル時間 | 1,645 ms |
| コンパイル使用メモリ | 122,476 KB |
| 実行使用メモリ | 814,592 KB |
| 最終ジャッジ日時 | 2024-09-15 05:46:55 |
| 合計ジャッジ時間 | 5,265 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 2 MLE * 1 -- * 16 |
ソースコード
#if 0
たぶん想定 MLE もしくは TLE
メモリでたぶん落ちると思われる
2^17 * 40 * 40 * 8 byte ~ 1600 MB ぐらい？ 実際はこの数倍必要なはず
dynamic seg on dynamic seg + 二分探索
たぶん
space : O((N + Q) lg^2 A)
time : O(N lg^2 N + Q lg^3 N)
#endif
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;
constexpr ll inf = 1ll << 40;
// - scalable
// DynamicSegmentTree([ <initial> ])
// - fixed-range
// DynamicSegmentTree(L, R [, <initial> ])
// DynamicSegmentTree(size [, <initial> ])
// === initial values ===
// <initial> := one value or function
// when you feed initial-one-value : O(log^2 N) time / query
// when you feed initial-function
// : O(timeof(f(l, r)) log N) time / query
// === --- ===
// NOTE : one value is recommended rather than O(log SIZE) function
// NOTE : better to use fixed-range
/// --- Dynamic SegmentTree {{{ ///
#include <cassert>
#include <functional>
#include <memory>
template < class Monoid >
struct DynamicSegmentTreeNode {
public:
using T = typename Monoid::T;
using node_type = DynamicSegmentTreeNode;
using pointer = node_type *;
T value;
pointer l = 0, r = 0;
DynamicSegmentTreeNode(T value = Monoid::identity()) : value(value) {}
DynamicSegmentTreeNode(pointer l, pointer r) : l(l), r(r) {}
};
template < class Monoid,
class Allocator = std::allocator< DynamicSegmentTreeNode< Monoid > > >
struct DynamicSegmentTree {
public:
using T = typename Monoid::T;
using size_type = long long;
using node_type = DynamicSegmentTreeNode< Monoid >;
using pointer = node_type *;
using func_type = std::function< T(size_type l, size_type r) >;
private:
static Allocator alc;
pointer top = 0;
// it should be only given positive length ranges
func_type get_initial = [](...) { return Monoid::identity(); };
const bool range_fixed;
size_type L, R;
void expand(size_type t) {
assert(!range_fixed);
while(t < L || R <= t) {
if(R == static_cast< size_type >(0))
R = 1;
else {
R <<= 1;
if(top) {
pointer new_l = 0, new_r = 0;
if(top->l)
std::allocator_traits< Allocator >::construct(
alc, new_l = alc.allocate(1), nullptr, top->l);
if(top->r)
std::allocator_traits< Allocator >::construct(
alc, new_r = alc.allocate(1), top->r, nullptr);
top->l = new_l, top->r = new_r;
if(new_l) update(new_l, -R, 0);
if(new_r) update(new_r, 0, R);
update(top, -R, R);
}
}
L = -R;
}
}
void update(pointer node, size_type l, size_type r) {
assert(node && r - l >= 2);
node->value = Monoid::op(node->l ? node->l->value : get_initial(l, (l + r) / 2),
node->r ? node->r->value : get_initial((l + r) / 2, r));
}
public:
// scalable
DynamicSegmentTree() : range_fixed(0), L(0), R(0) {}
DynamicSegmentTree(const T &initial) : DynamicSegmentTree() { set_initial(initial); }
DynamicSegmentTree(const func_type &get_initial) : DynamicSegmentTree() {
this->get_initial = get_initial;
}
// [L, R)
DynamicSegmentTree(size_type L, size_type R) : range_fixed(1), L(L), R(R) {
assert(L < R);
}
DynamicSegmentTree(size_type L, size_type R, const T &initial)
: DynamicSegmentTree(L, R) {
set_initial(initial);
}
DynamicSegmentTree(size_type L, size_type R, const func_type &get_initial)
: DynamicSegmentTree(L, R) {
this->get_initial = get_initial;
}
// [0, R)
DynamicSegmentTree(size_type R) : DynamicSegmentTree(0, R) {}
DynamicSegmentTree(size_type R, const T &initial) : DynamicSegmentTree(R) {
set_initial(initial);
}
DynamicSegmentTree(size_type R, const func_type &get_initial) : DynamicSegmentTree(R) {
this->get_initial = get_initial;
}
void set_initial(const T &initial) {
get_initial = [initial](size_type l, size_type r) {
size_type n = r - l;
n--;
T u = initial, v = initial;
while(n) {
if(n & 1) u = Monoid::op(u, v);
n >>= 1;
if(n) v = Monoid::op(v, v);
}
return u;
};
}
void set(size_type i, const T &val) {
if(!range_fixed)
expand(i);
else
assert(L <= i && i < R);
if(!top)
std::allocator_traits< Allocator >::construct(
alc, top = alc.allocate(1), get_initial(L, R));
set(i, val, L, R, top);
}
private:
void set(size_type i, const T &val, size_type l, size_type r, pointer node) {
assert(node);
if(r - l == 1) {
node->value = val;
return;
}
size_type m = (l + r) / 2;
if(i < m) {
if(!node->l)
std::allocator_traits< Allocator >::construct(
alc, node->l = alc.allocate(1), get_initial(l, m));
set(i, val, l, m, node->l);
} else {
if(!node->r)
std::allocator_traits< Allocator >::construct(
alc, node->r = alc.allocate(1), get_initial(m, r));
set(i, val, m, r, node->r);
}
update(node, l, r);
}
public:
T fold(size_type l, size_type r) {
if(range_fixed) {
if(l < L) l = L;
if(R < r) r = R;
}
if(l >= r) return Monoid::identity();
if(!range_fixed) {
if(r < L || R < l) return get_initial(l, r);
if(l < L) return Monoid::op(get_initial(l, L), fold(L, r));
if(R < r) return Monoid::op(fold(l, R), get_initial(R, r));
}
return fold(l, r, L, R, top);
}
T get(size_type i) {
if(range_fixed) assert(L <= i && i < R);
return fold(i, i + 1);
}
private:
T fold(size_type a, size_type b, size_type l, size_type r, pointer node) {
if(b <= l || r <= a) return Monoid::identity();
if(!node)
return get_initial(std::max< size_type >(a, l), std::min< size_type >(b, r));
if(a <= l && r <= b) return node->value;
return Monoid::op(
fold(a, b, l, (l + r) / 2, node->l), fold(a, b, (l + r) / 2, r, node->r));
}
};
template < class Monoid, class Allocator >
Allocator DynamicSegmentTree< Monoid, Allocator >::alc;
/// }}}--- ///
/// --- Monoid examples {{{ ///
constexpr long long inf_monoid = 1e18 + 100;
#include <algorithm>
struct Nothing {
using T = char;
using Monoid = Nothing;
using M = T;
static constexpr T op(const T &, const T &) { return T(); }
static constexpr T identity() { return T(); }
template < class X >
static constexpr X actInto(const M &, long long, const X &x) {
return x;
}
};
template < class U = long long >
struct RangeMin {
using T = U;
static T op(const T &a, const T &b) { return std::min< T >(a, b); }
static constexpr T identity() { return T(inf_monoid); }
};
template < class U = long long >
struct RangeMax {
using T = U;
static T op(const T &a, const T &b) { return std::max< T >(a, b); }
static constexpr T identity() { return T(-inf_monoid); }
};
template < class U = long long >
struct RangeSum {
using T = U;
static T op(const T &a, const T &b) { return T(a.first + b.first, a.second + b.second); }
static constexpr T identity() { return T(0, 0); }
};
template < class U >
struct RangeProd {
using T = U;
static T op(const T &a, const T &b) { return a * b; }
static constexpr T identity() { return T(1); }
};
template < class U = long long >
struct RangeOr {
using T = U;
static T op(const T &a, const T &b) { return a | b; }
static constexpr T identity() { return T(0); }
};
#include <bitset>
template < class U = long long >
struct RangeAnd {
using T = U;
static T op(const T &a, const T &b) { return a & b; }
static constexpr T identity() { return T(-1); }
};
template < size_t N >
struct RangeAnd< std::bitset< N > > {
using T = std::bitset< N >;
static T op(const T &a, const T &b) { return a & b; }
static constexpr T identity() { return std::bitset< N >().set(); }
};
/// }}}--- ///
using Seg = DynamicSegmentTree< RangeSum<pair<ll, ll>> >;
using P = pair<ll, ll>;
P op(P a, P b) {
a.first += b.first;
a.second += b.second;
return a;
}
template<class T = long long, class Index = long long>
struct DynamicSegmentTree2D {
Index L, R;
struct Node {
Seg seg;
Node *l = 0, *r = 0;
Node() {}
};
Node *p = 0;
DynamicSegmentTree2D(Index L, Index R): L(L), R(R) { }
void upd(Seg& seg, Index x, T v) {
auto w = seg.get(x);
w.first += v.first;
w.second += v.second;
seg.set(x, w);
}
public:
void add(Index y, Index x, T v) {
assert(L <= y && y < R);
add(p, L, R, y, x, v);
}
private:
void add(Node*& t, Index a, Index b, Index y, Index x, T v) {
if(!t) t = new Node;
upd(t->seg, x, v);
if(a == y && y + 1 == b) return;
Index mid = (a + b) / 2;
if(y < mid) add(t->l, a, mid, y, x, v);
else add(t->r, mid, b, y, x, v);
}
public:
T fold(Index yl, Index yr, Index xl, Index xr) {
if(yl < L) yl = L;
if(yr > R) yl = R;
if(yl >= yr) return T();
if(xl >= xr) return T();
return fold(p, L, R, yl, yr, xl, xr);
}
private:
T fold(Node* k, Index a, Index b, Index yl, Index yr, Index xl, Index xr) {
if(!k) return T(0, 0);
if(yr <= a || b <= yl) return T(0, 0);
if(yl <= a && b <= yr) return k->seg.fold(xl, xr);
Index mid = (a + b) / 2;
return op(
fold(k->l, a, mid, yl, yr, xl, xr),
fold(k->r, mid, b, yl, yr, xl, xr)
);
}
};
constexpr int Q = 1 << 16;
int n, q;
ll t[Q], l[Q], r[Q];
ll med[Q], smaller[Q], bigger[Q];
using P = pair<ll, ll>;
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0);
cin >> n >> q;
DynamicSegmentTree2D<P> dseg(0, inf);
vector<ll> v(n);
for(auto &e: v) cin >> e;
for(int i = 0; i < q; i++) cin >> t[i] >> l[i] >> r[i];
for(int i = 0; i < n; i++) dseg.add(v[i], i, P(v[i], 1));
ll sum16 = 0;
ll sum40 = 0;
for(int i = 0; i < q; i++) {
if(t[i] == 1) { // update
l[i] ^= sum16;
r[i] ^= sum40;
l[i]--;
dseg.add(v[l[i]], l[i], P(-v[l[i]], -1));
dseg.add(r[i], l[i], P(r[i], 1));
v[l[i]] = r[i];
} else { // query
l[i] ^= sum16;
r[i] ^= sum16;
if(l[i] > r[i]) swap(l[i], r[i]);
l[i]--;
int len = r[i] - l[i];
ll ok = inf - 1, ng = -1;
while(abs(ok - ng) > 1) {
ll mid = (ok + ng) / 2;
auto f1 = dseg.fold(mid + 1, inf, l[i], r[i]);
if(f1.second <= len / 2) ok = mid; else ng = mid;
}
med[i] = ok;
smaller[i] = dseg.fold(0, med[i], l[i], r[i]).second;
bigger[i] = dseg.fold(med[i] + 1, inf, l[i], r[i]).second;
ll z = -dseg.fold(0, med[i], l[i], r[i]).first + dseg.fold(med[i] + 1, inf, l[i], r[i]).first;
z -= ll(len / 2 - smaller[i]) * med[i];
z += ll((len - len / 2) - bigger[i]) * med[i];
if(len % 2 == 0) {
} else {
z -= med[i];
}
sum16 ^= z % Q;
sum40 ^= z % (1ll << 40);
cout << z << "\n";
}
}
return 0;
}