#1041114 (C++17) No.3524 二進範囲更新範囲和取得

提出ソース

結果

問題	No.3524 二進範囲更新範囲和取得
コンテスト
ユーザー	👑 binap
提出日時	2025-02-06 17:34:51
言語	C++17 (gcc 15.2.0 + boost 1.89.0) コンパイル: `g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	MLE (最新) AC (最初)
実行時間	-
コード長	6,912 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	4,914 ms
コンパイル使用メモリ	284,132 KB
実行使用メモリ	709,824 KB
平均クエリ数	367.69
最終ジャッジ日時	2026-05-01 20:56:06
合計ジャッジ時間	44,981 ms
ジャッジサーバーID （参考情報）	judge2_0 / judge3_0

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
other	AC * 21 MLE * 24

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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);}

// 18:25 Start
// monoid?
// f(x, d) = x^d + 1
// f(x, d) + f(y, d) is not descriptable by x + y
// f(f(x, d1), d2) is not descriptable by f(x, g(d1, d2))
// 19:25 cnt_ix = #{j \in S_i| a_j = x (mod B)} ?
// 19:30 O(Q^2) is ok <- ?
// 19:39
// case I: #S_i < sqrt(N) naive
// case II: #S_i > sqrt(N) memoize
// 19:59 O(Q^2B) simply process cnt_ix 
// 20:00 break

// 20:36 Start Implementation O(Q^2B)　-> ng
// 21:00 break

// 17:00 Restart
// O(Q^2B) or less
// algorithm is just like dfs
// on query t
// y = 1, 2 or 3, 4 or , ... , x
// dfs_in: evaluating latest updates until t
// dfs_out: evaluating t-th update

// 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;
	vector<vector<int>> cnt_init(n + 1, vector<int>(b));
	
	auto f = [&](int x, int y, auto f){
		if(y > n) return;
		cnt_init[x][y % b]++;
		f(x, y * 2, f);
		f(x, y * 2 + 1, f);
	};
	
	for(int x = 1; x <= n; x++){
		f(x, x, f);
	}
	
	vector<vector<int>> cnt(n + 1, vector<int>(b));
	vector<int> Q;
	vector<vector<int>> transfer(q, vector<int>(b));
	
	rep(iq, q){
		int i;
		long long d;
		cin >> i >> d;
		
		Q.push_back(i);
		
		rep(x, b){
			transfir[iq][x] = (pow_mod(x, d, b) + 1) % b;
		}
		
		rep(jq, iq){
		}
	}
	
	return 0;
}

*/

/*
int main(){
	int n, b, q;
	cin >> n >> b >> q;
	vector<int> last_update(n + 1, -1);
	
	int r = sqrt(n);
	vector<vector<int>> cnt(r + 1, vector<int>(b));
	
	for(int x = 1; x <= r; x++){
		queue<int> qu;
		qu.push(x);
		while(qu.size()){
			auto y = qu.front(); qu.pop();
			if(y > n) continue;
			cnt[x][y % b]++;
			qu.push(2 * y);
			qu.push(2 * y + 1);
		}
	}
	
	auto is_ancestor = [&](int a, int b){
		
	};
	
	vector<pair<int, long long>> Q(q, {-1, -1LL});
	
	rep(t, q){
		int i;
		long long d;
		cin >> i >> d;
		
		if(i <= r){
			Q[t] = {i, d};
			
		}else{
			
		}
	}
	
	
	return 0;
}

*/

/*
int main(){
	int n, b, q;
	cin >> n >> b >> q;
	
	vector<vector<int>> cnt(n + 1, vector<int>(b));
	
	for(int x = 1; x <= n; x++){
		queue<int> qu;
		qu.push(x);
		while(qu.size()){
			auto y = qu.front(); qu.pop();
			if(y > n) continue;
			cnt[x][y % b]++;
			qu.push(2 * y);
			qu.push(2 * y + 1);
		}
	}
	
	vector<vector<int>> memo(n + 1);
	vector<pair<int>> Q(q);
	vector<vector<int>> transfer(q, vector<int>(b));
	
		// y \in S_x
		auto in = [&](int y, int x){
			while(y >= x){
				if(y == x) return true;
				y /= x;
			}
			return false;
		};
	
	rep(t1, q){
		int x;
		long long d;
		cin >> x >> d;
		memo[x].push_back(t);
		Q[t1] = x;
		
		rep(x, b){
			transfer[t1][x] = pow_mod<long long>(x, d, b) + 1;
		}
		
		
		
		for(int t2 = 0; t2 <= t1; t2++){
			int y = Q[t2];
			
			// y \in S_x and x != y
			if(in(y, x) and x != y){
				rep(i, b) cnt_sub[i] -= cnt[y][i];
				rep(i, b) cnt_sub[i] += cnt[y][i] * transfer[t2][];
			}
			
			// x \in S_y
			if(in(x, y)){
				rep(i, b) transfer_sub[i] = transfer[t2][transfer_sub[i]];
			}
		}
		
	}
	
	
	return 0;
}
*/

int main(){
	int n, b, q;
	cin >> n >> b >> q;
	
	vector<vector<int>> cnt(n + 1, vector<int>(b));
	
	for(int x = 1; x <= n; x++){
		queue<int> qu;
		qu.push(x);
		while(qu.size()){
			auto y = qu.front(); qu.pop();
			if(y > n) continue;
			cnt[x][y % b]++;
			qu.push(2 * y);
			qu.push(2 * y + 1);
		}
	}
	
	vector<int> last_update(n + 1, -1);
	vector<vector<int>> memo(n + 1);
	vector<vector<int>> transfer(q, vector<int>(b));
	
	auto calc = [&](int x){
		int res = 0;
		rep(i, b) res += cnt[x][i] * i;
		return res % b;
	};
	
	rep(t1, q){
		int x;
		long long d;
		cin >> x >> d;
		
		rep(i, b){
			transfer[t1][i] = (mod_pow<long long>(i, d, b) + 1) % b;
		}
		
		vector<int> route;
		{
			int y = x;
			while(y > 0){
				route.push_back(y);
				y /= 2;
			}
			reverse(route.begin(), route.end());
		}
		
		vector<int> updates;
		for(int y : route){
			for(int t2 : memo[y]) updates.push_back(t2);
			sort(updates.begin(), updates.end());
			
			for(int t2 : updates){
				if(t2 > last_update[y]){
					vector<int> tmp(b);
					rep(i, b) tmp[transfer[t2][i]] += cnt[y][i];
					swap(cnt[y], tmp);
				}
			}
			last_update[y] = t1;
		}
		
		vector<int> delta(b);
		{
			rep(i, b) delta[i] -= cnt[x][i];
			vector<int> tmp(b);
			rep(i, b) tmp[transfer[t1][i]] += cnt[x][i];
			rep(i, b) delta[i] += tmp[i];
		}
		
		for(int y : route){
			rep(i, b) cnt[y][i] += delta[i];
		}
		
//		cout << cnt;
		
		int ans = calc(x);
		cout << ans << "\n";
		
		memo[x].push_back(t1);
	}
//	cout << transfer;
	
	
	return 0;
}

yukicoder

結果

ソースコード