結果
| 問題 | No.3524 二進範囲更新範囲和取得 |
| コンテスト | |
| ユーザー |
👑  binap
|
| 提出日時 | 2025-02-07 11:24:15 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,046 bytes |
| 記録 | |
| コンパイル時間 | 4,789 ms |
| コンパイル使用メモリ | 282,068 KB |
| 実行使用メモリ | 47,392 KB |
| 平均クエリ数 | 1167.69 |
| 最終ジャッジ日時 | 2026-05-01 20:56:39 |
| 合計ジャッジ時間 | 22,542 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 16 WA * 29 |
ソースコード
#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef long double ld;
typedef pair<int, int> P;
template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;}
template <int m> ostream& operator<<(ostream& os, const dynamic_modint<m>& a) {os << a.val(); return os;}
template <int m> istream& operator>>(istream& is, static_modint<m>& a) {long long x; is >> x; a = x; return is;}
template <int m> istream& operator>>(istream& is, dynamic_modint<m>& a) {long long x; is >> x; a = x; return is;}
template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;}
template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;}
template<typename T> ostream& operator<<(ostream& os, const set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename S, auto op, auto e> ostream& operator<<(ostream& os, const atcoder::segtree<S, op, e>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}
template<typename S, auto op, auto e, typename F, auto mapping, auto composition, auto id> ostream& operator<<(ostream& os, const atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}
template<typename T> void chmin(T& a, T b){a = min(a, b);}
template<typename T> void chmax(T& a, T b){a = max(a, b);}
// Square Division
// divide [li, ri)
struct SquareDivision{
int n, D;
vector<int> l, r;
SquareDivision(int n, int D = -1) : n(n), D(D) {}
bool initialized = false;
void init(){
assert(n > 0);
initialized = true;
if(D == -1) D = sqrt(n);
assert(D >= 1 and D <= n);
l.resize(D);
r.resize(D);
l[0] = 0;
int width = n / D;
assert(width > 0);
rep(i, D - 1){
r[i] = l[i] + width;
l[i + 1] = r[i];
}
r[D - 1] = n;
}
tuple<vector<int>, vector<int>, vector<int>> divide(int li, int ri){
vector<int> minor_left;
vector<int> major;
vector<int> minor_right;
int li_major = lower_bound(l.begin(), l.end(), li) - l.begin();
int ri_major = lower_bound(r.begin(), r.end(), ri) - r.begin();
if(li_major >= ri_major){
for(int minor_idx = li; minor_idx < ri; minor_idx++) minor_left.push_back(minor_idx);
}else{
for(int minor_idx = li; minor_idx < l[li_major]; minor_idx++) minor_left.push_back(minor_idx);
for(int major_idx = li_major; major_idx < ri_major; major_idx++) major.push_back(major_idx);
for(int minor_idx = l[ri_major]; minor_idx < ri; minor_idx++) minor_right.push_back(minor_idx);
}
return make_tuple(minor_left, major, minor_right);
}
};
// https://ei1333.github.io/luzhiled/snippets/math/mod-pow.html
template< typename T >
T mod_pow(T x, T n, const T &p) {
T ret = 1;
while(n > 0) {
if(n & 1) (ret *= x) %= p;
(x *= x) %= p;
n >>= 1;
}
return ret;
}
int main(){
int N, B, Q;
cin >> N >> B >> Q;
int D = max((int)sqrt((double)N / B), 1);
SquareDivision sq(N, D);
sq.init();
vector<int> in(N + 1);
vector<int> out(N + 1);
int t = 0;
auto dfs = [&](int from, auto dfs) -> void{
if(from > N) return;
in[from] = t; t++;
dfs(from * 2, dfs);
dfs(from * 2 + 1, dfs);
out[from] = t;
};
dfs(1, dfs);
vector<vector<int>> transfer(D, vector<int>(B));
rep(i, D) rep(j, B) transfer[i][j] = j;
vector<int> belong(N);
rep(i, D){
for(int x = sq.l[i]; x < sq.r[i]; x++) belong[x] = i;
}
vector<int> a(N);
vector<vector<int>> cnt(D, vector<int>(B));
vector<int> sum(D);
for(int x = 1; x <= N; x++){
int idx = in[x];
int i = belong[idx];
a[idx] = x % B;
cnt[i][x % B]++;
sum[i] += x % B;
}
auto change_minor = [&](int idx, int c){
int i = belong[idx];
cnt[i][a[idx]]--;
a[idx] = c;
cnt[i][a[idx]]++;
};
auto change_major = [&](int i, vector<int> transfer_sub){
vector<int> cnt_sub(B);
rep(j, B){
sum[i] -= transfer[i][j] * cnt[i][j];
}
rep(j, B){
transfer[i][j] = transfer[i][transfer_sub[j]];
}
rep(j, B){
sum[i] += transfer[i][j] * cnt[i][j];
}
};
auto evaluate = [&](int i){
for(int idx = sq.l[i]; idx < sq.r[i]; idx++){
change_minor(idx, transfer[i][a[idx]]);
}
rep(j, B) transfer[i][j] = j;
};
rep(_, Q){
int x;
long long d;
cin >> x >> d;
vector<int> transfer_sub(B);
rep(j, B) transfer_sub[j] = (mod_pow<long long>(j, d, B) + 1) % B;
auto [minor_left, major, minor_right] = sq.divide(in[x], out[x]);
/*
cout << "minor_left: " << minor_left;
cout << "major: " << major;
cout << "minor_right: " << minor_right;
cout << "\n";
*/
int ans = 0;
if(minor_left.size()){
int i = belong[minor_left[0]];
evaluate(i);
for(int idx : minor_left){
sum[i] -= a[idx];
change_minor(idx, transfer_sub[a[idx]]);
sum[i] += a[idx];
ans += a[idx];
}
}
for(int i : major){
change_major(i, transfer_sub);
ans += sum[i];
}
if(minor_right.size()){
int i = belong[minor_right[0]];
evaluate(i);
for(int idx : minor_right){
sum[i] -= a[idx];
change_minor(idx, transfer_sub[a[idx]]);
sum[i] += a[idx];
ans += a[idx];
}
}
cout << ans % B << "\n";
}
return 0;
}