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

• 問題: No.1891 Static Xor Range Composite Query
• ユーザー: tau1235
• 提出日時: 2026-09-29 22:22:44
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 288 ms / 5,000 ms
• コード長: 3,779 bytes
• コンパイル時間: 2,550 ms
• コンパイル使用メモリ: 347,648 KB
• 実行使用メモリ: 48,512 KB
• 最終ジャッジ日時: 2026-09-29 22:23:08
• 合計ジャッジ時間: 12,501 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_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 XorSegmentTreeStatic{
  int n,log;
  int xorval;
  vector<vector<S>> table;
  XorSegmentTreeStatic(vector<S> v){
    n=v.size();
    log=0;
    while (1<<log<n) log++;
    assert(n==1<<log);
    xorval=0;
    table=vector(log+1,vector<S>(n));
    table[log]=v;
    for (int d=log-1;d>=0;d--) for (int i=0;i<1<<d;i++) update(d,i);
  }
  S get(int p){
    assert(0<=p&&p<n);
    return table[log][p^xorval];
  }
  S prod(int l,int r){
    assert(0<=l&&l<=r&&r<=n);
    return prod(0,n,l,r,0);
  }
  void operate_xor(int x){
    assert(0<=x&&x<n);
    xorval^=x;
  }
private:
  S prod(int l,int r,int ql,int qr,int dep){
    if (qr<=l||r<=ql) return e();
    if (ql<=l&&r<=qr) return table[dep][l^xorval];
    int mid=(l+r)/2;
    return op(prod(l,mid,ql,qr,dep+1),prod(mid,r,ql,qr,dep+1));
  }
  void update(int d,int p){
    int l=p<<(log-d);
    int h=1<<(log-d-1);
    for (int i=0;i<n>>(d+1);i++){
      table[d][l+i]=op(table[d+1][l+i],table[d+1][l+h+i]);
      table[d][l+h+i]=op(table[d+1][l+h+i],table[d+1][l+i]);
    }
  }
};

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);
  for (int i=0;i<n;i++) cin>>v[i].a>>v[i].b;
  XorSegmentTreeStatic<S,op,e> seg(v);
  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";
  }
}