Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- I am Hunting High and Low
- Diving from the sky above
- Looking for, more and more, once again
- I'm Hunting High and Low
- Sometimes I may win, sometimes I'll lose
- It's just a game that I play
- After the storm there's a calm
- Through the clouds shines a ray of the sun
- I'm carried from all my harm
- There is no one I can't outrun
- Now I'm leaving my worries behind
- Feel the freedom of body and mind
- I'm starting my journey, I'm drifting away with the wind, I go___________________:-
- */
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 1e5 + 50;
- #define f(i,a,n) for(int i = a; i < n; i++)
- #define L cout << '\n';
- #define pb(x) push_back(x)
- #define C(x) cout << x << ' '
- #define A(v) v.begin(), v.end()
- #define int long long int
- #define ff first
- #define ss second
- int tree[N << 2 + 5], arr[N];
- void build(int l, int r, int node){
- if(l == r){
- tree[node] = arr[l];
- return;
- }
- int mid = (l + r) / 2;
- build(l, mid, node * 2);
- build(mid + 1, r, (node * 2 )+ 1);
- tree[node] = tree[node * 2] + tree[node * 2 + 1];
- }
- int query(int l, int r, int ql, int qr, int node ){
- if(r < ql || l > qr)return 0LL;
- if(ql <= l and r <= qr)
- return tree[node];
- int mid = (l + r) / 2;
- return query(l, mid, ql, qr, node * 2 + 1) + query(mid + 1, r, ql, qr, node * 2 + 1);
- }
- void update(int l, int r, int val, int pos, int node){
- if(l == r and l == pos){
- tree[node] = val;
- return;
- }
- if(pos < l || pos > r)return;
- int mid = (l + (r - l) / 2);
- update(l, mid, val, pos, 2 * node);
- update(mid + 1, r, val, pos, 2 * node + 1);
- tree[node] = tree[node * 2] + tree[node * 2 + 1];
- }
- signed main(){
- ios_base::sync_with_stdio(0);
- cin.tie(NULL);cout.tie(NULL);
- int n, i, l, r, q;
- cin >> n;
- for(i = 1; i <= n; i++){
- cin >> arr[i];
- }
- build(1, n, 1);
- cin >> q;
- while(q--){
- cin >> l >> r;
- update(1, n, l, r, 1);
- }
- C(query(1, n, 1, 3, 1));L;
- return 0;
- }
Add Comment
Please, Sign In to add comment