Compile Error
foo.cc:2:1: error: 'vector' does not name a type
2 | vector<vector<int>> t(4 * N, vector<int> (32));
| ^~~~~~
foo.cc:10:42: error: 'vector' has not been declared
10 | void build(int node, int st, int en, vector<ll> &arr) { //=> O(N)
| ^~~~~~
foo.cc:10:48: error: expected ',' or '...' before '<' token
10 | void build(int node, int st, int en, vector<ll> &arr) { //=> O(N)
| ^
foo.cc:27:52: error: 'll' has not been declared
27 | void update(int node, int st, int en, int idx, ll val) { //=> O(log n)
| ^~
foo.cc: In member function 'auto Segment_Tree::merge(auto:1&, auto:2&)':
foo.cc:6:9: error: 'vector' was not declared in this scope
6 | vector<int> tmp(32);
| ^~~~~~
foo.cc:6:16: error: expected primary-expression before 'int'
6 | vector<int> tmp(32);
| ^~~
foo.cc:7:37: error: 'tmp' was not declared in this scope
7 | for(int b = 0; b < 32; b++) tmp[b] = l[b] + r[b];
| ^~~
foo.cc:8:16: error: 'tmp' was not declared in this scope
8 | return tmp;
| ^~~
foo.cc: In member function 'void Segment_Tree::build(int, int, int, int)':
foo.cc:13:13: error: 'bitset' was not declared in this scope
13 | bitset<32> b1 = arr[st];
| ^~~~~~
foo.cc:13:24: error: 'b1' was not declared in this scope
13 | bitset<32> b1 = arr[st];
| ^~
foo.cc:13:29: error: 'arr' was not declared in this scope
13 | bitset<32> b1 = arr[st];
| ^~~
foo.cc:14:41: error: 't' was not declared in this scope
14 | for(int b = 0; b < 32; b++) t[node][b] = b1[b];
| ^
foo.cc:18:35: error: 'arr' was not declared in this scope
18 | build(node << 1, st, mid, arr); // divide left side
| ^~~
foo.cc:21:21: error: 't' was not declared in this scope
21 | auto &Cur = t[node];
| ^
foo.cc: In member function 'void Segment_Tree::update(int, int, int, int, int)':
foo.cc:29:13: error: 'bitset' was not declared in this scope
29 | bitset<32> b1 = val;
| ^~~~~~
foo.cc:29:24: error: 'b1' was not declared in this scope
29 | bitset<32> b1 = val;
| ^~
foo.cc:31:20: error: 't' was not declared in this scope
31 | if(t[node][b] == 1 && b1[b] == 0) t[node][b] = 1;
| ^
foo.cc:42:21: error: 't' was not declared in this scope
42 | auto &Cur = t[node];
| ^
foo.cc: In member function 'auto Segment_Tree::query(int, int, int, int, int)':
foo.cc:50:20: error: 'vector' was not declared in this scope
50 | return vector<int> (32, 0); // <== careful
| ^~~~~~
foo.cc:50:27: error: expected primary-expression before 'int'
50 | return vector<int> (32, 0); // <== careful
| ^~~
foo.cc:50:27: error: expected ';' before 'int'
foo.cc:50:30: error: expected unqualified-id before '>' token
50 | return vector<int> (32, 0); // <== careful
| ^
foo.cc:53:20: error: 't' was not declared in this scope
53 | return t[node];
| ^
foo.cc: At global scope:
foo.cc:63:1: error: 'll' does not name a type
63 | ll mod = 1e9 + 7;
| ^~
foo.cc:65:1: error: 'll' does not name a type
65 | ll Pow(ll a, ll b) { // O(log b)
| ^~
foo.cc: In function 'void solve()':
foo.cc:77:5: error: 'll' was not declared in this scope
77 | ll n, q;
| ^~
foo.cc:78:5: error: 'cin' was not declared in this scope
78 | cin >> n >> q;
| ^~~
foo.cc:78:12: error: 'n' was not declared in this scope
78 | cin >> n >> q;
| ^
foo.cc:78:17: error: 'q' was not declared in this scope
78 | cin >> n >> q;
| ^
foo.cc:79:5: error: 'vector' was not declared in this scope
79 | vector<ll> v(n + 1);
| ^~~~~~
foo.cc:79:16: error: 'v' was not declared in this scope
79 | vector<ll> v(n + 1);
| ^
foo.cc:81:11: error: expected ';' before 'x'
81 | ll x; cin >> x;
| ^~
| ;
foo.cc:81:22: error: 'x' was not declared in this scope
81 | ll x; cin >> x;
| ^
foo.cc:98:15: error: expected ';' before 'sum'
98 | ll sum = 0, sz = r - l + 1;
| ^~~~
| ;
foo.cc:100:19: error: expected ';' before 'cnt0'
100 | ll cnt0 = sz - bitCnt[b];
| ^~~~~
| ;
foo.cc:101:19: error: expected ';' before 'cnt1'
101 | ll cnt1 = bitCnt[b];
| ^~~~~
| ;
foo.cc:102:20: error: 'cnt1' was not declared in this scope
102 | if(cnt1 > 0) {
| ^~~~
foo.cc:103:23: error: expected ';' before 'totCom'
103 | ll totCom = (Pow(2, cnt1 - 1) * Pow(2, cnt0)) % mod; // (nC1 + nC3 + ...+ nClastOdd = 2^(n - 1)) * (nC0 + nC1 + ...+nCn = 2^n)
| ^~~~~~~
| ;
foo.cc:104:21: error: 'sum' was not declared in this scope
104 | sum += (totCom * Pow(2, b)) % mod;
| ^~~
foo.cc:104:29: error: 'totCom' was not declared in this scope
104 | sum += (totCom * Pow(2, b)) % mod;
| ^~~~~~
foo.cc:104:38: error: 'Pow' was not declared in this scope
104 | sum += (totCom * Pow(2, b)) % mod;
| ^~~
foo.cc:104:51: error: 'mod' was not declared in this scope
104 | sum += (totCom * Pow(2, b)) % mod;
| ^~~
foo.cc:108:13: error: 'cout' was not declared in this scope
108 | cout << sum << endl;
| ^~~~
foo.cc:108:21: error: 'sum' was not declared in this scope
108 | cout << sum << endl;
| ^~~
foo.cc:108:28: error: 'endl' was not declared in this scope
108 | cout << sum << endl;
| ^~~~
Code
const int N = 2e5 + 9;
vector<vector<int>> t(4 * N, vector<int> (32));
struct Segment_Tree {
auto merge(auto &l, auto &r) { // <== Change this function
vector<int> tmp(32);
for(int b = 0; b < 32; b++) tmp[b] = l[b] + r[b];
return tmp;
}
void build(int node, int st, int en, vector<ll> &arr) { //=> O(N)
if (st == en) {
// t[node] = arr[st];
bitset<32> b1 = arr[st];
for(int b = 0; b < 32; b++) t[node][b] = b1[b];
return;
}
int mid = (st + en) >> 1;
build(node << 1, st, mid, arr); // divide left side
build(node << 1 | 1, mid + 1, en, arr); // divide right side
// Merging left and right portion
auto &Cur = t[node];
auto &Left = t[node << 1];
auto &Right = t[node << 1 | 1];
Cur = merge(Left, Right);
return;
}
void update(int node, int st, int en, int idx, ll val) { //=> O(log n)
if (st == en) {
bitset<32> b1 = val;
for(int b = 0; b < 32; b++) {
if(t[node][b] == 1 && b1[b] == 0) t[node][b] = 1;
else if(t[node][b] == 0 && b1[b] == 1) t[node][b] = 1;
else if(t[node][b] == 1 && b1[b] == 1) t[node][b] = 0;
}
// t[node] = val;
return;
}
int mid = (st + en) >> 1;
if (idx <= mid) update(node << 1, st, mid, idx, val);
else update(node << 1 | 1, mid + 1, en, idx, val);
// Merging left and right portion
auto &Cur = t[node];
auto &Left = t[node << 1];
auto &Right = t[node << 1 | 1];
Cur = merge(Left, Right);
return;
}
auto query(int node, int st, int en, int l, int r) { //=> O(log n)
if (st > r || en < l) { // No overlapping and out of range
return vector<int> (32, 0); // <== careful
}
if (l <= st && en <= r) { // Complete overlapped (l-r in range)
return t[node];
}
// Partial overlapping
int mid = (st + en) >> 1;
auto Left = query(node << 1, st, mid, l, r);
auto Right = query(node << 1 | 1, mid + 1, en, l, r);
return merge(Left, Right);
}
} st1;
ll mod = 1e9 + 7;
ll Pow(ll a, ll b) { // O(log b)
a %= mod;
ll ans = 1;
while (b) {
if (b & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
void solve() {
ll n, q;
cin >> n >> q;
vector<ll> v(n + 1);
for (int i = 1; i <= n; i++) {
ll x; cin >> x;
v[i] = x;
}
st1.build(1, 1, n, v);
short type;
while(q--) {
cin >> type;
if(type == 1) {
int pos, x;
cin >> pos >> x;
st1.update(1, 1, n, pos, x);
}
else {
int l, r;
cin >> l >> r;
auto bitCnt = st1.query(1, 1, n, l, r);
// coutall(bitCnt);
ll sum = 0, sz = r - l + 1;
for(int b = 0; b < 32; b++) {
ll cnt0 = sz - bitCnt[b];
ll cnt1 = bitCnt[b];
if(cnt1 > 0) {
ll totCom = (Pow(2, cnt1 - 1) * Pow(2, cnt0)) % mod; // (nC1 + nC3 + ...+ nClastOdd = 2^(n - 1)) * (nC0 + nC1 + ...+nCn = 2^n)
sum += (totCom * Pow(2, b)) % mod;
sum %= mod;
}
}
cout << sum << endl;
}
}
return;
}
Information
- Submit By
-
_ASRafi__ LV 9
- Type
- Submission
- Problem
- P1183 The Sorcerer’s Subsequence Sum
- Language
- C++17 (G++ 13.2.0)
- Submit At
- 2025-03-21 18:11:28
- Judged At
- 2025-03-21 18:11:28
- Judged By
-
judge
- Score
- 0
- Total Time
- 0ms
- Peak Memory
- 0 Bytes