小清新线段树

小清新线段树的概念是由jiry_2提出的，区别于zkw(重口味)线段树命名。这里我的理解是可以归为一类结合时间复杂度分析以及懒标记应用的非传统线段树。不过既为非传统，这类题目总体来说还是做法各异，下面就结合题目做一些分析。

入门难度

1.bzoj 3211 花神游历各国

区间求和，区间开根号（下取整）

因为只有开根号操作，所以最后不是1就是0，且一个数开根号次数O(loglogC)O(loglogC)级别的，1e9的数最多开5次。所以就怎么暴力都行了，比如判断当前区间最大值是否是1，或者直接记录访问每个节点的次数是否达到5次，用于剪枝。时间复杂度O(nlogn+nloglogC)O(nlogn+nloglogC)。

2.bzoj 3333 排队计划

这个题其实不是很入门

有一个排列，每次修改是给一个位置x，先拿出x及之后所有小于等于a[x]的数，从小到大排序后，再放回空位中，一开始及每次操作完都要输出当前排列的逆序对数。

计算逆序对数就用传统方法，把以每个位置为开头的逆序对数加起来。那么通过观察发现，这个排序操作会抹掉x及之后所有小于等于a[x]的那些位置的贡献，并且不会对其他不动的位置的贡献造成影响。这样每次用线段树通过判断最小值，每次暴力下去找到需要清除贡献的地方即可，因为每个点只会被清除一次，那么平摊下来总时间复杂度就是O(nlogn)O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
#define N 500010
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
int a[N],n,m;
int h[N],cnt;
int val[N],c[N];
struct node
{
    int l,r,mn;
    ll val;
} t[N<<2];
int ask(int x)
{
    int ans=0;
    for(;x;x-=x&(-x)) ans+=c[x];
    return ans;
}
void change(int x,int y)
{
    for(;x<=cnt;x+=x&(-x)) c[x]+=y;
}
void push_up(int p)
{
    t[p].mn=min(t[ls(p)].mn,t[rs(p)].mn);
    t[p].val=t[ls(p)].val+t[rs(p)].val;
}
void build(int p,int l,int r)
{
    t[p].l=l;t[p].r=r;
    if(l==r)
    {
        t[p].val=val[l];
        t[p].mn=a[l];
        return;
    }
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void change(int p,int l,int r,int y)
{
    if(t[p].r<l||r<t[p].l||t[p].mn>y) return;
    if(t[p].l==t[p].r)
    {
        t[p].val=0;
        t[p].mn=INF;
        a[t[p].l]=INF;
        return;
    }
    change(ls(p),l,r,y);
    change(rs(p),l,r,y);
    push_up(p);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",a+i);
        h[i]=a[i];
    }
    cnt=n;
    sort(h+1,h+cnt+1);
    cnt=unique(h+1,h+cnt+1)-h-1;
    for(int i=n;i>=1;--i)
    {
        a[i]=lower_bound(h+1,h+cnt+1,a[i])-h;
        val[i]=ask(a[i]-1);
        change(a[i],1);
    }
    build(1,1,n);
    printf("%lld\n",t[1].val);
    while(m--)
    {
        int x;
        scanf("%d",&x);
        if(a[x]!=INF) change(1,x,n,a[x]);
        printf("%lld\n",t[1].val);
    }
    return 0;
}

进阶难度

1.Petrozavodsk Winter-2018. AtCoder Contest I. ADD, DIV, MAX

维护序列，支持区间加，区间整除，区间求最大值。

我们定义线段树上每个节点势能函数为W=log2(Max−Min)W=log_2(Max-Min)，或者直观理解就是这个区间除以多少次2就会完全相同。那么由于线段树一共O(n)O(n)个节点，初始总势能为O(nlogC)O(nlogC)。因为线段树区间操作会访问O(logn)O(logn)个节点，所以一次区间加操作至多增加O(lognlogC)O(lognlogC)。由于我们修改时访问一个节点就会使该节点势能减一，所以总的时间复杂度是O(nlognlogC)O(nlognlogC)。

