Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <math.h>
- using namespace std;
- struct sqrt_dec {
- vector <int> elements;
- int min, max, sum;
- };
- int n, k;
- vector <int> a;
- vector <sqrt_dec> arr;
- void reading() {
- cin >> n;
- a.resize(n);
- for (int i = 0; i < n; i++)
- cin >> a[i];
- }
- void building() {
- int len = ceil(sqrt(n));
- arr.resize(len);
- int cnt = 0;
- for (int i = 0; i < n; i++) {
- if (i != 0 && i % len == 0)
- cnt++;
- arr[cnt].elements.push_back(a[i]);
- }
- for (int i = 0; i < arr.size(); i++) {
- arr[i].sum = 0;
- arr[i].max = 0;
- arr[i].min = 1000000000;
- for (int j = 0; j < arr[i].elements.size(); j++) {
- arr[i].sum += arr[i].elements[j];
- arr[i].max = max(arr[i].max, arr[i].elements[j]);
- arr[i].min = min(arr[i].min, arr[i].elements[j]);
- }
- }
- }
- void writing() {
- for (int i = 0; i < arr.size(); i++) {
- cout << "sum = " << arr[i].sum << "; max = " << arr[i].max << "; elements: ";
- for (int j = 0; j < arr[i].elements.size(); j++)
- cout << arr[i].elements[j] << " ";
- cout << endl;
- }
- }
- int max_query(int l, int r) {
- int request_answer = 0, cur_pos = 0, cnt = 0;
- while (cnt < arr.size() && cur_pos + arr[cnt].elements.size() <= l) {
- cur_pos += arr[cnt].elements.size();
- cnt++;
- }
- if (cur_pos + arr[cnt].elements.size() <= r) {
- for (int i = l - cur_pos; i < arr[cnt].elements.size(); i++)
- request_answer = max(request_answer, arr[cnt].elements[i]);
- cur_pos += arr[cnt].elements.size();
- cnt++;
- while (cnt < arr.size() && cur_pos + arr[cnt].elements.size() <= r) {
- request_answer = max(request_answer, arr[cnt].max);
- cur_pos += arr[cnt].elements.size();
- cnt++;
- }
- for (int i = 0; i <= r - cur_pos; i++)
- request_answer = max(request_answer, arr[cnt].elements[i]);
- return request_answer;
- }
- for (int i = l - cur_pos; i <= r - cur_pos; i++) {
- request_answer = max(request_answer, arr[cnt].elements[i]);
- }
- return request_answer;
- }
- int sum_query(int l, int r) {
- int request_answer = 0, cur_pos = 0, cnt = 0;
- while (cnt <= arr.size() && cur_pos + arr[cnt].elements.size() <= l) {
- cur_pos += arr[cnt].elements.size();
- cnt++;
- }
- if (cur_pos + arr[cnt].elements.size() <= r) {
- for (int i = l - cur_pos - 1; i < arr[cnt].elements.size(); i++)
- request_answer += arr[cnt].elements[i];
- cur_pos += arr[cnt].elements.size();
- cnt++;
- while (cnt < arr.size() && cur_pos + arr[cnt].elements.size() <= r) {
- request_answer += arr[cnt].sum;
- cur_pos += arr[cnt].elements.size();
- cnt++;
- }
- for (int i = 0; i <= r - cur_pos; i++)
- request_answer += arr[cnt].elements[i];
- return request_answer;
- }
- for (int i = l - cur_pos; i <= r - cur_pos; i++) {
- request_answer += arr[cnt].elements[i];
- }
- return request_answer;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement