#1159229 (C++23) No.3506 All Distance is Square Number

• 問題: No.3506 All Distance is Square Number
• ユーザー: はじっこゆーれー
• 提出日時: 2026-04-18 06:37:16
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 3,373 bytes
• コンパイル時間: 1,371 ms
• コンパイル使用メモリ: 192,536 KB
• 実行使用メモリ: 7,976 KB
• 最終ジャッジ日時: 2026-04-18 06:37:19
• 合計ジャッジ時間: 2,779 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
other	WA * 29

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct Node {
    long long sum;
    long long max_v;
    long long min_v;
    long long lazy;
};
vector<Node> tree;
long long integer_sqrt(long long x) {
    long long res = sqrt(x);
    while ((res + 1) * (res + 1) <= x) res++;
    while (res * res > x) res--;
    return res;
}
void apply_assign(int node, int l, int r, long long x) {
    tree[node].sum = x * (r - l);
    tree[node].max_v = x;
    tree[node].min_v = x;
    tree[node].lazy = x;
}
void push(int node, int l, int r) {
    if (tree[node].lazy != -1) {
        int mid = l + (r - l) / 2;
        apply_assign(node * 2, l, mid, tree[node].lazy);
        apply_assign(node * 2 + 1, mid, r, tree[node].lazy);
        tree[node].lazy = -1;
    }
}
void pull(int node) {
    tree[node].sum = tree[node * 2].sum + tree[node * 2 + 1].sum;
    tree[node].max_v = max(tree[node * 2].max_v, tree[node * 2 + 1].max_v);
    tree[node].min_v = min(tree[node * 2].min_v, tree[node * 2 + 1].min_v);
}
void build(int node, int l, int r, const vector<long long>& A) {
    tree[node].lazy = -1;
    if (l + 1 == r) {
        tree[node].sum = A[l];
        tree[node].max_v = A[l];
        tree[node].min_v = A[l];
        return;
    }
    int mid = l + (r - l) / 2;
    build(node * 2, l, mid, A);
    build(node * 2 + 1, mid, r, A);
    pull(node);
}
void update_assign(int node, int l, int r, int ql, int qr, long long x) {
    if (ql >= r || qr <= l) return;
    if (ql <= l && r <= qr) {
        apply_assign(node, l, r, x);
        return;
    }
    push(node, l, r);
    int mid = l + (r - l) / 2;
    update_assign(node * 2, l, mid, ql, qr, x);
    update_assign(node * 2 + 1, mid, r, ql, qr, x);
    pull(node);
}
void update_sqrt(int node, int l, int r, int ql, int qr) {
    if (ql >= r || qr <= l) return;
    if (ql <= l && r <= qr) {
        if (tree[node].max_v == tree[node].min_v) {
            long long v = integer_sqrt(tree[node].max_v);
            apply_assign(node, l, r, v);
            return;
        }
    }
    push(node, l, r);
    int mid = l + (r - l) / 2;
    update_sqrt(node * 2, l, mid, ql, qr);
    update_sqrt(node * 2 + 1, mid, r, ql, qr);
    pull(node);
}
long long query_sum(int node, int l, int r, int ql, int qr) {
    if (ql >= r || qr <= l) return 0;
    if (ql <= l && r <= qr) return tree[node].sum;
    push(node, l, r);
    int mid = l + (r - l) / 2;
    return query_sum(node * 2, l, mid, ql, qr) + query_sum(node * 2 + 1, mid, r, ql, qr);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, Q;
    if (!(cin >> N >> Q)) return 0;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    tree.resize(4 * N);
    build(1, 0, N, A);
    for (int i = 0; i < Q; ++i) {
        int type;
        cin >> type;
        if (type == 0) {
            int l, r;
            cin >> l >> r;
            if (l == r) cout << 0 << "\n";
            else cout << query_sum(1, 0, N, l, r) << "\n";
        } else if (type == 1) {
            int l, r;
            long long x;
            cin >> l >> r >> x;
            if (l < r) update_assign(1, 0, N, l, r, x);
        } else if (type == 2) {
            int l, r;
            cin >> l >> r;
            if (l < r) update_sqrt(1, 0, N, l, r);
        }
    }
    return 0;
}