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

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

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

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

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

Could you share the problem link?

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;
}

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

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