提出 #35558599

---

ソースコード 拡げる

#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 m;

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();
  m=read();
  int Q=read();
  vector<array<int,3> >lrx;
  rep(i,0,Q)lrx.push_back({read()-1,read()-1,read()});

  vector<int> vals = {m}; // 离散化: [离散化value] = value
  for(auto [l,r,x]:lrx)vals.push_back(x);
  sort(begin(vals), end(vals));
  vals.resize(unique(begin(vals), end(vals))-begin(vals));
  int K = size(vals); // 不同的x的个数

  build(SEG_ROOT,lowb(vals,m));
  vector<vector<pair<int,int>>> query(K); // query[离散化value] = { {l,r} }
  for(auto [l,r,x]:lrx){
    int k = lowb(vals,x); // binary search: value=>离散化value
    update(SEG_ROOT,l,r,k);
    query[k].push_back({l,r});
  }
  toB(SEG_ROOT);

  vector<vector<int> > index(K); // index[离散化value] = {index in A}
  rep(i,0,n) {
    assert(b[i] >= 0);
    assert(b[i] <K);
    index[b[i]].push_back(i);
  }

  mint ans = 1;
  rep(k,0,K){ // 枚举离散的x
    auto&list=index[k]; // 下标 列表
    int sz=size(list);
    mint x=vals[k]; // 值x
    if(query[k].empty()) { // 没有存在性要求, 只会发生在 值为M的时候, 而个数为0, 用下面的算会是0 * 0^0=0
      if(sz)ans*=(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[k]) {
      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 = x.inv(); // x非0
    vector<mint> dp(sz); // 记录没有乘倍数的"原始"值
    mint sum = 0; // sum 记录没有乘倍数的"原始"值 = sum(dp[依赖区间])
    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*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;}
      |                  ~~~~~^~~~~~~~~

ジャッジ結果