Блог пользователя DeWitt

Автор DeWitt, 7 лет назад, По-русски

Недавно, решая задачи Петрозаводских тренировок этого года, столкнулся с интересной задачей:

есть массив, размера N <  = 105, и три типа запросов:

1 l r d -- увиличить все элементы на отрезке от l до r на t

2 l r -- на отрезке применить операцию взятия корня в округлением вниз, т.е.

3 l r -- почитать сумму на отрезке.

Запросов так же до 105, X всегде меньше 105

Пробовал разные подходы, но ничего работающего не нашел.

Подскажите, может кто знает.

З.Ы. Не хочет вставлять формулы :( Очень странный редактор постов

  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А какое ограничение на x?

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

По логике вещей, если проталкивать в ДО второй запрос до тех пор, пока на отрезке, соответствующему вершине, не будут все числа равны, то суммарно это будет работать не более чем за . Но ни мне, ни моему сокоманднику не удалось пропихнуть это в ТЛ (валится на 102-ом тесте).

А вообще, можно ж видео разбора посмотреть, и не гадать, как ее решать)

З.Ы. доллар X = \left \lfloor \sqrt{X} \right \rfloor доллар

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    На контесте такое решение заходило (например, мы сдали). После контеста был придуман и добавлен контртест (кажется, как раз номер 102). Тест такой:

    3 4 3 4 ... 3 4
    add 1 n 12
    sqrt 1 n
    add 1 n 12
    sqrt 1 n
    ...
    

    Можно заметить, что числа будут ходить по циклу 3 -> 15 -> 3 и 4 -> 16 -> 4, то есть на каждый запрос можно обойти всё дерево.

    Однако после контеста мы смогли это обойти :) Не помню, как именно, но суть сводилась к тому, что надо ифать не тогда, когда остался один элемент на всём отрезке, а когда два очень близких.

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Could you share the problem link?

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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;
}
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем DeWitt (предыдущая версия, новая версия, сравнить).