rakkoon69's blog

By rakkoon69, history, 2 years ago, In English

Given an array of n integers equal to zero. There are 3 type of queries:

  1. Increase all elements from l to r by 1
  2. Decrease all elements from l to r by 1
  3. Count the number of zeros from l to r

Is there an efficient way to solve this problem in O(N log N), O(N sqrt(N)) or at least O(N log2 N)? Thank you in advance!

I've found a O(N log N) solution which I've implemented in 258E - Little Elephant and Tree, my submission: 226468052 (The STree namespace)

  • Vote: I like it
  • +16
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You could do this with segment tree with lazy propagation, I believe? (https://cp-algorithms.com/data_structures/segment_tree.html#range-updates-lazy-propagation)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a problem link available for the problem?

Marinush

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think I have a solution in NsqrtN. Split the array into Sqrt(N) blocks. Now, every add/subtract query we do will go through at most sqrt(N) complete blocks and 2 non-complete blocks. For each block we store a frequency array of elements, we know the elements won't exceed Q in absolute values (Q is the number of modifications).

    Now for updates: For each complete block, just add 1/-1 to the block depending on the query. For noncomplete blocks change the frequency of the previous a[i] to the new a[i] that is obtained by performing the addition/subtraction.

    Now for queries: For each complete block, we add to the answer the frequency of -sum_of_block. For noncomplete we just check if its value + sum_of_block is 0 or not and add 1 to the answer for the query if it is.

    Marinush

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Actually, I came up with this problem while solving Mars Maps (BOI 2001). And thank you for your answer! And do you have any solution using segment tree?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it
        const int N=150000*3+10;
        #define mid ((l+r)>>1)
        #define ls (x<<1)
        #define rs (x<<1|1)
        int n,m;
        struct node{
            int mi,cnt;
            int ans,ad;
        }t[4*N];
        int a[N],buc[N];
        int st,lim;
        void pushup(int x){
            t[x].mi=min(t[ls].mi,t[rs].mi);
            t[x].cnt=(t[ls].mi==t[x].mi?t[ls].cnt:0)+(t[rs].mi==t[x].mi?t[rs].cnt:0);
            t[x].ans=t[ls].ans+t[rs].ans;
        }
        void tag(int x,int c){
            t[x].mi+=c;
            t[x].ans=(t[x].mi==0)?t[x].cnt:0;
            t[x].ad+=c;
        }
        void pushdown(int x){
            if(t[x].ad){
                tag(ls,t[x].ad);tag(rs,t[x].ad);
                t[x].ad=0;
            }
        }
        void build(int x,int l,int r){
            if(l==r){
                t[x].cnt=1;t[x].ans=1;
                return;
            }
            build(ls,l,mid);
            build(rs,mid+1,r);
            pushup(x);
        }
        void upda(int x,int l,int r,int L,int R,int c){
            if(L<=l&&r<=R){
                tag(x,c);return;
            }
            pushdown(x);
            if(L<=mid) upda(ls,l,mid,L,R,c);
            if(mid<R) upda(rs,mid+1,r,L,R,c);
            pushup(x);
        }
        int query(int x,int l,int r,int L,int R){
            if(L<=l&&r<=R) return t[x].ans;
            pushdown(x);
            if(R<=mid) return query(ls,l,mid,L,R);
            if(mid<L) return query(rs,mid+1,r,L,R);
            return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R);
        }
        void chan(int x,int c){
            int k=x-buc[x]+1-(c>0);
            upda(1,1,lim,k,k,c);
            buc[x]+=c;
        }