#1190780 (C++23) No.1891 Static Xor Range Composite Query

• 問題: No.1891 Static Xor Range Composite Query
• ユーザー: tau1235
• 提出日時: 2026-09-30 01:49:16
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1,359 ms / 5,000 ms
• コード長: 4,122 bytes
• コンパイル時間: 2,518 ms
• コンパイル使用メモリ: 351,892 KB
• 実行使用メモリ: 30,080 KB
• 最終ジャッジ日時: 2026-09-30 01:49:42
• 合計ジャッジ時間: 24,429 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 30

ソースコード

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


struct FastIO{
  FastIO(){
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);
  }
} fastio;

template<int mod> struct modint{
  int x;
  modint():x(0){}
  modint(long long x_){
    x_%=mod;
    if (x_<0) x_+=mod;
    x=(int)x_;
  }
  static modint raw(int x_){
    modint ret;
    ret.x=x_;
    return ret;
  }
  int val()const{return x;}
  modint& operator+=(const modint &r){
    x+=r.x;
    if (x>=mod) x-=mod;
    return *this;
  }
  modint& operator-=(const modint &r){
    x-=r.x;
    if (x<0) x+=mod;
    return *this;
  }
  modint& operator*=(const modint &r){
    x=(int)((long long)x*r.x%mod);
    return *this;
  }
  modint& operator/=(const modint &r){return *this*=r.inv();}
  friend modint operator+(const modint &l,const modint &r){return modint(l)+=r;}
  friend modint operator-(const modint &l,const modint &r){return modint(l)-=r;}
  friend modint operator*(const modint &l,const modint &r){return modint(l)*=r;}
  friend modint operator/(const modint &l,const modint &r){return modint(l)/=r;}
  modint operator+()const{return *this;}
  modint operator-()const{return modint()-*this;}
  modint& operator++(){
    if (++x==mod) x=0;
    return *this;
  }
  modint& operator--(){
    if (x--==0) x=mod-1;
    return *this;
  }
  modint operator++(int){
    modint ret=*this;
    if (++x==mod) x=0;
    return ret;
  }
  modint operator--(int){
    modint ret=*this;
    if (x--==0) x=mod-1;
    return ret;
  } 
  friend bool operator==(const modint &l,const modint &r){return l.x==r.x;}
  friend bool operator!=(const modint &l,const modint &r){return l.x!=r.x;}
  modint inv()const{
    int a=mod,b=x,u=0,v=1;
    while (b){
      int q=a/b;
      swap(a-=q*b,b);
      swap(u-=q*v,v);
    }
    if (u<0) u+=mod;
    return modint::raw(u);
  }
  modint pow(unsigned long long k)const{
    modint ret=1,pw=*this;
    while (k){
      if (k&1) ret*=pw;
      pw*=pw;
      k>>=1;
    }
    return ret;
  }
  friend istream &operator>>(istream &is,modint &p){
    long long x;
    is>>x;
    p=modint(x);
    return is;
  }
  friend ostream &operator<<(ostream &os,const modint &p){return os<<p.x;}
};
using modint998244353=modint<998244353>;
using modint1000000007=modint<1000000007>;

template<typename S,S (*op)(S,S),S (*e)()>
struct XorSegmentTreeNonCommutative{
  int n,log;
  int m;
  int xorval;
  vector<vector<S>> table;
  XorSegmentTreeNonCommutative(int n){
    *this=XorSegmentTreeNonCommutative(vector<S>(n,e()));
  }
  XorSegmentTreeNonCommutative(vector<S> v){
    n=v.size();
    log=0;
    while (1<<log<n) log++;
    assert(n==1<<log);
    m=log/2;
    xorval=0;
    table=vector(m+1,vector<S>(n));
    table[0]=v;
    for (int h=1;h<=m;h++) for (int i=0;i<n>>h;i++) update(h,i);
  }
  void set(int p,S x){
    assert(0<=p&&p<n);
    p^=xorval;
    table[0][p]=x;
    for (int h=1;h<=m;h++){
      p/=2;
      update(h,p);
    }
  }
  S get(int p){
    assert(0<=p&&p<n);
    return table[0][p^xorval];
  }
  S prod(int l,int r){
    assert(0<=l&&l<=r&&r<=n);
    return prod(0,n,l,r,log);
  }
  void operate_xor(int x){
    assert(0<=x&&x<n);
    xorval^=x;
  }
private:
  void update(int h,int p){
    assert(1<=h&&h<=m);
    assert(0<=p&&p<n);
    int l=p<<h;
    int hl=1<<(h-1);
    for (int i=0;i<1<<(h-1);i++){
      table[h][l+i]=op(table[h-1][l+i],table[h-1][l+hl+i]);
      table[h][l+hl+i]=op(table[h-1][l+hl+i],table[h-1][l+i]);
    }
  }
  S prod(int l,int r,int ql,int qr,int h){
    if (qr<=l||r<=ql) return e();
    if (ql<=l&&r<=qr&&h<=m) return table[h][l^xorval];
    int mid=(l+r)/2;
    return op(prod(l,mid,ql,qr,h-1),prod(mid,r,ql,qr,h-1));
  }
};

using mint=modint998244353;
struct S{mint a,b;};
S op(S a,S b){return S{a.a*b.a,b.a*a.b+b.b};}
S e(){return S{1,0};}

int main(){
  int n,q;
  cin>>n>>q;
  vector<S> v(n);
  XorSegmentTreeNonCommutative<S,op,e> seg(n);
  for (int i=0;i<n;i++) cin>>v[i].a>>v[i].b,seg.set(i,v[i]);
  while (q--){
    int l,r,p,x;
    cin>>l>>r>>p>>x;
    seg.operate_xor(p);
    S ret=seg.prod(l,r);
    seg.operate_xor(p);
    mint ans=ret.a*x+ret.b;
    cout<<ans<<"\n";
  }
}