#1177596 (C++23(gcc16)) No.3671 Reusable Lazy Segment Tree

• 問題: No.3671 Reusable Lazy Segment Tree
• ユーザー: harurun
• 提出日時: 2026-08-19 10:15:32
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 12,518 bytes
• コンパイル時間: 3,131 ms
• コンパイル使用メモリ: 369,216 KB
• 実行使用メモリ: 73,996 KB
• 最終ジャッジ日時: 2026-09-04 22:29:13
• 合計ジャッジ時間: 27,202 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 14 TLE * 1 -- * 4

ソースコード

#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1

#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder

#endif  // ATCODER_INTERNAL_BITOP_HPP

#ifndef ATCODER_LAZYSEGTREE_HPP
#define ATCODER_LAZYSEGTREE_HPP 1

#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>

#include "atcoder/internal_bit"

namespace atcoder {

#if __cplusplus >= 201703L

template <class S,
          auto op,
          auto e,
          class F,
          auto mapping,
          auto composition,
          auto id>
struct lazy_segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");
    static_assert(
        std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
        "mapping must work as S(F, S)");
    static_assert(
        std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
        "composition must work as F(F, F)");
    static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
                  "id must work as F()");

#else

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {

#endif

  public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        used_d = std::vector<bool>(2*size);
        used_lz = std::vector<bool>(size);
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
        fill(used_d.begin(),used_d.end(),false);
        history_d.clear();
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        assign_d(p, x);
        for (int i = 1; i <= log; i++) update(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 prod(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 - 1) >> 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_prod() { 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);
        assign_d(p, mapping(f, d[p]));
        for (int i = 1; i <= log; i++) update(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) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    void reset(){
        for(auto [k,val]:history_d){
            used_d[k]=false;
            d[k]=val;
        }
        for(auto k:history_lz){
            used_lz[k]=false;
            lz[k]=id();
        }
        history_d.clear();
        history_lz.clear();
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;
    std::vector<bool> used_d, used_lz;
    std::vector<std::pair<int,S>> history_d;
    std::vector<int> history_lz;

    void update(int k) { 
        assign_d(k, op(d[2 * k], d[2 * k + 1])); 
    }
    void all_apply(int k, F f) {
        assign_d(k, mapping(f, d[k]));
        if (k < size) assign_lz(k, composition(f, lz[k]));
    }
    void push(int k) {
        if(lz[k]==id()){
            return;
        }
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        assign_lz(k, id());
    }

    void assign_d(int k, const S& val){
        if(!used_d[k]){
            used_d[k]=true;
            history_d.push_back({k,d[k]});
        }
        d[k] = val;
    }

    void assign_lz(int k, const F& val){
        if(val!=id() && !used_lz[k]){
            used_lz[k]=true;
            history_lz.push_back(k);
        }
        lz[k]=val;
    }


};

}  // namespace atcoder

#endif  // ATCODER_LAZYSEGTREE_HPP


#ifndef CPPLIB_SRC_STRUCTURE_IO_FASTIO_HPP_INCLUDED
#define CPPLIB_SRC_STRUCTURE_IO_FASTIO_HPP_INCLUDED

#include <limits>
#include <stdio.h>

#define read_size 1000000
#define write_size 1000000

struct fastio {
private:
  char read_data[read_size];
  int read_pos = 0;
  int read_len = 0;

  char write_data[write_size];
  int write_pos = 0;

  int getch() {
    if (read_pos == read_len) {
      read_len = fread(read_data, 1, read_size, stdin);
      read_pos = 0;
      if (read_len == 0) return EOF;
    }
    return read_data[read_pos++];
  }

  void ungetch() {
    if (read_pos > 0) read_pos--;
  }

  void readspeoln() {
    int c;
    while (true) {
      c = getch();
      if (c == EOF) return;
      if (c != ' ' && c != '\n' && c != '\r' && c != '\t') {
        ungetch();
        return;
      }
    }
  }

  void flush() {
    if (write_pos != 0) {
      fwrite(write_data, 1, write_pos, stdout);
      write_pos = 0;
    }
  }

public:
  fastio() {}

  ~fastio() {
    flush();
  }

  void readint(int &x) {
    readspeoln();

    int c = getch();
    bool negative = false;
    unsigned int value = 0;

    if (c == '-') {
      negative = true;
      c = getch();
    }

    while ('0' <= c && c <= '9') {
      value = value * 10U + static_cast<unsigned int>(c & 15);
      c = getch();
    }

    if (c != EOF) ungetch();

    if (negative && value == static_cast<unsigned int>(
        std::numeric_limits<int>::max()) + 1U) {
      x = std::numeric_limits<int>::min();
    } else {
      x = negative ? -static_cast<int>(value) : static_cast<int>(value);
    }
  }

  void readll(long long &x) {
    readspeoln();

    int c = getch();
    bool negative = false;
    unsigned long long value = 0;

    if (c == '-') {
      negative = true;
      c = getch();
    }

    while ('0' <= c && c <= '9') {
      value = value * 10ULL + static_cast<unsigned long long>(c & 15);
      c = getch();
    }

    if (c != EOF) ungetch();

    if (negative && value == static_cast<unsigned long long>(
        std::numeric_limits<long long>::max()) + 1ULL) {
      x = std::numeric_limits<long long>::min();
    } else {
      x = negative ? -static_cast<long long>(value) : static_cast<long long>(value);
    }
  }

  // [a, z]
  void readstr(char *s) {
    readspeoln();

    int c = getch();
    
    while (c != EOF && c != ' ' && c != '\n' && c != '\r' && c != '\t') {
      *s++ = (char)c;
      c = getch();
    }

    if (c != EOF) ungetch();

    *s = '\0';
  }

  void write(char c) {
    if (write_pos == write_size) flush();
    write_data[write_pos++] = c;
  }

  void write(const char *s) {
    while (*s) write(*s++);
  }

  void writeint(int x) {
    if (x == 0) {
      write('0');
      return;
    }

    unsigned int value;
    if (x < 0) {
      write('-');
      value = 0U - static_cast<unsigned int>(x);
    } else {
      value = static_cast<unsigned int>(x);
    }

    char s[20];
    int n = 0;

    while (value > 0) {
      s[n++] = char('0' + value % 10U);
      value /= 10U;
    }

    while (n--) write(s[n]);
  }

  void writell(long long x) {
    if (x == 0) {
      write('0');
      return;
    }

    unsigned long long value;
    if (x < 0) {
      write('-');
      value = 0ULL - static_cast<unsigned long long>(x);
    } else {
      value = static_cast<unsigned long long>(x);
    }

    char s[30];
    int n = 0;

    while (value > 0) {
      s[n++] = char('0' + value % 10ULL);
      value /= 10ULL;
    }

    while (n--) write(s[n]);
  }
};

#endif  // CPPLIB_SRC_STRUCTURE_IO_FASTIO_HPP_INCLUDED

#include <bits/stdc++.h>
using namespace std;

const int mask=(1<<30)-1;

// 0の数, 1の数
using S=array<pair<int,int>, 30>;

S op(S a, S b){
    for(int i=0;i<30;i++){
        a[i].first+=b[i].first;
        a[i].second+=b[i].second;
    }
    return a;
}

S e(){
    return S{};
}

using F = array<int,30>;

S mapping(F f, S x){
    for(int i=0;i<30;i++){
        if(f[i] == 1){
            // AND 0
            x[i].first+=x[i].second;
            x[i].second=0;
        }else if(f[i] == 2){
            // OR 1
            x[i].second+=x[i].first;
            x[i].first=0;
        }
    }
    return x;
}

F composition(F f, F g){
    for(int i=0;i<30;i++){
        if(f[i]==1){
            g[i]=1;
        }else if(f[i]==2){
            g[i]=2;
        }
    }
    return g;
}

F id(){
    return F{};
}


int A[100010],l[100010],r[100010],x[100010],L[100010],R[100010];

int main(){
    fastio io;
    int N, M;
    io.readint(N);
    io.readint(M);
    vector<S> AA(N);
    for(int i=0;i<N;i++){
        io.readint(A[i]);
        for(int j=0;j<30;j++){
            if((A[i]>>j)&1){
                AA[i][j].second=1;
            }else{
                AA[i][j].first=1;
            }
        }
    }
    for(int i=0;i<M;i++){
        io.readint(l[i]);
    }
    for(int i=0;i<M;i++){
        io.readint(r[i]);
    }
    for(int i=0;i<M;i++){
        io.readint(x[i]);
    }
    for(int i=0;i<M;i++){
        io.readint(L[i]);
    }
    for(int i=0;i<M;i++){
        io.readint(R[i]);
    }
    atcoder::lazy_segtree<S,op,e,F,mapping,composition,id> seg(AA);
    int Q;
    io.readint(Q);
    for(int i=0;i<Q;i++){
        int s,q;
        io.readint(s);
        io.readint(q);
        int y=i+1;
        for(int j=1;j<=q;j++){
            int z=(s+j)%M;
            int u=min(N, max(1, l[z]^y));
            int v=min(N, max(1, r[z]^y));
            int U=min(N, max(1, L[z]^y));
            int V=min(N, max(1, R[z]^y));
            int ld=min(u,v)-1;
            int rd=max(u,v);
            int Ld=min(U,V)-1;
            int Rd=max(U,V);
            int X=x[z]^y;
            if((z+1)%2==0){
                F f{};
                for(int k=0;k<30;k++){
                    if((X>>k)&1){
                        f[k]=2;
                    }
                }
                seg.apply(ld, rd, f);
            }else{
                F f{};
                for(int k=0;k<30;k++){
                    if(((X>>k)&1)==0){
                        f[k]=1;
                    }
                }
                seg.apply(ld, rd, f);
            }
            S res=seg.prod(Ld, Rd);
            y=0;
            for(int k=0;k<30;k++){
                y+=((1LL<<k)*(long long)res[k].second)&mask;
                y&=mask;
            }
        }
        io.writeint(y);
        io.write('\n');
        seg.reset();
    }
}