結果
| 問題 |
No.925 紲星 Extra
|
| コンテスト | |
| ユーザー |
 ei1333333
|
| 提出日時 | 2019-11-08 23:04:01 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 18,324 bytes |
| コンパイル時間 | 4,060 ms |
| コンパイル使用メモリ | 226,724 KB |
| 最終ジャッジ日時 | 2025-01-08 02:48:21 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 2 TLE * 1 MLE * 16 |
ソースコード
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
using namespace std;
using int64 = long long;
const int mod = 1e9 + 7;
const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
struct IoSetup {
IoSetup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
} iosetup;
template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
os << p.first << " " << p.second;
return os;
}
template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
is >> p.first >> p.second;
return is;
}
template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
for(int i = 0; i < (int) v.size(); i++) {
os << v[i] << (i + 1 != v.size() ? " " : "");
}
return os;
}
template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
for(T &in : v) is >> in;
return is;
}
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
template< typename T = int64 >
vector< T > make_v(size_t a) {
return vector< T >(a);
}
template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}
template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
t = v;
}
template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
for(auto &e : t) fill_v(e, v);
}
template< typename F >
struct FixPoint : F {
FixPoint(F &&f) : F(forward< F >(f)) {}
template< typename... Args >
decltype(auto) operator()(Args &&... args) const {
return F::operator()(*this, forward< Args >(args)...);
}
};
template< typename F >
inline decltype(auto) MFP(F &&f) {
return FixPoint< F >{forward< F >(f)};
}
// かずまさんありがとう
using COL = bool;
const COL RED = false, BLACK = true;
class fid {
struct node {
COL color;
int size;
bool val;
int all;
node *p, *ch[2];
node() : color(BLACK), size(0), val(0), all(0), p(nullptr), ch{nullptr, nullptr} {}
node(COL c, bool v, node *par, node *l, node *r) : color(c), size(1), val(v), all(v), p(par), ch{l, r} {}
} *NIL, *root;
node *new_node(bool val) const {
return new node(RED, val, NIL, NIL, NIL);
}
void update(node *x) {
x->size = x->ch[0]->size + 1 + x->ch[1]->size;
x->all = x->ch[0]->all + x->val + x->ch[1]->all;
}
void update_up(node *x) {
while(x != NIL) update(x), x = x->p;
}
void rotate(node *x, int b) {
node *y = x->ch[1 - b];
x->ch[1 - b] = y->ch[b];
if(y->ch[b] != NIL) {
y->ch[b]->p = x;
}
y->p = x->p;
if(x->p == NIL) {
root = y;
} else {
x->p->ch[x != x->p->ch[0]] = y;
}
y->ch[b] = x;
x->p = y;
update(x);
update(y);
}
void insert_fix(node *x) {
while(x->p->color == RED) {
int b = (x->p != x->p->p->ch[0]);
node *y = x->p->p->ch[1 - b];
if(y->color == RED) {
x->p->color = BLACK;
y->color = BLACK;
x->p->p->color = RED;
x = x->p->p;
continue;
}
if(x == x->p->ch[1 - b]) {
x = x->p;
rotate(x, b);
}
x->p->color = BLACK;
x->p->p->color = RED;
rotate(x->p->p, 1 - b);
}
root->color = BLACK;
}
void transplant(node *u, node *v) {
if(u->p == NIL) {
root = v;
} else {
u->p->ch[u != u->p->ch[0]] = v;
}
v->p = u->p;
}
void erase_fix(node *x) {
while(x != root && x->color == BLACK) {
int b = (x != x->p->ch[0]);
node *w = x->p->ch[1 - b];
if(w->color == RED) {
w->color = BLACK;
x->p->color = RED;
rotate(x->p, b);
w = x->p->ch[1 - b];
}
if(w->ch[b]->color == BLACK && w->ch[1 - b]->color == BLACK) {
w->color = RED;
x = x->p;
continue;
}
if(w->ch[1 - b]->color == BLACK) {
w->ch[b]->color = BLACK;
w->color = RED;
rotate(w, 1 - b);
w = x->p->ch[1 - b];
}
w->color = x->p->color;
x->p->color = BLACK;
w->ch[1 - b]->color = BLACK;
rotate(x->p, b);
x = root;
}
x->color = BLACK;
}
node *find_first(node *x) const {
while(x->ch[0] != NIL) x = x->ch[0];
return x;
}
node *find(node *t, int k) const {
if(k < 0 || t->size <= k) return NIL;
node *x = t;
while(x->ch[0]->size != k) {
if(k < x->ch[0]->size) {
x = x->ch[0];
} else {
k -= x->ch[0]->size + 1;
x = x->ch[1];
}
}
return x;
}
int find(node *t, int l, int r) const {
if(t == NIL || r <= 0 || t->size <= l) return 0;
if(l <= 0 && t->size <= r) return t->all;
int c = t->ch[0]->size;
return find(t->ch[0], l, r) + (l <= c && c < r ? t->val : 0) + find(t->ch[1], l - (c + 1), r - (c + 1));
}
public:
fid() : NIL(new node()), root(NIL) {}
int size() const {
return root->size;
}
void insert(int k, bool b) {
node *y = NIL, *v = new_node(b);
if(root == NIL) {
root = v;
} else if(k == 0) {
y = find_first(root);
y->ch[0] = v;
} else {
y = find(root, k - 1);
if(y->ch[1] == NIL) {
y->ch[1] = v;
} else {
y = find_first(y->ch[1]);
y->ch[0] = v;
}
}
v->p = y;
update_up(y);
insert_fix(v);
}
void erase(int k) {
node *x = find(root, k);
node *y = x, *z;
COL c = y->color;
if(x->ch[0] == NIL) {
z = x->ch[1];
transplant(x, x->ch[1]);
} else if(x->ch[1] == NIL) {
z = x->ch[0];
transplant(x, x->ch[0]);
} else {
y = find_first(x->ch[1]);
c = y->color;
z = y->ch[1];
if(y->p == x) {
z->p = y;
} else {
transplant(y, y->ch[1]);
y->ch[1] = x->ch[1];
y->ch[1]->p = y;
}
transplant(x, y);
y->ch[0] = x->ch[0];
y->ch[0]->p = y;
y->color = x->color;
update(y);
}
update_up(z->p);
if(c == BLACK) erase_fix(z);
}
bool find(int k) const {
return find(root, k)->val;
}
int rank(int k, bool b) const {
return b ? find(root, 0, k) : k - find(root, 0, k);
}
int rank(int l, int r, bool b) const {
return b ? find(root, l, r) : r - l - find(root, l, r);
}
int select(int k, bool b) const {
int res = 0;
node *x = root;
while(true) {
assert(x != NIL);
int c = b ? x->ch[0]->all : x->ch[0]->size - x->ch[0]->all;
if(k == c && x->val == b) return res + x->ch[0]->size;
if(k < c) {
x = x->ch[0];
} else {
k -= c + (x->val == b);
res += x->ch[0]->size + 1;
x = x->ch[1];
}
}
}
int select(int l, int k, bool b) const {
return select(k + rank(l, b), b);
}
};
template< typename T >
class red_black_tree {
struct node {
COL color;
int size;
T val;
node *p, *ch[2];
node() : color(BLACK), size(0), val(), p(nullptr), ch{nullptr, nullptr} {}
node(COL c, T v, node *par, node *l, node *r) : color(c), size(1), val(v), p(par), ch{l, r} {}
} *NIL, *root;
node *new_node(T val) const {
return new node(RED, val, NIL, NIL, NIL);
}
void update(node *x) {
x->size = x->ch[0]->size + 1 + x->ch[1]->size;
}
void update_up(node *x) {
while(x != NIL) update(x), x = x->p;
}
void rotate(node *x, int b) {
node *y = x->ch[1 - b];
x->ch[1 - b] = y->ch[b];
if(y->ch[b] != NIL) {
y->ch[b]->p = x;
}
y->p = x->p;
if(x->p == NIL) {
root = y;
} else {
x->p->ch[x != x->p->ch[0]] = y;
}
y->ch[b] = x;
x->p = y;
update(x);
update(y);
}
void insert_fix(node *x) {
while(x->p->color == RED) {
int b = (x->p != x->p->p->ch[0]);
node *y = x->p->p->ch[1 - b];
if(y->color == RED) {
x->p->color = BLACK;
y->color = BLACK;
x->p->p->color = RED;
x = x->p->p;
continue;
}
if(x == x->p->ch[1 - b]) {
x = x->p;
rotate(x, b);
}
x->p->color = BLACK;
x->p->p->color = RED;
rotate(x->p->p, 1 - b);
}
root->color = BLACK;
}
void transplant(node *u, node *v) {
if(u->p == NIL) {
root = v;
} else {
u->p->ch[u != u->p->ch[0]] = v;
}
v->p = u->p;
}
void erase_fix(node *x) {
while(x != root && x->color == BLACK) {
int b = (x != x->p->ch[0]);
node *w = x->p->ch[1 - b];
if(w->color == RED) {
w->color = BLACK;
x->p->color = RED;
rotate(x->p, b);
w = x->p->ch[1 - b];
}
if(w->ch[b]->color == BLACK && w->ch[1 - b]->color == BLACK) {
w->color = RED;
x = x->p;
continue;
}
if(w->ch[1 - b]->color == BLACK) {
w->ch[b]->color = BLACK;
w->color = RED;
rotate(w, 1 - b);
w = x->p->ch[1 - b];
}
w->color = x->p->color;
x->p->color = BLACK;
w->ch[1 - b]->color = BLACK;
rotate(x->p, b);
x = root;
}
x->color = BLACK;
}
node *find_first(node *x) const {
if(x == NIL) return NIL;
while(x->ch[0] != NIL) x = x->ch[0];
return x;
}
node *find(node *t, int k) const {
if(k < 0 || t->size <= k) return NIL;
node *x = t;
while(x->ch[0]->size != k) {
if(k < x->ch[0]->size) {
x = x->ch[0];
} else {
k -= x->ch[0]->size + 1;
x = x->ch[1];
}
}
return x;
}
public:
red_black_tree() : NIL(new node()), root(NIL) {}
T find(int k) const {
return find(root, k)->val;
}
void update(int k, T val) {
node *t = find(root, k);
t->val = val;
}
void insert(int k, T val) {
node *y = NIL, *v = new_node(val);
if(root == NIL) {
root = v;
} else if(k == 0) {
y = find_first(root);
y->ch[0] = v;
} else {
y = find(root, k - 1);
if(y->ch[1] == NIL) {
y->ch[1] = v;
} else {
y = find_first(y->ch[1]);
y->ch[0] = v;
}
}
v->p = y;
update_up(y);
insert_fix(v);
}
void erase(int k) {
node *x = find(root, k);
node *y = x, *z;
COL c = y->color;
if(x->ch[0] == NIL) {
z = x->ch[1];
transplant(x, x->ch[1]);
} else if(x->ch[1] == NIL) {
z = x->ch[0];
transplant(x, x->ch[0]);
} else {
y = find_first(x->ch[1]);
c = y->color;
z = y->ch[1];
if(y->p == x) {
z->p = y;
} else {
transplant(y, y->ch[1]);
y->ch[1] = x->ch[1];
y->ch[1]->p = y;
}
transplant(x, y);
y->ch[0] = x->ch[0];
y->ch[0]->p = y;
y->color = x->color;
update(y);
}
update_up(z->p);
if(c == BLACK) erase_fix(z);
}
};
template< typename T >
class dynamic_wavelet_matrix {
T h;
red_black_tree< T > all;
vector< fid > data;
vector< int > mid;
public:
dynamic_wavelet_matrix(T h_ = 30) : h(h_), data(h), mid(h) {}
void insert(int k, T val) {
all.insert(k, val);
for(T b = 0; b < h; b++) {
bool d = (val >> (h - 1 - b)) & 1;
data[b].insert(k, d);
if(d) {
k = data[b].rank(k, d) + mid[b];
} else {
k = data[b].rank(k, d);
mid[b]++;
}
}
}
void erase(int k) {
T val = all.find(k);
all.erase(k);
for(T b = 0; b < h; b++) {
bool d = (val >> (h - 1 - b)) & 1;
data[b].erase(k);
if(d) {
k = data[b].rank(k, d) + mid[b];
} else {
k = data[b].rank(k, d);
mid[b]--;
}
}
}
T get(int k) const {
return all.find(k);
}
int rank(int p, T val) {
return rank(0, p, val);
}
int rank(int l, int r, T val) {
if(val >> h) return 0;
for(T b = 0; b < h; b++) {
if(val & ((T) 1 << (h - 1 - b))) {
l = data[b].rank(l, true) + mid[b];
r = data[b].rank(r, true) + mid[b];
} else {
l = data[b].rank(l, false);
r = data[b].rank(r, false);
}
}
return r - l;
}
int rank_less_than(int l, int r, T ub) {
if(ub >> h) return r - l;
int res = 0;
for(T b = 0; b < h; b++) {
bool d = (ub >> (h - 1 - b)) & 1;
int lcnt = data[b].rank(l, d);
int rcnt = data[b].rank(r, d);
if(d) res += (r - l) - (rcnt - lcnt);
l = lcnt;
r = rcnt;
if(d) {
l += mid[b];
r += mid[b];
}
}
return res;
}
int rank_range(int l, int r, T lb, T ub) {
return rank_less_than(l, r, ub) - rank_less_than(l, r, lb);
}
int select(int x, T val) {
static int left[h];
int l = 0, r = data[0].size();
for(T b = 0; b < h; b++) {
left[b] = l;
if(val & ((T) 1 << (h - 1 - b))) {
l = data[b].rank(l, true) + mid[b];
r = data[b].rank(r, true) + mid[b];
} else {
l = data[b].rank(l, false);
r = data[b].rank(r, false);
}
}
for(int b = h - 1; b >= 0; b--) {
x = data[b].select(left[b], x, (bool) ((val >> (h - 1 - b)) & 1)) - left[b];
}
return x;
}
int select(int l, int r, int x, T val) {
return select(x + rank(l, val), val);
}
T kth_element(int l, int r, int k) const {
T res = 0;
for(T b = 0; b < h; b++) {
int cnt = data[b].rank(l, r, false);
res <<= 1;
if(k >= cnt) {
l = data[b].rank(l, true) + mid[b];
r = data[b].rank(r, true) + mid[b];
k -= cnt;
res |= 1;
} else {
l = data[b].rank(l, false);
r = data[b].rank(r, false);
}
}
return res;
}
};
using ll = long long;
struct RMQ {
using type = pair< int64, int64 >;
static type id() { return type(0, 0); }
static type op(const type &l, const type &r) { return type(l.first + r.first, l.second + r.second); }
};
template< typename M >
class node {
using T = typename M::type;
public:
T val;
node< M > *l, *r;
node(T val_) : val(val_), l(nullptr), r(nullptr) {}
};
template< typename M >
class dynamic_segment_tree {
using T = typename M::type;
const ll n;
node< M > *root;
T value(node< M > *t) {
return t ? t->val : M::id();
}
T sub(ll l, ll r, node< M > *n, ll lb, ll ub) {
if(!n || ub <= l || r <= lb) return M::id();
if(l <= lb && ub <= r) return n->val;
ll c = (lb + ub) / 2;
return M::op(sub(l, r, n->l, lb, c), sub(l, r, n->r, c, ub));
}
node< M > *suc(ll p, node< M > *t, ll lb, ll ub, T val) {
if(!t) t = new node< M >(M::id());
if(lb + 1 == ub) {
t->val = val;
return t;
}
ll c = (lb + ub) / 2;
if(p < c) t->l = suc(p, t->l, lb, c, val);
else t->r = suc(p, t->r, c, ub, val);
t->val = M::op(value(t->l), value(t->r));
return t;
}
public:
dynamic_segment_tree(ll n_) :
n(1ll << (ll) ceil(log2(n_))), root(nullptr) {
}
void update(ll p, T val) {
root = suc(p, root, 0, n, val);
}
T find(ll l, ll r) {
return sub(l, r + 1, root, 0, n);
}
};
template< typename M >
class node2 {
using T = typename M::type;
public:
dynamic_segment_tree< M > val;
node2< M > *l, *r;
node2(ll size) : val(size), l(nullptr), r(nullptr) {}
};
template< typename M >
class dynamic_segment_tree2 {
using T = typename M::type;
const ll h, w;
node2< M > *root;
T value(node2< M > *t, ll p) {
return t ? t->val.find(p, p) : M::id();
}
T sub(ll li, ll lj, ll ri, ll rj, node2< M > *n, ll lb, ll ub) {
if(!n || ub <= li || ri <= lb) return M::id();
if(li <= lb && ub <= ri) {
return n->val.find(lj, rj);
}
ll c = (lb + ub) / 2;
return M::op(sub(li, lj, ri, rj, n->l, lb, c), sub(li, lj, ri, rj, n->r, c, ub));
}
node2< M > *suc(ll pi, ll pj, node2< M > *t, ll lb, ll ub, T val) {
if(!t) t = new node2< M >(w);
if(lb + 1 == ub) {
t->val.update(pj, val);
return t;
}
ll c = (lb + ub) / 2;
if(pi < c) t->l = suc(pi, pj, t->l, lb, c, val);
else t->r = suc(pi, pj, t->r, c, ub, val);
t->val.update(pj, M::op(value(t->l, pj), value(t->r, pj)));
return t;
}
public:
dynamic_segment_tree2(ll h_, ll w_) :
h(1ll << (ll) ceil(log2(h_))), w(w_), root(nullptr) {}
void update(ll pi, ll pj, T val) {
root = suc(pi, pj, root, 0, h, val);
}
T find(ll li, ll lj, ll ri, ll rj) {
return sub(li, lj, ri + 1, rj, root, 0, h);
}
};
template< class T >
struct BinaryIndexedTree {
vector< T > data;
BinaryIndexedTree(int sz) {
data.assign(++sz, 0);
}
T sum(int k) {
T ret = 0;
for(++k; k > 0; k -= k & -k) ret += data[k];
return (ret);
}
void add(int k, T x) {
for(++k; k < data.size(); k += k & -k) data[k] += x;
}
};
int main() {
int N, Q;
cin >> N >> Q;
vector< int64 > A(N);
cin >> A;
dynamic_wavelet_matrix< int64 > mat(41);
for(int i = 0; i < N; i++) {
mat.insert(i, A[i]);
}
const int64 two16 = 65536;
const int64 two40 = 1099511627776;
dynamic_segment_tree2< RMQ > seg(N + 1, two40);
for(int i = 0; i < N; i++) {
seg.update(i, A[i], make_pair(A[i], 1));
}
BinaryIndexedTree< int64 > bit(N);
for(int i = 0; i < N; i++) {
bit.add(i, A[i]);
}
int64 s = 0;
for(int i = 0; i < Q; i++) {
int64 t, l, r;
cin >> t >> l >> r;
if(t == 1) {
l ^= s % two16;
r ^= s % two40;
--l;
mat.erase(l);
seg.update(l, A[l], make_pair(0, 0));
bit.add(l, -A[l]);
A[l] = r;
bit.add(l, A[l]);
seg.update(l, A[l], make_pair(A[l], 1));
mat.insert(l, A[l]);
} else {
l ^= s % two16;
r ^= s % two16;
if(l > r) swap(l, r);
--l;
int md = (r - l) / 2;
int64 val = mat.kth_element(l, r, md);
auto ret = seg.find(l, val, r - 1, infll);
int64 upcnt = ret.second;
int64 upsum = ret.first;
int64 lowcnt = (r - l) - upcnt;
int64 lowsum = bit.sum(r - 1) - bit.sum(l - 1) - upsum;
int64 sum = (upsum - upcnt * val) + (val * lowcnt - lowsum);
cout << sum << endl;
s ^= sum;
}
}
}