具体实现就是线段树维护最大值最小值，以及加法的懒标记，对于除法操作如果当前区间的最大值和最小值的改变量是相同的，那么对于这个区间来说，除法操作就可以看成整体加上一个数，否则暴力递归到左右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
struct node
{
    int l,r,min,max,add;
} t[N<<4];
int n,m;
void push_up(int p)
{
    t[p].min=min(t[ls(p)].min,t[rs(p)].min);
    t[p].max=max(t[ls(p)].max,t[rs(p)].max);
}
void update(int p,int y)
{
    t[p].add+=y;
    t[p].min+=y;
    t[p].max+=y;
}
void push_down(int p)
{
    if(t[p].add)
    {
        update(ls(p),t[p].add);
        update(rs(p),t[p].add);
        t[p].add=0;
    }
}

void build(int p,int l,int r)
{
    t[p].l=l;t[p].r=r;
    if(l==r)
    {
        int x;
        scanf("%d",&x);
        t[p].min=t[p].max=x;
        t[p].add=0;
        return ;
    }
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void Add(int p,int l,int r,int x)
{
    if(t[p].r<l || r<t[p].l) return;
    if(l<=t[p].l && t[p].r<=r)
    {
        update(p,x);
        return;
    }
    push_down(p);
    Add(ls(p),l,r,x);
    Add(rs(p),l,r,x);
    push_up(p);
}
void Div(int p,int l,int r,int x)
{
    if(t[p].r<l||r<t[p].l|| (t[p].max==0)) return;
    if(l<=t[p].l&&t[p].r<=r &&  t[p].min/x-t[p].min==t[p].max/x-t[p].max)
    {
        update(p,t[p].min/x-t[p].min);
        return;
    }
    push_down(p);
    Div(ls(p),l,r,x);
    Div(rs(p),l,r,x);
    push_up(p);
}
int Ask(int p,int l,int r)
{
    if(r<t[p].l || t[p].r<l) return 0;
    if(l<=t[p].l && t[p].r<=r) return t[p].max;
    push_down(p);
    return max(Ask(ls(p),l,r),Ask(rs(p),l,r));
}
int main()
{
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        int op,l,r,x;
        scanf("%d%d%d%d",&op,&l,&r,&x);
        ++l;++r;
        if(op==0) Add(1,l,r,x);
        else if(op==1)
        {
            if(x>1) Div(1,l,r,x);
        }
        else printf("%d\n",Ask(1,l,r));
    }
    return 0;
}

2.Codeforces 438D The Child and Sequence

维护序列，支持区间求和，区间模一个数，单点修改。

首先需要用一个很好证明的式子x mod p≤x/2x\, mod\, p \le x/2，也就是说模操作会让每个数至少除以2。由于只有单点修改，那么就比上一个题好分析了，势能函数是每个区间最大值除以2的次数，初始总势能O(nlogC)O(nlogC)，单点修改还是，改变了O(logn)O(logn)个点，每个点充能O(logC)O(logC)，所以总的时间复杂度O(nlognlogC)O(nlognlogC)。

那么具体实现额外维护最大值，当区间最大值小于模数就剪枝，否则暴力下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
struct node
{
    int l,r,mx;
    ll sum;
} t[N<<2];
int n,m;
void push_up(int p)
{
    t[p].mx=max(t[ls(p)].mx,t[rs(p)].mx);
    t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
}
void build(int p,int l,int r)
{
    t[p].l=l;t[p].r=r;
    if(l==r)
    {
        int x;
        scanf("%d",&x);
        t[p].mx=x;
        t[p].sum=x;
        return ;
    }
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void change(int p,int l,int r,int y)
{
    if(t[p].r<l||r<t[p].l||t[p].mx<y) return;
    if(t[p].l==t[p].r)
    {
        t[p].sum=t[p].mx=t[p].mx%y;
        return;
    }
    change(ls(p),l,r,y);
    change(rs(p),l,r,y);
    push_up(p);
}
void change(int p,int x,int y)
{
    if(t[p].l==t[p].r)
    {
        t[p].sum=t[p].mx=y;
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid) change(ls(p),x,y);
    else change(rs(p),x,y);
    push_up(p);
}
ll ask(int p,int l,int r)
{
    if(t[p].r<l||r<t[p].l) return 0;
    if(l<=t[p].l && t[p].r<=r) return t[p].sum;
    return ask(ls(p),l,r)+ask(rs(p),l,r);
}
int main()
{
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--)
    {
        int opt;
        scanf("%d",&opt);
        if(opt==1)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%lld\n",ask(1,l,r));
        }
        else if(opt==2)
        {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            change(1,l,r,x);
        }
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);
            change(1,x,y);
        }
    }
    return 0;
}

