結果

問題 No.2861 Slime Party
ユーザー dyktr_06
提出日時 2024-05-14 03:46:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 13,406 bytes
コンパイル時間 3,043 ms
コンパイル使用メモリ 225,828 KB
最終ジャッジ日時 2025-02-21 13:58:18
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 20 WA * 56
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
template <typename T>
pair<vector<vector<int>>, int> cartesianTree(vector<T> &a){
int n = a.size();
vector<vector<int>> G(n);
vector<int> par(n, -1), st;
for(int i = 0; i < n; ++i){
int prev = -1;
while(!st.empty() && a[i] > a[st.back()]){
prev = st.back();
st.pop_back();
}
if(prev != -1){
par[prev] = i;
}
if(!st.empty()){
par[i] = st.back();
}
st.emplace_back(i);
}
int root = -1;
for(int i = 0; i < n; ++i){
if(par[i] != -1){
G[par[i]].emplace_back(i);
} else{
root = i;
}
}
return make_pair(G, root);
}
class HeavyLightDecomposition{
protected:
int V;
vector<vector<int>> G;
vector<int> stsize, parent, pathtop, depth, in, reverse_in, out;
int root;
private:
// Subtree Size
void buildStsize(int curr, int prev){
stsize[curr] = 1, parent[curr] = prev;
for(int &v : G[curr]){
if(v == prev){
if(v == G[curr].back()) break;
else swap(v, G[curr].back());
}
buildStsize(v, curr);
stsize[curr] += stsize[v];
if(stsize[v] > stsize[G[curr][0]]){
swap(v, G[curr][0]);
}
}
}
void buildPath(int curr, int prev, int &t){
in[curr] = t++;
reverse_in[in[curr]] = curr;
for(int v : G[curr]){
if(v == prev) continue;
if(v == G[curr][0]){
pathtop[v] = pathtop[curr];
} else{
pathtop[v] = v;
}
depth[v] = depth[curr] + 1;
buildPath(v, curr, t);
}
out[curr] = t;
}
public:
HeavyLightDecomposition(int node_size) : V(node_size), G(V), stsize(V, 0), parent(V, -1),
pathtop(V, -1), depth(V, 0), in(V, -1), reverse_in(V, -1), out(V, -1){}
void add_edge(int u, int v){
G[u].push_back(v);
G[v].push_back(u);
}
void build(int _root = 0){
root = _root;
int t = 0;
buildStsize(root, -1);
pathtop[root] = root;
buildPath(root, -1, t);
}
inline int get(int a){
return in[a];
}
int la(int a, int k) {
while(true){
int u = pathtop[a];
if(in[a] - k >= in[u]) return reverse_in[in[a] - k];
k -= in[a] - in[u] + 1;
a = parent[u];
}
}
int lca(int a, int b){
int pa = pathtop[a], pb = pathtop[b];
while(pathtop[a] != pathtop[b]){
if(in[pa] > in[pb]){
a = parent[pa], pa = pathtop[a];
} else{
b = parent[pb], pb = pathtop[b];
}
}
if(in[a] > in[b]) swap(a, b);
return a;
}
int dist(int a, int b){ return depth[a] + depth[b] - 2 * depth[lca(a, b)]; }
int jump(int from, int to, int k) {
if(!k) return from;
int l = lca(from, to);
int d = dist(from, to);
if(d < k) return -1;
if(depth[from] - depth[l] >= k) return la(from, k);
k -= depth[from] - depth[l];
return la(to, depth[to] - depth[l] - k);
}
void subtree_query(int a, const function<void(int, int)> &func){
func(in[a], out[a]);
}
void path_query(int a, int b, const function<void(int, int)> &func, bool include_root = true, bool reverse_path = false){
vector<pair<int, int>> path;
int pa = pathtop[a], pb = pathtop[b];
while(pathtop[a] != pathtop[b]){
if(in[pa] > in[pb]){
path.emplace_back(in[pa], in[a] + 1);
a = parent[pa], pa = pathtop[a];
} else{
path.emplace_back(in[pb], in[b] + 1);
b = parent[pb], pb = pathtop[b];
}
}
if(in[a] > in[b]) swap(a, b);
if(include_root) path.emplace_back(in[a], in[b] + 1);
else path.emplace_back(in[a] + 1, in[b] + 1);
if(!reverse_path) reverse(path.begin(), path.end());
else for(auto &p : path) p = make_pair(V - p.second, V - p.first);
for(auto [u, v] : path){
func(u, v);
}
}
void path_noncommutative_query(int a, int b, const function<void(int, int)> &func, const function<void(int, int)> &func2){
int l = lca(a, b);
path_query(a, l, func2, false, true);
path_query(l, b, func, true, false);
}
};
template <typename X>
struct SegTree{
using FX = function<X(X, X)>; // X•X -> X
int n;
FX fx;
const X ex;
vector<X> dat;
SegTree(int n_, const FX &fx_, const X &ex_) : n(), fx(fx_), ex(ex_){
int x = 1;
while(n_ > x){
x *= 2;
}
n = x;
dat.assign(n * 2, ex);
}
X get(int i) const {
return dat[i + n];
}
void set(int i, const X &x){ dat[i + n] = x; }
void build(){
for(int k = n - 1; k >= 1; k--) dat[k] = fx(dat[k * 2], dat[k * 2 + 1]);
}
void update(int i, const X &x){
i += n;
dat[i] = x;
while(i > 0){
i >>= 1; // parent
dat[i] = fx(dat[i * 2], dat[i * 2 + 1]);
}
}
X query(int a, int b){
X vl = ex;
X vr = ex;
int l = a + n;
int r = b + n;
while(l < r){
if(l & 1) vl = fx(vl, dat[l++]);
if(r & 1) vr = fx(dat[--r], vr);
l >>= 1;
r >>= 1;
}
return fx(vl, vr);
}
X operator [](int i) const {
return dat[i + n];
}
};
template <class S,
S(*op)(S, S),
S(*e)(),
class F,
S(*mapping)(F, S),
F(*composition)(F, F),
F(*id)()>
struct LazySegTree{
private:
int _n, size, log;
vector<S> d;
vector<F> lz;
void pull(int k){ d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f){
d[k] = mapping(f, d[k]);
if(k < size) lz[k] = composition(f, lz[k]);
}
void push(int k){
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
public:
LazySegTree() : LazySegTree(0){}
LazySegTree(int n) : LazySegTree(vector<S>(n, e())){}
LazySegTree(const vector<S> &v) : _n(int(v.size())){
log = 0;
size = 1;
while(size < _n) size <<= 1, log++;
d = vector<S>(2 * size, e());
lz = vector<F>(size, id());
for(int i = 0; i < _n; i++) d[size + i] = v[i];
for(int i = size - 1; i >= 1; i--){
pull(i);
}
}
void update(int p, S x){
assert(0 <= p && p < _n);
p += size;
for(int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for(int i = 1; i <= log; i++) pull(p >> i);
}
S get(int p){
assert(0 <= p && p < _n);
p += size;
for(int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S query(int l, int r){
assert(0 <= l && l <= r && r <= _n);
if(l == r) return e();
l += size;
r += size;
for(int i = log; i >= 1; i--){
if(((l >> i) << i) != l) push(l >> i);
if(((r >> i) << i) != r) push(r >> i);
}
S sml = e(), smr = e();
while(l < r){
if(l & 1) sml = op(sml, d[l++]);
if(r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_query(){ return d[1]; }
void apply(int p, F f){
assert(0 <= p && p < _n);
p += size;
for(int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for(int i = 1; i <= log; i++) pull(p >> i);
}
void apply(int l, int r, F f){
assert(0 <= l && l <= r && r <= _n);
if(l == r) return;
l += size;
r += size;
for(int i = log; i >= 1; i--){
if(((l >> i) << i) != l) push(l >> i);
if(((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while(l < r){
if(l & 1) all_apply(l++, f);
if(r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for(int i = 1; i <= log; i++){
if(((l >> i) << i) != l) pull(l >> i);
if(((r >> i) << i) != r) pull((r - 1) >> i);
}
}
template <bool (*g)(S)>
int max_right(int l){
return max_right(l, [](S x){ return g(x); });
}
template <class G>
int max_right(int l, G g){
assert(0 <= l && l <= _n);
assert(g(e()));
if(l == _n) return _n;
l += size;
for(int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do{
while(l % 2 == 0) l >>= 1;
if(!g(op(sm, d[l]))){
while(l < size){
push(l);
l = (2 * l);
if(g(op(sm, d[l]))){
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while((l & -l) != l);
return _n;
}
template <bool (*g)(S)>
int min_left(int r){
return min_left(r, [](S x){ return g(x); });
}
template <class G>
int min_left(int r, G g){
assert(0 <= r && r <= _n);
assert(g(e()));
if(r == 0) return 0;
r += size;
for(int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do{
r--;
while(r > 1 && (r % 2)) r >>= 1;
if(!g(op(d[r], sm))){
while(r < size){
push(r);
r = (2 * r + 1);
if(g(op(d[r], sm))){
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while((r & -r) != r);
return 0;
}
};
const long long INF = 1LL << 60;
using S = long long;
using F = long long;
S op(S l, S r){
return min(l, r);
}
S e(){
return INF;
}
S mapping(F f, S x){
return x + f;
}
F composition(F f, F g){
return f + g;
}
F id(){
return 0LL;
}
bool f(S x){
return x > 0;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
long long L;
cin >> n >> q >> L;
vector<long long> a(n), x(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
for(int i = 0; i < n; i++){
cin >> x[i];
}
auto [G, root] = cartesianTree(a);
HeavyLightDecomposition hld(n);
for(int i = 0; i < n; i++){
for(int j : G[i]){
hld.add_edge(i, j);
}
}
hld.build(root);
SegTree<long long> segx(n, [](long long a, long long b){ return a + b; }, 0LL);
for(int i = 0; i < n; i++){
segx.update(hld.get(i), x[i]);
}
LazySegTree<S, op, e, F, mapping, composition, id> seg(n);
vector<int> pidx(n);
{
long long sum = 0;
auto query_sum = [&](int l, int r){
sum += segx.query(l, r);
};
for(int i = 0; i < n; i++){
for(int j : G[i]){
int idx = max(hld.get(i), hld.get(j));
sum = 0;
pidx[j] = i;
hld.subtree_query(j, query_sum);
seg.update(idx, sum + L - a[i]);
}
}
}
while(q--){
int t; cin >> t;
if(t == 1){
int a;
long long b;
cin >> a >> b;
a--;
long long d = b - segx[hld.get(a)];
segx.update(hld.get(a), b);
auto add_query = [&](int l, int r){
seg.apply(l, r, d);
};
hld.path_query(root, a, add_query, false);
}else{
int c;
cin >> c;
c--;
vector<pair<int, int>> path;
auto query_min = [&](int l, int r){
if(l == r){
return;
}
path.emplace_back(l, r);
};
if(L <= min(a[c], a[c + 1])){
cout << L << "\n";
continue;
}
int s = c + 1;
if(a[c] < a[c + 1]) s = c;
hld.path_query(s, root, query_min, false);
reverse(path.begin(), path.end());
int curr = -1;
for(auto [l, r] : path){
if(seg.query(l, r) > 0){
curr = l;
}else{
int x = seg.min_left<f>(r);
if(l <= x && x < r){
curr = x;
}
break;
}
}
long long ans = L;
auto query_sum = [&](int l, int r){
ans += segx.query(l, r);
};
if(curr == -1){
hld.subtree_query(s, query_sum);
}else{
hld.subtree_query(pidx[curr], query_sum);
}
cout << ans << "\n";
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0