DeWitt's blog

By DeWitt, 4 years ago, translation, In English

A few days ago, I was solving a contest, where I found a problem, that I couldn't solve there.

You have got an array, size of N <  = 105, and you are recieving up to M<=10^5 queries of the three types:

1 l r d -- increase every element at the segment [l;r] by t, i.e. X +  = t

2 l r -- square root every element at the segment and round all of them down, X = [sqrt(X)]

3 l r -- get the sum at the segment

I tried several approaches, but none worked. If someone has some good idea, give me a clue.

p.s. messing around with the CF post editor :(

Edit: Sorry, forgot to mention: each X <  = 105

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

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

Auto comment: topic has been translated by DeWitt (original revision, translated revision, compare)

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Could you share the problem link?

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I found almost the same problem in hdoj.

http://acm.split.hdu.edu.cn/showproblem.php?pid=5828

However,the author's solution can't pass all tests after data enhancement.I found most accepted solution before data enhancement used this way:

1.build a segtree to store the sum,maximum and minimum value in an interval.

2.increase and get sum operation equals to normal segtree operations.

3.In an interval,if maximum value equals to the minimum value,the sqrt operation only covers interval by the same value.

4.If sqrt(maximum)-sqrt(minimum)==1 ,the sqrt operation equals to subtraction operation.

5.If sqrt(maximum)-sqrt(minimum)==0 ,the sqrt operation equals to interval cover.

6.else just recursion down.Due to the number of times need to get a number sqrted to 1 is small,the efficient is not too slow.

Here is one of the code passed before data enhancement.

/*****************************************************/

#include <cassert>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

//#define mid (l + r) >> 1 
#define ls (t << 1)
#define rs ((t<<1) | 1)

#define N 100050

using namespace std;

typedef long long LL;

struct Tree{ LL max,min,sum,siz; }tr[4*N];
LL A[N],tag[4*N],tag2[4*N];
LL n,m;
LL ans = 0LL;

inline void read(LL &x) {
    static char c;
    while(!isdigit(c = getchar()));
    x = c - '0';
    while( isdigit(c = getchar()))
        x = x * 10 + (c - '0');
}

void out(LL a) {
    if(a > 9) out(a / 10);
    putchar(a % 10 + '0');
}

inline Tree merge(Tree p1,Tree p2,int t) {
    Tree tmp;
    if (tag2[ls] == tag2[rs] && tag2[ls] != -1) {
    	tag2[t] = tag2[ls];
    	tag[t] = 0;
    } else tag2[t] = -1;
    tmp.max = max( p1.max , p2.max );
    tmp.min = min( p1.min , p2.min );
    tmp.sum = p1.sum + p2.sum;
    tmp.siz = p1.siz + p2.siz;
    return tmp;
}

void build(int l,int r,int t) {
    tag[t] = 0;
    if (l == r) {
        tr[t].max = tr[t].min = A[l];
        tr[t].sum = 1LL * A[l];
        tr[t].siz = 1;
        tag2[t] = A[l];
        return ;
    }
    tag2[t] = -1;
    int mid = (l + r) >> 1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    tr[t] = merge(tr[ls],tr[rs],t);
}

inline void color(int t,LL v) {
    tr[t].max += v;
    tr[t].min += v;
    tr[t].sum += 1LL * tr[t].siz * v;
    return ;
} 

inline void color2(int t,LL v) {
    tr[t].max = v;
    tr[t].min = v;
    tr[t].sum = 1LL * tr[t].siz * v;
    return ;
}

inline void push_down(int t) {
    if (tag[t] == 0  && tag2[t] == -1) return ;
    assert(!(tag[t] != 0 && tag2[t] != -1));
    if (tag2[t] != -1) {
        tag[ls] = tag[rs] = 0LL;
        tag2[ls] = tag2[t];
            color2(ls,tag2[t]);
        
        tag2[rs] = tag2[t];
            color2(rs,tag2[t]);
    } else {
        if (tag2[ls] != -1) 
            tag2[ls] += tag[t]; 
        else 
            tag[ls] += tag[t];
        color(ls,tag[t]);

        if (tag2[rs] != -1) 
            tag2[rs] += tag[t];
        else
            tag[rs] += tag[t];
        color(rs,tag[t]);
    }
    tag2[t] = -1; tag[t] = 0;
    return ;
}

LL ll,rr; LL v;
void update_sqrt(int l,int r,int t) {
    //assert(l <= rr && r >= ll);
    //if (l > rr || r < ll) return ;
    if (l >= ll && r <= rr) {
        if (tag2[t] != -1) {
            tag2[t] = 1LL * sqrt( tag2[t] );
            tr[t].max = tr[t].min = tag2[t];
            tr[t].sum = tr[t].siz * tag2[t];
            return ;
        }
        LL p1 = sqrt( tr[t].max );
        LL p2 = sqrt( tr[t].min );
        if (tr[t].max - tr[t].min == 1) {
            if (p1 - p2 == 1) {
                LL v = p1 - tr[t].max;
                tag[t] += v;
                color(t,v);
            } else {
                LL v = p1;
                tag[t] = 0;
                tag2[t] = v;
                color2(t,v);
            }
            return ;
        }
    }
    push_down(t);
    int mid = (l + r) >> 1;
    if (ll <= mid) update_sqrt(l,mid,ls);
    if (rr > mid) update_sqrt(mid+1,r,rs);
    tr[t] = merge(tr[ls],tr[rs],t);
}

void update_add(int l,int r,int t) {
    //assert(l <= rr && r >= ll);
    if (l >= ll && r <= rr) {
        if (tag2[t] != -1) 
            tag2[t] += v; 
        else 
            tag[t] += v;
        color(t,v);
        return ;
    }
    push_down(t);
    int mid = (l + r) >> 1;
    if (ll <= mid)
        update_add(l,mid,ls);
    if (rr > mid)
        update_add(mid+1,r,rs);
    tr[t] = merge(tr[ls],tr[rs],t); 
}

void query(int l,int r,int t) {
    //assert(l <= rr && r >= ll);
    if (l >= ll && r <= rr) { ans += 1LL * tr[t].sum; return; }
    push_down(t);
    int mid = (l + r) >> 1;
    if (ll <= mid) query(l,mid,ls);
    if (rr > mid) query(mid+1,r,rs);
    tr[t] = merge(tr[ls],tr[rs],t);
}

int main()
{
    LL T = 0; read(T);
    while (T--) {
        //memset(tr,0,sizeof(tr));
        //memset(tag,0,sizeof(tag));
        //memset(tag2,255,sizeof(tag2));
        read(n); read(m);
        for (int i=1;i<=n;i++) read(A[i]);
        build(1,n,1);
        while (m--) {
            LL cmd = 0; read(cmd); read(ll); read(rr);
            switch(cmd) {
                case 1: { read(v); update_add(1,n,1); break;    }
                case 2: { update_sqrt(1,n,1); break; }
                case 3: { ans = 0LL; query(1,n,1); out(ans); printf("\n"); break; }
                assert(0);
            }
        }
    }
    return 0;
}
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    You forgot to mention that for step 4 we need maximum == minimum + 1

»
4 years ago, # |
Rev. 2   Vote: I like it -65 Vote: I do not like it

This tutorial could be helpful :

Range updates with BIT / Fenwick Tree

EDIT: I post a link for a tutorial and get all these downvotes! really?

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

Auto comment: topic has been updated by DeWitt (previous revision, new revision, compare).