#1150679 (C++23) No.3464 Max and Sum on Grid

提出ソース
結果

問題	No.3464 Max and Sum on Grid
コンテスト
ユーザー	hato336
提出日時	2026-02-28 16:24:33
言語	C++23 (gcc 15.2.0 + boost 1.89.0) コンパイル: `g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	AC
実行時間	1,822 ms / 5,000 ms
コード長	9,074 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	4,874 ms
コンパイル使用メモリ	363,152 KB
実行使用メモリ	23,448 KB
最終ジャッジ日時	2026-02-28 16:24:58
合計ジャッジ時間	23,839 ms
ジャッジサーバーID （参考情報）	judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 10
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define ov4(a, b, c, d, name, ...) name
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for(ll i = (a)-1; i >= (b); i--)
#define fore(e, v) for(auto&& e : v)
#define all(a) begin(a), end(a)
#define si(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template<typename T, typename S> bool chmin(T& a, const S& b) { return a > b ? a = b, 1 : 0; }
template<typename T, typename S> bool chmax(T& a, const S& b) { return a < b ? a = b, 1 : 0; }

const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;

#define i128 __int128_t

#define U uint32_t
#define L uint64_t
struct bit_vector {
   static constexpr U w = 64;
   vector<L> block;
   vector<U> count;
   int n, zeros;

   inline U get(U i) const { return U(block[i / w] >> (i % w)) & 1; }
   inline void set(U i) { block[i / w] |= 1LL << (i % w); }

   bit_vector() {}
   bit_vector(int n) { init(n); }
   void init(int _n) {
      n = zeros = _n;
      block.resize(n / w + 1, 0);
      count.resize(si(block), 0);
   }

   void build() {
      rep(i, 1, si(block)) count[i] = count[i - 1] + popcount(block[i - 1]);
      zeros = rank0(n);
   }

   inline U rank0(U i) const { return i - rank1(i); }
   inline U rank1(U i) const { return count[i / w] + popcount(block[i / w] & ((1ULL << i % w) - 1)); }
};

template<typename T, const int lg = 31> struct WaveletMatrix {
   int n;
   vector<T> a;
   array<bit_vector, lg> bv;
   WaveletMatrix(const vector<T>& _a) : n(_a.size()), a(_a) { build2(); }

   void build() {
      rep(i, lg) bv[i] = bit_vector(n);
      vector<T> cur = a, nxt(n);
      per(h, lg, 0) {
         rep(i, n) if(cur[i] >> h & 1) bv[h].set(i);
         bv[h].build();
         array<decltype(begin(nxt)), 2> it{begin(nxt), begin(nxt) + bv[h].zeros};
         rep(i, n) * it[bv[h].get(i)]++ = cur[i];
         swap(cur, nxt);
      }
      return;
   }

   inline pair<U, U> succ0(int l, int r, int h) const { return make_pair(bv[h].rank0(l), bv[h].rank0(r)); }

   inline pair<U, U> succ1(int l, int r, int h) const {
      U l0 = bv[h].rank0(l);
      U r0 = bv[h].rank0(r);
      U zeros = bv[h].zeros;
      return make_pair(l + zeros - l0, r + zeros - r0);
   }

   T access(U k) const {
      T ret = 0;
      per(h, lg, 0) {
         U f = bv[h].get(k);
         ret |= f ? T(1) << h : 0;
         k = f ? bv[h].rank1(k) + bv[h].zeros : bv[h].rank0(k);
      }
      return ret;
   }

   T kth_smallest(U l, U r, U k) const {
      T res = 0;
      for(int h = lg - 1; h >= 0; --h) {
         U l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
         if(k < r0 - l0) l = l0, r = r0;
         else {
            k -= r0 - l0;
            res |= (T)1 << h;
            l += bv[h].zeros - l0, r += bv[h].zeros - r0;
         }
      }
      return res;
   }
   T kth_largest(int l, int r, int k) { return kth_smallest(l, r, r - l - k - 1); }

   int range_freq(int l, int r, T upper) {
      if(upper >= (T(1) << lg)) return r - l;
      int ret = 0;
      per(h, lg, 0) {
         bool f = (upper >> h) & 1;
         U l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
         if(f) {
            ret += r0 - l0;
            l += bv[h].zeros - l0;
            r += bv[h].zeros - r0;
         } else {
            l = l0;
            r = r0;
         }
      }
      return ret;
   }
   int range_freq(int l, int r, T lower, T upper) { return range_freq(l, r, upper) - range_freq(l, r, lower); }

   array<vector<ll>, lg> sums;
   vector<ll> acc;
   void build2() {
      rep(i, lg) bv[i] = bit_vector(n), sums[i].assign(n + 1, 0);
      acc.resize(si(a) + 1);
      vector<T> cur = a, nxt(n);
      per(h, lg, 0) {
         rep(i, n) if((cur[i] >> h) & 1) bv[h].set(i);
         bv[h].build();
         array<decltype(begin(nxt)), 2> it{begin(nxt), begin(nxt) + bv[h].zeros};
         rep(i, n) * it[bv[h].get(i)]++ = cur[i];
         swap(cur, nxt);
         rep(i, n) sums[h][i + 1] = sums[h][i] + cur[i];
      }
      rep(i, n) acc[i + 1] = acc[i] + a[i];
   }

   ll bottom_k_sum(int l, int r, int k) {
      ll res = 0;
      per(h, lg, 0) {
         U l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
         if(k < r0 - l0) {
            l = l0, r = r0;
         } else {
            res += sums[h][r0] - sums[h][l0];
            k -= r0 - l0;
            l += bv[h].zeros - l0;
            r += bv[h].zeros - r0;
         }
      }
      res += sums[0][l + k] - sums[0][l];
      return res;
   }

   ll top_k_sum(int l, int r, int k) { return acc[r] - acc[l] - bottom_k_sum(l, r, r - l - k); }
};
#undef U
#undef L
struct Mo {
   int n;
   int l = -1, r = -1;
   vector<pii> lr;
   Mo(int n) : n(n) {}
   void add(int l, int r) { lr.eb(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 q = (int)lr.size();
      int bs = n / min<int>(n, sqrt(q));
      vector<int> ord(q);
      iota(all(ord), 0);
      sort(all(ord), [&](int a, int b) {
         int ab = lr[a].first / bs, bb = lr[b].first / bs;
         if(ab != bb) return ab < bb;
         return (ab & 1) ? lr[a].second > lr[b].second : lr[a].second < lr[b].second;
      });
      
      for(auto idx : ord) {
        //cerr << lr[idx].first << ' ' << lr[idx].second << endl;
        //cerr << l << ' ' << r << endl;
         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);
   }
};


int main() { 
    cin.tie(0)->sync_with_stdio(0);


    ll n,q;
    cin >> n >> q;
    vl a(n),b(n);
    rep(i,n){
        cin >> a[i];
    }
    rep(i,n){
        cin >> b[i];
    }
    WaveletMatrix<ll> wa(a),wb(b);


    vector<pll> v;
    rep(i,q){
        ll idx = i;
        ll l,d,r,u;
        cin >> l >> d >> r >> u;
        l--;d--;r--;u--;
        if(l-1 >= 0 && d-1 >= 0){

            v.push_back({(l-1) * n + d-1,idx});
        }
        //mo.add(l-1,d-1);

        v.push_back({r * n + u,idx});
        //mo.add(r,u);
        if(l-1 >= 0){

            v.push_back({(l-1)*n+u,~idx});
        }
        //mo.add(l-1,u);
        if(d-1 >= 0){

            v.push_back({r*n+d-1,~idx});
        }
    }
    sort(v.rbegin(), v.rend());
    vl ans(q);
    ll temp = 0;
    vl pre(n,0);
    rep(i,n){
        vl dp(n,0);
        rep(j,n){
            dp[j] = max(a[i],b[j]);
            if(j >= 1){
                dp[j] += dp[j-1];
            }
        }
        rep(j,n){
            dp[j] += pre[j];
            while(!v.empty() && v.back().first == (i * n + j)){
                ll t = 1;
                ll idx = v.back().second;
                v.pop_back();
                if(idx < 0){
                    idx = ~idx;
                    t = -1;
                }
                ans[idx] += dp[j] * t;
                //cerr << i << ' ' << j << ' ' << dp[j] <<endl;

            }

        }
        swap(pre,dp);
    }
    rep(i,q){
        cout << ans[i] << '\n';
    }
    return 0;
    /*
    auto add_left = [&](ll idx){
        //cerr << l << ' ' << r << ' ' << idx << ' ' <<  temp << endl;
        ll x = a[idx];
        ll right = mo.r + 1;
        ll cnt = wb.range_freq(0,right,x);
        temp += x * cnt;
        temp += wb.top_k_sum(0,right,right-cnt);

    };
    auto del_left = [&](ll idx){
        //cerr << l << ' ' << r << ' ' << idx << ' ' <<  temp << endl;
        ll x = a[idx];
        ll right = mo.r + 1;
        ll cnt = wb.range_freq(0,right,x);
        temp -= x * cnt;
        temp -= wb.top_k_sum(0,right,right-cnt);

    };
    auto add_right = [&](ll idx){
        //cerr << l << ' ' << r << ' ' << idx << ' ' <<  temp << endl;
        ll x = b[idx];
        ll right = mo.l + 1;
        ll cnt = wa.range_freq(0,right,x);
        temp += x * cnt;
        temp += wa.top_k_sum(0,right,right-cnt);

    };
    auto del_right = [&](ll idx){
        //cerr << l << ' ' << r << ' ' << idx << ' ' <<  temp << endl;
        ll x = b[idx];
        ll right = mo.l + 1;
        ll cnt = wa.range_freq(0,right,x);
        temp -= x * cnt;
        temp -= wa.top_k_sum(0,right,right-cnt);

    };
    auto out = [&](ll idx){
        //cerr << l << ' ' << r << ' ' << idx << ' ' <<  temp << endl;
        ll i = idx / 4;
        ll j = idx % 4;
        ans[i] += temp * (j < 2 ? 1 : -1);
    };
    mo.build(add_left,add_right,del_left,del_right,out);
    rep(i,q){
        cout << ans[i] << '\n';
    }
    */



}
yukicoder

結果

ソースコード
