Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define all(x) (x).begin(),(x).end()
- using namespace std;
- const int MSIZE = 1e5;
- const int CAP = 64;
- int arr[MSIZE];
- int add[(MSIZE + CAP - 1) / CAP];
- map<int, int> gr[(MSIZE + CAP - 1) / CAP];
- int n;
- void Add(int l, int r, int val) {
- if (l / CAP == r / CAP) {
- for (int i = l; i <= r; i++) {
- auto it = gr[i / CAP].find(arr[i]);
- it->second--;
- if (it->second == 0) {
- gr[i / CAP].erase(it);
- }
- arr[i] += val;
- gr[i / CAP][arr[i]]++;
- }
- return;
- }
- for (int i = l; i / CAP == l / CAP && i < n; i++) {
- auto it = gr[i / CAP].find(arr[i]);
- it->second--;
- if (it->second == 0) {
- gr[i / CAP].erase(it);
- }
- arr[i] += val;
- gr[i / CAP][arr[i]]++;
- }
- for (int i = r; i / CAP == r / CAP && i >= 0; i--) {
- auto it = gr[i / CAP].find(arr[i]);
- it->second--;
- if (it->second == 0) {
- gr[i / CAP].erase(it);
- }
- arr[i] += val;
- gr[i / CAP][arr[i]]++;
- }
- for (int i = l / CAP + 1; i < r / CAP; i++) {
- add[i] += val;
- }
- }
- bool Contains(int l, int r, int val) {
- if (l / CAP == r / CAP) {
- for (int i = l; i <= r; i++) {
- if (arr[i] + add[i / CAP] == val) {
- return true;
- }
- }
- return false;
- }
- for (int i = l; i / CAP == l / CAP && i < n; i++) {
- if (arr[i] + add[i / CAP] == val) {
- return true;
- }
- }
- for (int i = r; i / CAP == r / CAP && i >= 0; i--) {
- if (arr[i] + add[i / CAP] == val) {
- return true;
- }
- }
- for (int i = l / CAP + 1; i < r / CAP; i++) {
- auto it = gr[i].find(val - add[i]);
- if (it != gr[i].end()) {
- if (it->second > 0) {
- return true;
- }
- }
- }
- return false;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int q;
- cin >> n >> q;
- for (int i = 0; i < n; i++) {
- cin >> arr[i];
- gr[i / CAP][arr[i]]++;
- }
- while (q--) {
- char t;
- int l, r, val;
- cin >> t >> l >> r >> val;
- l--, r--;
- if (t == '+') {
- Add(l, r, val);
- } else {
- cout << (Contains(l, r, val) ? "YES\n" : "NO\n");
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement