提出 #35558963

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define SEG_ROOT 1,0,n-1
#define SEG_L (o<<1)
#define SEG_R (o<<1|1)
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid+1,r
int read(){int r;scanf("%d",&r);return r;}

const int N=200000;
const int INF=0x3f3f3f3f; // > 998244353
int seg[4*N+10]; // 叶子:min, 非叶子INF表示非区间lazy
int b[N+10];

int build(int o,int l,int r,int v){
  if(l==r)return seg[o]=v;
  build(SEG_L_CHILD,v);
  build(SEG_R_CHILD,v);
  return seg[o]=INF;
}
void setv(int o,int v){seg[o]=min(seg[o],v);}
void down(int o){
  if(seg[o]!=INF){
    setv(SEG_L,seg[o]);
    setv(SEG_R,seg[o]);
    seg[o]=INF;
  }
}
void update(int o,int l,int r,int ql,int qr,int v){
  if(ql<=l&&r<=qr) return setv(o,v);
  down(o);
  if(ql<=mid) update(SEG_L_CHILD,ql,qr,v);
  if(qr> mid) update(SEG_R_CHILD,ql,qr,v);
}

void toB(int o,int l,int r){
  if(l==r){
    b[l]=seg[o];
    return ;
  }
  down(o);
  toB(SEG_L_CHILD);
  toB(SEG_R_CHILD);
}

template <class T>
int lowb(const vector<T>& v, const T& x) {return lower_bound(begin(v), end(v), x)-begin(v);}

int main() {
  int n=read();
  int m=read();
  int Q=read();

  unordered_map<int,vector<pair<int,int>> > query; // query[value] = { {l,r} }
  build(SEG_ROOT,m);
  while(Q--){
    int l=read()-1;
    int r=read()-1;
    int x=read();
    update(SEG_ROOT,l,r,x);
    query[x].push_back({l,r});
  }
  toB(SEG_ROOT); // 计算每个A[i]的上界B[i]

  unordered_map<int,vector<int> > index; // index[value] = {index in A}
  index[m]={}; // 在没有x是m但是有些不被限制时
  rep(i,0,n) index[b[i]].push_back(i);

  mint ans = 1;
  for(auto &[x,list]:index){ // 下标 列表
    int sz=size(list);
    if(query[x].empty()) { // 没有存在性要求, 只会发生在 值为M的时候, 而个数为0, 用下面的算会是0 * 0^0=0
      if(sz) ans*=mint(x+1).pow(sz);
      continue;
    }

    int first = sz;
    vector<int> left(sz+1); // left[R] = list[max(L) ... R-1] 之间需要存在一个, 会出现不合法的情况left[R]=R, 但这种会让 sum = 0, 从而后续dp[i], sum 都为0 , 能正确处理
    for(auto [l,r]: query[x]) {
      int s = lowb(list, l);
      int t = lowb(list, r+1); // list[s,t-1] 之间需要存在一个x
      first = min(first, t);
      left[t] = max(left[t], s);
    }

    mint invx = mint(x).inv(); // x非0, 少做除法
    vector<mint> dp(sz);
    mint sum = 0; // sum 记录没有乘倍数的"原始"值 = sum(dp[j..i-1])
    int j=0;
    rep(i,0,sz){
      dp[i]=sum*invx + (i<first?invx:0); // i放x, dp[i][i]=sum dp[i-1][...] + (无限制前缀?x^i:0)
      sum +=dp[i];
      for(;j<left[i+1];j++) sum -= dp[j];
    }
    ans *= sum*mint(x).pow(sz);
  }
  printf("%d\n",ans.val());
  return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘int read()’:
./Main.cpp:12:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   12 | int read(){int r;scanf("%d",&r);return r;}
      |                  ~~~~~^~~~~~~~~

ジャッジ結果