結果

問題 No.3581 分数対称差更新区間計数取得
コンテスト
ユーザー tau1235
提出日時 2026-07-03 22:18:17
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 6,965 ms / 10,000 ms
コード長 781 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,364 ms
コンパイル使用メモリ 339,012 KB
実行使用メモリ 15,488 KB
最終ジャッジ日時 2026-07-03 22:19:51
合計ジャッジ時間 58,412 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

int op(int a,int b){return a+b;}
int e(){return 0;}

template< typename T >
vector< pair< pair< T, T >, T > > quotient_range(T N) {
  T M;
  vector< pair< pair< T, T >, T > > ret;
  for(M = 1; M * M <= N; M++) {
    ret.emplace_back(make_pair(M, M), N / M);
  }
  for(T i = M; i >= 1; i--) {
    T L = N / (i + 1) + 1;
    T R = N / i;
    if(L <= R && ret.back().first.second < L) ret.emplace_back(make_pair(L, R), N / L);
  }
  return ret;
}

int main(){
  int m=1e6+10;
  int q;
  cin>>q;
  atcoder::segtree<int,op,e> seg(m);
  while (q--){
    int i,l,r;
    cin>>i>>l>>r;
    r++;
    auto vec=quotient_range(i);
    for (auto [ignore,x]:vec) seg.set(x,seg.get(x)^1);
    cout<<seg.prod(l,r)<<endl;
  }
}
0