3.hdu 5306 Gorgeous Sequence

维护序列，区间对一个数取min，询问区间最小值，区间求和

这个题的做法就比较科幻了。

《Segment tree Beats!》课件中关于时间复杂度的证明一些是错误的

可以参考这里，http://jiry-2.blog.uoj.ac/blog/1404

时间复杂度O(nlog2n)O(nlog^{2}n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000010
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
struct node
{
    int fi,se,cnt,cov;
    ll sum;
} t[N<<2];
int n,m;
void read(int &x)
{
    static char ch;
    while(!isdigit(ch=getchar()));
    x=ch-'0';
    while(isdigit(ch=getchar()))
        x=x*10+(ch-'0');
}
void push_up(int p)
{
    t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
    if(t[ls(p)].fi==t[rs(p)].fi)
    {
        t[p].fi=t[ls(p)].fi;
        t[p].se=max(t[ls(p)].se,t[rs(p)].se);
        t[p].cnt=t[ls(p)].cnt+t[rs(p)].cnt;
    }
    else if(t[ls(p)].fi>t[rs(p)].fi)
    {
        t[p].fi=t[ls(p)].fi;
        t[p].se=max(t[ls(p)].se,t[rs(p)].fi);
        t[p].cnt=t[ls(p)].cnt;
    }
    else
    {
        t[p].fi=t[rs(p)].fi;
        t[p].se=max(t[ls(p)].fi,t[rs(p)].se);
        t[p].cnt=t[rs(p)].cnt;
    }
}
void build(int p,int l,int r)
{
    t[p].cov=-1;
    if(l==r)
    {
        read(t[p].fi);
        t[p].se=-1;
        t[p].cnt=1;
        t[p].sum=t[p].fi;
        return;
    }
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void update(int p,int y)
{
    if(y>=t[p].fi) return;
    t[p].sum-=1LL*t[p].cnt*(t[p].fi-y);
    t[p].fi=t[p].cov=y;
}
void push_down(int p)
{
    if(t[p].cov!=-1)
    {
        update(ls(p),t[p].cov);
        update(rs(p),t[p].cov);
        t[p].cov=-1;
    }
}
void change(int p,int l,int r,int L,int R,int y)
{
    if(r<L||R<l||t[p].fi<=y) return;
    if(L<=l && r<=R)
    {
        if(l==r)
        {
            t[p].sum=t[p].fi=y;
            t[p].se=-1;
            t[p].cnt=1;
            return;
        }
        if(t[p].se<y && y<t[p].fi)
        {
            update(p,y);
            return;
        }
    }
    push_down(p);
    int mid=l+r>>1;
    change(ls(p),l,mid,L,R,y);
    change(rs(p),mid+1,r,L,R,y);
    push_up(p);
}
int ask_max(int p,int l,int r,int L,int R)
{
    if(r<L||R<l) return -1;
    if(L<=l && r<=R) return t[p].fi;
    push_down(p);
    int mid=l+r>>1;
    return max(ask_max(ls(p),l,mid,L,R),ask_max(rs(p),mid+1,r,L,R));
}
ll ask_sum(int p,int l,int r,int L,int R)
{
    if(r<L||R<l) return 0;
    if(L<=l && r<=R) return t[p].sum;
    push_down(p);
    int mid=l+r>>1;
    return ask_sum(ls(p),l,mid,L,R)+ask_sum(rs(p),mid+1,r,L,R);
}
int main()
{
    int T;
    read(T);
    while(T--)
    {
        read(n);read(m);
        build(1,1,n);
        while(m--)
        {
            int opt,x,y,t;
            read(opt);read(x);read(y);
            if(opt==0)
            {
                read(t);
                change(1,1,n,x,y,t);
            }
            else if(opt==1)
                printf("%d\n",ask_max(1,1,n,x,y));
            else
                printf("%lld\n",ask_sum(1,1,n,x,y));
        }
    }
    return 0;
}

4.hdu 5634 Rikka with Phi

维护序列，区间赋值，区间取phi，区间求和。

首先根据定义以及相关公式，知道一个大于2的正整数的欧拉函数都是偶数，一个偶数的欧拉函数就至少小了一半，那么一个数能做的次数也就是O(logC)O(logC)级别的。

根据前面几个题，这个题的操作就很好想了，如果当前区间的数都相同，那么区间取phi的操作就转化成了区间赋值，同样的打标记即可，不同的话就暴力下去。

时间复杂度是一个log的就比较确信了，然而并不会证。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 300010
#define MAXN 10000000
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
int prime[MAXN+5],phi[MAXN+5],tot;
bool vis[MAXN+5];
struct node
{
    int l,r,max,min,cov;
    ll sum;
} t[N<<2];
int n,m;
void getprime()
{
    phi[1]=1;
    for(int i=2;i<=MAXN;++i)
    {
        if(!vis[i])
        {
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot && prime[j]<=MAXN/i;++j)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]) phi[i*prime[j]]=phi[i]*(prime[j]-1);
            else
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
        }
    }
}
void push_up(int p)
{
    t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
    t[p].max=max(t[ls(p)].max,t[rs(p)].max);
    t[p].min=min(t[ls(p)].min,t[rs(p)].min);
}
void build(int p,int l,int r)
{
    t[p].l=l;t[p].r=r;
    t[p].cov=-1;
    if(l==r)
    {
        int x;
        scanf("%d",&x);
        t[p].sum=t[p].max=t[p].min=x;
        return ;
    }
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
void update(int p,int y)
{
    t[p].sum=1LL*y*(t[p].r-t[p].l+1);
    t[p].max=t[p].min=y;
    t[p].cov=y;
}
void push_down(int p)
{
    if(t[p].cov!=-1)
    {
        update(ls(p),t[p].cov);
        update(rs(p),t[p].cov);
        t[p].cov=-1;
    }
}
void change(int p,int l,int r)
{
    if(t[p].r<l||r<t[p].l) return;
    if(l<=t[p].l && t[p].r<=r && t[p].max==t[p].min)
    {
        update(p,phi[t[p].max]);
        return;
    }
    push_down(p);
    change(ls(p),l,r);
    change(rs(p),l,r);
    push_up(p);
}
void cover(int p,int l,int r,int y)
{
    if(t[p].r<l||r<t[p].l) return;
    if(l<=t[p].l && t[p].r<=r)
    {
        update(p,y);
        return;
    }
    push_down(p);
    cover(ls(p),l,r,y);
    cover(rs(p),l,r,y);
    push_up(p);
}
ll ask(int p,int l,int r)
{
    if(t[p].r<l||r<t[p].l) return 0;
    if(l<=t[p].l && t[p].r<=r) return t[p].sum;
    push_down(p);
    return ask(ls(p),l,r)+ask(rs(p),l,r);
}
int main()
{
    getprime();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        build(1,1,n);
        while(m--)
        {
            int opt,l,r,x;
            scanf("%d%d%d",&opt,&l,&r);
            if(opt==1) change(1,l,r);
            else if(opt==2)
            {
                scanf("%d",&x);
                cover(1,l,r,x);
            }
            else printf("%lld\n",ask(1,l,r));
        }
    }
    return 0;
}
算法学习
#线段树 #时间复杂度
小清新线段树
https://izard.space/2018/11/08/小清新线段树/
作者
forever_you
发布于
2018年11月8日
许可协议