Created
February 11, 2022 10:21
-
-
Save shrubb/8c445021c6fd2c499b3f5a79c99bab24 to your computer and use it in GitHub Desktop.
Competitive programming template
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
#include <cstdlib> | |
#include <iostream> | |
#include <algorithm> | |
#include <vector> | |
#include <map> | |
#include <set> | |
#include <queue> | |
#include <cstring> | |
#include <cmath> | |
#include <utility> | |
#include <time.h> | |
#include <stack> | |
using namespace std; | |
#define ll long long | |
#define pr(v) cout << #v << " = " << v << "\n"; | |
int leftBinSearch(vector<int> & arr, int val) { | |
int left = 0, right = arr.size(); | |
// инвариант: | |
// arr[>=r] >= val | |
// arr[< l] < val | |
// поэтому когда left = right, left == левая граница | |
while (right != left) { | |
int mid = (left + right) / 2; | |
if (arr[mid] < val) { | |
left = mid + 1; | |
} else { | |
right = mid; | |
} | |
} | |
if (left == arr.size() or arr[left] != val) { | |
return -1; | |
} else { | |
return left; | |
} | |
} | |
int rightBinSearch(vector<int> & arr, int val) { | |
int left = -1, right = arr.size() - 1; | |
// инвариант: | |
// arr[> r] > val | |
// arr[<=l] <= val | |
// поэтому когда left = right, left == правая граница | |
while (right != left) { | |
int mid = (left + right + 1) / 2; | |
if (arr[mid] > val) { | |
right = mid - 1; | |
} else { | |
left = mid; | |
} | |
} | |
if (left == -1 or arr[left] != val) { | |
return -1; | |
} else { | |
return left; | |
} | |
} | |
// дерево отрезков для суммы | |
// https://informatics.msk.ru/mod/statements/view.php?chapterid=1364 | |
template <typename T> | |
class SegmentTree { | |
private: | |
// в arr[0] хранится "сумма" на всём отрезке | |
vector<T> arr; | |
vector<T> difference; | |
unsigned originIndex; | |
unsigned queryL, queryR; | |
T updateValue; | |
void push(unsigned node, unsigned left, unsigned right) { | |
difference[2 * node + 1] += difference[node]; | |
difference[2 * node + 2] += difference[node]; | |
difference[node] = 0; | |
} | |
T _query(unsigned node, unsigned left, unsigned right) { | |
if (left > queryR or right < queryL) { | |
return 0; | |
} | |
if (left >= queryL and right <= queryR) { | |
return arr[node] + (right - left + 1) * difference[node]; | |
} | |
push(node, left, right); | |
unsigned leftSonLeft = left, leftSonRight = left + (right - left) / 2; | |
unsigned rightSonLeft = leftSonRight + 1, rightSonRight = right; | |
T returnValue = | |
_query(2 * node + 1, leftSonLeft, leftSonRight) + | |
_query(2 * node + 2, rightSonLeft, rightSonRight); | |
arr[node] = arr[2 * node + 1] + difference[2 * node + 1] * (leftSonRight - leftSonLeft + 1) + | |
arr[2 * node + 2] + difference[2 * node + 2] * (rightSonRight - rightSonLeft + 1); | |
return returnValue; | |
} | |
void _update(unsigned node, unsigned left, unsigned right) { | |
if (left > queryR or right < queryL) { | |
return; | |
} | |
if (left >= queryL and right <= queryR) { | |
difference[node] += updateValue; | |
return; | |
} | |
push(node, left, right); | |
unsigned leftSonLeft = left, leftSonRight = left + (right - left) / 2; | |
unsigned rightSonLeft = leftSonRight + 1, rightSonRight = right; | |
_update(2 * node + 1, leftSonLeft, leftSonRight); | |
_update(2 * node + 2, rightSonLeft, rightSonRight); | |
arr[node] = arr[2 * node + 1] + difference[2 * node + 1] * (leftSonRight - leftSonLeft + 1) + | |
arr[2 * node + 2] + difference[2 * node + 2] * (rightSonRight - rightSonLeft + 1); | |
} | |
public: | |
SegmentTree(unsigned n) { | |
unsigned newSize = 1; | |
while (newSize < n) { | |
newSize *= 2; | |
} | |
newSize *= 2; | |
arr.resize(newSize); | |
difference.resize(newSize); | |
originIndex = (newSize / 2) - 1; | |
} | |
SegmentTree(vector<T> & origin): SegmentTree(origin.size()) { | |
std::copy(origin.begin(), origin.end(), arr.begin() + originIndex); | |
for (int i = originIndex - 1; i >= 0; --i) { | |
arr[i] = arr[2 * i + 1] + arr[2 * i + 2]; | |
} | |
} | |
T query(unsigned left, unsigned right) { | |
queryL = left; | |
queryR = right; | |
return _query(0, 0, originIndex); | |
} | |
void update(unsigned left, unsigned right, T value) { | |
queryL = left; | |
queryR = right; | |
updateValue = value; | |
_update(0, 0, originIndex); | |
} | |
}; | |
int main() | |
{ | |
//freopen("input.txt", "r", stdin); | |
//freopen("output.txt", "w", stdout); | |
ios_base::sync_with_stdio(false); | |
int n,m; | |
cin >> n >> m; | |
SegmentTree<int> tree(n+1); | |
for (int i = 0; i < m; ++i) { | |
int cmd; | |
cin >> cmd; | |
if (cmd == 1) { | |
int l,r,s; | |
cin >> l >> r >> s; | |
tree.update(l, r-1, s); | |
} else { | |
int l,r; | |
cin >> l >> r; | |
cout << tree.query(l, r-1) << endl; | |
} | |
} | |
//cout.precision(10); | |
//cout << fixed; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment