线段树练习

  • 时间:
  • 分类:

UOJ #228

题

维护区间开根、区间加和区间求和。

解

因为开根最大只可能有$ O(\lg a_i) $次，所以朴素的做法是区间开根转化为单点开根。
但这道题还需要进一步优化。
注意到开根后下取整得到的相同的数，原先所对应的数是有很多的，换句话说，有一些连续的数开根后下取整得到相同的数。
维护区间minmax后区间set。
上面的思路是对的，但换一种思路。相邻两个数若开根后属于不同的数，这两个数也必然相邻。
然后计算出区间minmax后开根下取整比较差，再区间减即可。

码（1190ms 13072kb）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
int n;
const int maxn = 1e5 + 100;
struct Info
{
    long long sum, add, _min, _max; 
    Info(long long a = 0, long long b = 0, long long c = 0) : sum(a), _min(b), _max(c), add(0){}
    Info operator+(const Info& rhs){return Info(sum + rhs.sum, min(_min, rhs._min), max(_max, rhs._max));}
}I[maxn << 2];
void build(int o = 1, int L = 1, int R = n)
{
    if(L == R) read(I[o].sum), I[o]._min = I[o]._max = I[o].sum;
    else
    {
        int M = (L + R) >> 1;
        build(o << 1, L, M);
        build(o << 1 | 1, M + 1, R);
        I[o] = I[o << 1] + I[o << 1 | 1];
    }
}
inline void pushdown(int o, int L, int R)
{
    if(L == R || !I[o].add) return;
    int M = (L + R) >> 1;
    I[o << 1].add += I[o].add;
    I[o << 1].sum += I[o].add * (long long)(M - L + 1);
    I[o << 1]._min += I[o].add;
    I[o << 1]._max += I[o].add; 
    I[o << 1 | 1].add += I[o].add;
    I[o << 1 | 1].sum += I[o].add * (long long)(R - M);
    I[o << 1 | 1]._min += I[o].add;
    I[o << 1 | 1]._max += I[o].add; 
    I[o].add = 0;
}
int l, r; long long v;
void add(int o = 1, int L = 1, int R = n)
{
    pushdown(o, L, R);
    if(l <= L && R <= r) I[o].sum += v * (R - L + 1), I[o].add += v, I[o]._min += v, I[o]._max += v;
    else
    {
        int M = (L + R) >> 1;
        if(l <= M) add(o << 1, L, M);
        if(M < r) add(o << 1 | 1, M + 1, R);
        I[o] = I[o << 1] + I[o << 1 | 1];
    }
}
void sroot(int o = 1, int L = 1, int R = n)
{
    pushdown(o, L, R);
    if(l <= L && R <= r && floor(sqrt(I[o]._max)) - floor(sqrt(I[o]._min)) == I[o]._max - I[o]._min) 
        v = floor(sqrt(I[o]._max)) - I[o]._max, add(o, L, R);
    else
    {
        int M = (L + R) >> 1;
        if(l <= M) sroot(o << 1, L, M);
        if(M < r) sroot(o << 1 | 1, M + 1, R);
        I[o] = I[o << 1] + I[o << 1 | 1];
    }
}
long long query(int o = 1, int L = 1, int R = n)
{
    pushdown(o, L, R);
    if(l <= L && R <= r) return I[o].sum;
    int M = (L + R) >> 1; long long ret = 0;
    if(l <= M) ret += query(o << 1, L, M);
    if(M < r) ret += query(o << 1 | 1, M + 1, R);
    return ret;
}
int main()
{
    int m; read(n, m);
    build();
    while(m--)
    {
        int t; read(t);
        if(t == 1) read(l, r, v), add();
        else if(t == 2) read(l, r), sroot();
        else read(l, r), printf("%lld\n", query());
    }
    return 0;
}

CF 444C

题

一段序列，两种操作。把区间内所有格子置为颜色 $ c $ 。查询一段区间历史版本修改的差的和的求和。

解

这道题范围给得比较宽松。所以用那种区间开根类似的思路递归改就可以。
本来想用下面那道题的解法……但还是太弱了……
时间复杂度严格 $ O(mn \lg n) $。
对了把pushdown至于合法条件判断后可以跑得更快。

码（186 ms 11200 KB）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e5 + 100;
struct Info
{
    long long c, d;
    long long sum;
    Info(long long a = 0, long long c = 0) : c(a), sum(c), d(0) {}
    Info operator+(const Info& rhs)
    {
        return Info(c == rhs.c ? c : 0, sum + rhs.sum);
    }
} I[maxn << 2];
int n;
void build(int o = 1, int L = 1, int R = n)
{
    if(L == R) I[o].c = L;
    else
    {
        int M = (L + R) >> 1;
        build(o << 1, L, M);
        build(o << 1 | 1, M + 1, R);
        I[o] = I[o << 1] + I[o << 1 | 1];
    }
}
int l, r; long long v;
inline void pushdown(int o, int L, int R)
{
    if(I[o].c && L != R)
    {
        int M = (L + R) >> 1;
        I[o << 1].c = I[o << 1 | 1].c = I[o].c;
        I[o << 1].d += I[o].d, I[o << 1 | 1].d += I[o].d;
        I[o << 1].sum += I[o].d * (M - L + 1);
        I[o << 1 | 1].sum += I[o].d * (R - M);
        I[o].c = I[o].d = 0;
    }
}
void update(int o = 1, int L = 1, int R = n)
{
    if(l <= L && R <= r && I[o].c)
        I[o].d += abs(v - I[o].c), I[o].sum += abs(v - I[o].c) * (R - L + 1), I[o].c = v;
    else
    {
        int M = (L + R) >> 1;
    pushdown(o, L, R);
        if(l <= M) update(o << 1, L, M);
        if(M < r) update(o << 1 | 1, M + 1, R);
        I[o] = I[o << 1] + I[o << 1 | 1];
    }
}
long long query(int o = 1, int L = 1, int R = n)
{
    if(l <= L && R <= r)
        return I[o].sum;
    int M = (L + R) >> 1;
    pushdown(o, L, R);
    long long ret = 0;
    if(l <= M) ret += query(o << 1, L, M);
    if(M < r) ret += query(o << 1 | 1, M + 1, R);
    return ret;
}
int main()
{
    int m; read(n, m);
    build();
    while(m--)
    {
        int t; read(t);
        if(t == 1)
            read(l, r, v), update();
        else
            read(l, r), printf("%I64d\n", query());
    }
    return 0;
}

HDU 5306

题

区间对一个数取$ \min $。查询区间最大值、和。

解

参考 WC 2016 Segment Tree Beats! 的讲课课件。
考虑记录最大值、最大值出现次数、次大值 $ \\_max, cnt, sec $ ，则对数 $ t $ 我们可以有

if t >= _max then
    return //显然毋需更新
if sec < t < _max then
    sum = sum - (_max - t) * cnt
    _max = t
    return
else
    ...//???

前二情况上面的处理显然，第三种呢。递归重复前述处理就行了。
时间复杂度呢？下面我们证明它仍然是和普通一样的 $ O(m \lg n) $。
我们可以将每一个节点的最大值标记看成是区间取 $ \min $，故子树的值显然应该是严格单调递减的，其它为非法节点。
所以每次向下的过程会在碰到第一个非法标记的时候解除递归。可以发现总的下放过程不超过打标记和标记下放时间之和，即 $ O(m \lg n) $ 。均摊一下即是单次 $ O(\lg n) $ 。
至此我们完成了对如此做法复杂度的证明。

码（1170MS 130396K）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char *ch, *ch1, buf[40*1024000+5], buf1[40*1024000+5];
template<class T>      
void read(T &x)   {      
    for (++ch; *ch <= 32; ++ch);      
    for (x = 0; '0' <= *ch; ch++)    x = x * 10 + *ch - '0';      
}  
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e6 + 5;
struct Info
{
    int _max, sec, cnt;
    long long sum;
    Info(long long a = 0, int b = 0, int c = -1, int d = 0): sum(a), _max(b), sec(c), cnt(d) {}
    Info operator+(const Info& rhs)
    {
        if(_max == rhs._max) return Info(sum + rhs.sum, _max, max(sec, rhs.sec), cnt + rhs.cnt);
        if(_max < rhs._max) return Info(sum + rhs.sum, rhs._max, max(rhs.sec, _max), rhs.cnt);
        return Info(sum + rhs.sum, _max, max(sec, rhs._max), cnt);
    }
} I[maxn << 2];
int n;
int l, r, v;
void build(int o = 1, int L = 1, int R = n)
{
    if(L == R) read(I[o].sum), I[o]._max = I[o].sum, I[o].cnt = 1, I[o].sec = -1;
    else
    {
        int M = (L + R) >> 1;
        build(o << 1, L, M);
        build(o << 1 | 1, M + 1, R);
        I[o] = I[o << 1] + I[o << 1 | 1];
    }
}
inline void pushdown(int o, int L, int R)
{
    if(L == R) return;
    if(I[o << 1]._max > I[o]._max) I[o << 1].sum += (long long)(I[o]._max - I[o << 1]._max) * (long long)I[o << 1].cnt, I[o << 1]._max = I[o]._max;
    if(I[o << 1 | 1]._max > I[o]._max) I[o << 1 | 1].sum += (long long)(I[o]._max - I[o << 1 | 1]._max) * (long long)I[o << 1 | 1].cnt, I[o << 1 | 1]._max = I[o]._max;
}
void update(int o = 1, int L = 1, int R = n)
{
    if(I[o]._max <= v) return;
    if(l <= L && R <= r && I[o].sec < v)
    {
        I[o].sum -= (long long)(I[o]._max - v) * (long long)I[o].cnt, I[o]._max = v;
        return;
    }
    int M = (L + R) >> 1;
    pushdown(o, L, R);
    if(l <= M) update(o << 1, L, M);
    if(M < r) update(o << 1 | 1, M + 1, R);
    I[o] = I[o << 1] + I[o << 1 | 1];
}
int getmax(int o = 1, int L = 1, int R = n)
{
    if((l <= L && R <= r)) return I[o]._max;
    int M = (L + R) >> 1;
    pushdown(o, L, R);
    int ret = 0;
    if(l <= M) ret = max(ret, getmax(o << 1, L, M));
    if(M < r) ret = max(ret, getmax(o << 1 | 1, M + 1, R));
    return ret;
}
long long getsum(int o = 1, int L = 1, int R = n)
{
    if((l <= L && R <= r)) return I[o].sum;
    int M = (L + R) >> 1;
    pushdown(o, L, R);
    long long ret = 0;
    if(l <= M) ret = ret + getsum(o << 1, L, M);
    if(M < r) ret = ret + getsum(o << 1 | 1, M + 1, R);
    return ret;
}
int main()
{
    ch = buf - 1;      
    ch1 = buf1 - 1;      
    fread(buf, 1, 1000 * 35 * 1024, stdin); 
    int t; read(t);
    while(t--)
    {
        //memset(I, 0, sizeof I);
        int m; read(n, m);
        build();
        while(m--)
        {
            int type; read(type);
            if(type == 0) read(l, r, v), update();
            else if(type == 1) read(l, r), printf("%lld\n", getmax());
            else read(l, r), printf("%lld\n", getsum());
        }
    }
    return 0;
}

标签: 线段树

添加新评论