rakkoon69's blog

A weird segment tree problem
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

Comments Comments (9)
| 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)

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

Is there a problem link available for the problem?

Marinush

→ Reply
  • »
    »
    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

    → Reply
    • »
      »
      »
      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?

      → Reply
      • »
        »
        »
        »
        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;
}
        → Reply