线段树练习（也有树状数组）

字数统计: 9.1k字 | 阅读时长: 44分

线段树练习（也有树状数组）

洛谷 P2184 贪婪大陆

题目背景

面对蚂蚁们的疯狂进攻，小FF的Tower defence宣告失败……人类被蚂蚁们逼到了Greed Island上的一个海湾。现在，小FF的后方是一望无际的大海， 前方是变异了的超级蚂蚁。 小FF还有大好前程，他可不想命丧于此， 于是他派遣手下最后一批改造SCV布置地雷以阻挡蚂蚁们的进攻。

题目描述

小FF最后一道防线是一条长度为N的战壕， 小FF拥有无数多种地雷，而SCV每次可以在[ L , R ]区间埋放同一种不同于之前已经埋放的地雷。 由于情况已经十万火急，小FF在某些时候可能会询问你在[ L’ , R’] 区间内有多少种不同的地雷， 他希望你能尽快的给予答复。

对于30%的数据： 0<=n, m<=1000;

对于100%的数据： 0<=n, m<=10^5.

输入输出格式

输入格式：

第一行为两个整数n和m； n表示防线长度， m表示SCV布雷次数及小FF询问的次数总和。

接下来有m行， 每行三个整数Q，L , R； 若Q=1 则表示SCV在[ L , R ]这段区间布上一种地雷， 若Q=2则表示小FF询问当前[ L , R ]区间总共有多少种地雷。

输出格式：

对于小FF的每次询问，输出一个答案（单独一行），表示当前区间地雷总数。

思路：这题第一眼看完全没有思路啊，但其实很简单，我们可以把一个区间看成开头和结尾两个点，那么假如我们能知道一个点前面有多少开头和结尾（显然能），这题会不会好做呢？

看图

img

就把这个玩意当图吧（别笑！！！），左箭头表示一个区间的开头，右箭头表示结尾，两个|之间是我们要查询的区间，首先我们先不管区间的结尾，那么有可能的答案个数就是查询区间结尾前面的区间开头个数。

这样我们做出来差点AC的0分做法，因为有些区间早在查询区间开头前就结束了，这些区间的个数？查询区间开头前面有一个右箭头就结束一个区间你还问什么！

那么ans=sum1[r]-sum2[l-1]（l,r表示查询区间的开始和结束，是l-1的原因是如果在l处有一个区间结束了，那也要算到答案里）

树状数组做的（这一定是假的线段树练习）：

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
#include<cstdio>
#include<iostream>
using namespace std;
int c1[100001],c2[100001],n,t; 
inline int lowbit(int x){return x&(-x);}
inline void update1(int x){
    while (x<=n){
        c1[x]++;
        x+=lowbit(x);
    }
}
inline void update2(int x){
    while (x<=n){
        c2[x]++;
        x+=lowbit(x);
    }
}
inline int query1(int x){
    int ans=0;
    while (x){
        ans+=c1[x];
        x-=lowbit(x);
    }
    return ans;
}
inline int query2(int x){
    int ans=0;
    while (x){
        ans+=c2[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    int b,x,y;
    scanf("%d%d",&n,&t);
    while (t--){
        scanf("%d%d%d",&b,&x,&y);
        if (b==1){
            update1(x);
            update2(y);
        }
        else{
            int c=query1(y)-query2(x-1);
            printf("%d\n",c);
        }
    }
    return 0;
}

洛谷 P3870 [TJOI2009]开关+P2846 [USACO08NOV]光开关Light Switching+P2574 XOR的艺术（三道重题）

题目描述

现有N（2 ≤ N ≤ 100000）盏灯排成一排，从左到右依次编号为：1，2，……，N。然后依次执行M（1 ≤ M ≤ 100000）项操作，操作分为两种：第一种操作指定一个区间[a, b]，然后改变编号在这个区间内的灯的状态（把开着的灯关上，关着的灯打开），第二种操作是指定一个区间[a, b]，要求你输出这个区间内有多少盏灯是打开的。灯在初始时都是关着的。

输入输出格式

输入格式：

第一行有两个整数N和M，分别表示灯的数目和操作的数目。接下来有M行，每行有三个整数，依次为：c, a, b。其中c表示操作的种类，当c的值为0时，表示是第一种操作。当c的值为1时表示是第二种操作。a和b则分别表示了操作区间的左右边界（1 ≤ a ≤ b ≤ N）。

输出格式：

每当遇到第二种操作时，输出一行，包含一个整数：此时在查询的区间中打开的灯的数目。

这么水的题还三道？我第一个做的是那个XOR的艺术，那题还需要建个树，其他两个，emmmm。

其实就是让你把一变成零，把零变成一，那么下推的法则就是sum[rt]=r-l+1-sum[rt]，然后标记取异或，算了看代码吧。

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
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll sum[4000001],ad[4000001],n,t,i,a[1000001];
char c;
inline void pushup(ll rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
inline void build(ll rt,ll l,ll r){
    if (l==r){
        sum[rt]=a[l];
        return;
    }
    ll m=(l+r)>>1;
    build(rt<<1,l,m);
    build(rt<<1|1,m+1,r);
    pushup(rt);
}
inline void pushdown(ll rt,ll l,ll r){
    if (ad[rt]){
        ll m=(l+r)>>1;
        ad[rt<<1]^=ad[rt];
        ad[rt<<1|1]^=ad[rt];
        sum[rt<<1]=(m-l+1)-sum[rt<<1];
        sum[rt<<1|1]=(r-m)-sum[rt<<1|1];
        ad[rt]=0;
    }
    return;
}
inline void update(ll rt,ll l,ll r,ll x,ll y){
    if (x>r||l>y) return;
    if (x<=l&&r<=y){
        sum[rt]=r-l+1-sum[rt];
        ad[rt]=ad[rt]^1;
        return;
    }
    pushdown(rt,l,r);
    ll m=(l+r)>>1;
    if (m>=x) update(rt<<1,l,m,x,y);
    if (m<y) update(rt<<1|1,m+1,r,x,y);
    pushup(rt);
}
inline ll query(ll rt,ll l,ll r,ll x,ll y){
    if (x>r||l>y) return 0;
    if (x<=l&&r<=y)    return sum[rt];
    pushdown(rt,l,r);
    ll ans=0,m=(r+l)>>1;
    if (m>=x) ans+=query(rt<<1,l,m,x,y);
    if (m<y) ans+=query(rt<<1|1,m+1,r,x,y);
    return ans;
}
int main(){
    ll b,x,y;
    scanf("%lld%lld",&n,&t);
    c=getchar(); c=getchar();
    for (i=1; i<=n; i++){
        scanf("%c",&c);
        a[i]=c-'0';
    }
    build(1,1,n);
    while (t--){
        scanf("%lld%lld%lld",&b,&x,&y);
        if (b==0){
            update(1,1,n,x,y);
        }
        else{
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

洛谷 P1471 方差

题目背景

滚粗了的HansBug在收拾旧数学书，然而他发现了什么奇妙的东西。

题目描述

蒟蒻HansBug在一本数学书里面发现了一个神奇的数列，包含N个实数。他想算算这个数列的平均数和方差。

输入输出格式

输入格式：

第一行包含两个正整数N、M，分别表示数列中实数的个数和操作的个数。

第二行包含N个实数，其中第i个实数表示数列的第i项。

接下来M行，每行为一条操作，格式为以下两种之一：

操作1：1 x y k ，表示将第x到第y项每项加上k，k为一实数。

操作2：2 x y ，表示求出第x到第y项这一子数列的平均数。

操作3：3 x y ，表示求出第x到第y项这一子数列的方差。

输出格式：

输出包含若干行，每行为一个实数，即依次为每一次操作2或操作3所得的结果（所有结果四舍五入保留4位小数）。

思路：

首先，平均数好求，维护一个区间和就好了，那么我们来推柿子：

设数列 a1,a2,a3…an长度为n(废话)，平均数为x

那么方差：$((a1-x)^2 + (a2-x)^2 +(a3-x)^2…….+ (an-x)^2 )/n$

$=(a1^2 + a2^2 …… +an^2 +nx^2 - 2(a1+a2..an)*x)/n;$

那么我们设$a1+a2..+an=sum$

则$nx=sum nxx=sumx$

则原式=$(a1^2 + a2^2 …… +an^2 +sumx - 2sum*x)/n$

=$(a1^2 + a2^2 …… +an^2 - sum*x)/n;$

又 $sum/n=x$

则原式=$(a1^2 + a2^2 …… +an^2 )/n- x^2;$

这么看我们只要求平方和和平均数就好了？

还没完，还有区间加呢！怎么维护一个区间的平方和呢？

接着推柿子：

还是设数列 $a1,a2,a3…an$长度为n,这个数列要加x

那么$(a1+x)^2+(a2+x)^2+(a3+x)^2+…..(a2+x)^2$

=$a1^2 + a2^2…… +an^2 +nx^2 +2(a1+a2..+an)*x$

于是我们就可以同时维护和以及平方和，然后用上面那个式子求方差。

完了。。这回真完了。

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
#include<cstdio>
#include<iostream>
#define d double 
using namespace std;
d a[100001],sum[400001],sf[400001],ad[400001];
int n,t,i;
inline void pushup(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    sf[rt]=sf[rt<<1]+sf[rt<<1|1];
}
inline void build(int rt,int l,int r){
    if (l==r){
        sum[rt]=a[l];
        sf[rt]=a[l]*a[l];
        return;
    }
    int m=(l+r)>>1;
    build(rt<<1,l,m);
    build(rt<<1|1,m+1,r);
    pushup(rt);
}
inline void pushdown(int rt,int l,int r){
    if (ad[rt]){
        int m=(l+r)>>1;
        ad[rt<<1]+=ad[rt];
        ad[rt<<1|1]+=ad[rt];
        sf[rt<<1]+=(ad[rt]*ad[rt]*(m-l+1)+sum[rt<<1]*ad[rt]*2);
        sum[rt<<1]+=ad[rt]*(m-l+1);
        sf[rt<<1|1]+=(ad[rt]*ad[rt]*(r-m)+sum[rt<<1|1]*ad[rt]*2);
        sum[rt<<1|1]+=ad[rt]*(r-m);
        ad[rt]=0;
    }
}
inline void update(int rt,int l,int r,int x,int y,d k){
    if (l>y||r<x) return;
    if (x<=l&&r<=y){
        ad[rt]+=k;
        sf[rt]+=k*k*(r-l+1)+sum[rt]*k*2;
        sum[rt]+=k*(r-l+1);
        return;
    }
    pushdown(rt,l,r);
    int m=(l+r)>>1;
    update(rt<<1,l,m,x,y,k);
    update(rt<<1|1,m+1,r,x,y,k);
    pushup(rt);
}
inline d query1(int rt,int l,int r,int x,int y){
    if (l>y||r<x) return 0;
    if (x<=l&&r<=y)    return sum[rt];
    pushdown(rt,l,r);
    int m=(l+r)>>1;d ans=0;
    if (m>=x) ans+=query1(rt<<1,l,m,x,y);
    if (m<y) ans+=query1(rt<<1|1,m+1,r,x,y);
    return ans;
}
inline d query2(int rt,int l,int r,int x,int y){
    if (l>y||r<x) return 0;
    if (x<=l&&r<=y)    return sf[rt];
    pushdown(rt,l,r);
    int m=(l+r)>>1;d ans=0;
    if (m>=x) ans+=query2(rt<<1,l,m,x,y);
    if (m<y) ans+=query2(rt<<1|1,m+1,r,x,y);
    return ans;    
}
int main(){
    int x,y,b; d k;
    scanf("%d%d",&n,&t);
    for (i=1; i<=n; i++) cin>>a[i];
    build(1,1,n);
    while (t--){
        scanf("%d%d%d",&b,&x,&y);
        if (b==1){
            scanf("%lf",&k);
            update(1,1,n,x,y,k);
        }
        if (b==2){
            d f=query1(1,1,n,x,y)/(y-x+1);
            printf("%.4lf\n",f);
        }
        if (b==3){
            d ret=query2(1,1,n,x,y)/(y-x+1),pj=query1(1,1,n,x,y)/(y-x+1);
            d fg=ret-pj*pj;
            printf("%.4lf\n",fg);
        }
    }
    return 0;
}

洛谷 P1438 无聊的数列

题目背景

无聊的YYB总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的YYB想出了一道无聊的题：无聊的数列。。。（K峰：这题不是傻X题吗）

题目描述

维护一个数列{a[i]}，支持两种操作：

1、1 L R K D：给出一个长度等于R-L+1的等差数列，首项为K，公差为D，并将它对应加到a[L]~a[R]的每一个数上。即：令a[L]=a[L]+K，a[L+1]=a[L+1]+K+D，

a[L+2]=a[L+2]+K+2D……a[R]=a[R]+K+(R-L)D。

2、2 P：询问序列的第P个数的值a[P]。

输入输出格式

输入格式：

第一行两个整数数n，m，表示数列长度和操作个数。

第二行n个整数，第i个数表示a[i]（i=1,2,3…,n）。

接下来的m行，表示m个操作，有两种形式：

1 L R K D

2 P 字母意义见描述（L≤R）。

输出格式：

对于每个询问，输出答案，每个答案占一行。

img

第一眼看：嗯？等差数列？单点查询？

并没有思路，然后翻题解翻到了差分，没了。

我们可以先这么想，毒瘤出题人怎么可能只有单点查询呢！说单点查询一定是坑人的！最后一定还是区间查询！

区间查询出一个点的值？差分！（以上是笑话）

思路：既然知道了用差分，那么我们来看怎么维护，分类讨论一下，首先看首项，它的差分数组应该加k，后面l+1到r项应该全部加d，第r+1项要减去等比数列的最后一项（全部是根据差分的定义，请自行模拟）。

那么单点查询就是求差分数组的前缀和。

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
#include<cstdio>
#include<iostream>
using namespace std;
int sum[400001],n,t,a[100001],ad[400001];
inline void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
inline void build(int rt,int l,int r){
    if (l==r){
        sum[rt]=a[l];
        return;
    }
    int m=(l+r)>>1;
    build(rt<<1,l,m);
    build(rt<<1|1,m+1,r);
    pushup(rt);
}
inline void pushdown(int rt,int l,int r){
    if (ad[rt]){
        int m=(l+r)>>1;
        sum[rt<<1]+=ad[rt]*(m-l+1);
        sum[rt<<1|1]+=ad[rt]*(r-m);
        ad[rt<<1]+=ad[rt];
        ad[rt<<1|1]+=ad[rt];
        ad[rt]=0;
    }
}
inline void update(int rt,int l,int r,int x,int y,int k){
    if (l>y||r<x) return;
    if (x<=l&&r<=y){
        ad[rt]+=k;
        sum[rt]+=(r-l+1)*k;
        return;
    }
    pushdown(rt,l,r);
    int m=(l+r)>>1;
    if (m>=x) update(rt<<1,l,m,x,y,k);
    if (m<y) update(rt<<1|1,m+1,r,x,y,k);
    pushup(rt);
}
inline int query(int rt,int l,int r,int x,int y){
    if (l>y||x>r) return 0;
    if (x<=l&&r<=y) return sum[rt];
    pushdown(rt,l,r);
    int m=(l+r)>>1,ans=0;
    if (x<=m) ans+=query(rt<<1,l,m,x,y);
    if (m<y) ans+=query(rt<<1|1,m+1,r,x,y);
    return ans;
}
int main(){
    int x,y=0,b,k,d,i;
    scanf("%d%d",&n,&t);
    for (i=1; i<=n; i++){
        scanf("%d",&x);
        a[i]=x-y;
        y=x;
    }
    build(1,1,n);
    while (t--){
        scanf("%d",&b);
        if (b==1){
            scanf("%d%d%d%d",&x,&y,&k,&d);
            update(1,1,n,x,x,k);
            if (x<y) update(1,1,n,x+1,y,d);
            if (y<n) update(1,1,n,y+1,y+1,-(k+(y-x)*d));
        }
        if (b==2){
            scanf("%d",&x);
            printf("%d\n",query(1,1,n,1,x));
        }
    }
    return 0;
}

洛谷 P1558 色板游戏

题目背景

阿宝上学了，今天老师拿来了一块很长的涂色板。

题目描述

色板长度为L，L是一个正整数，所以我们可以均匀地将它划分成L块1厘米长的小方格。并从左到右标记为1, 2, … L。

现在色板上只有一个颜色，老师告诉阿宝在色板上只能做两件事：

  1. “C A B C” 指在A到 B 号方格中涂上颜色 C。
  2. “P A B” 指老师的提问：A到 B号方格中有几种颜色。

学校的颜料盒中一共有 T 种颜料。为简便起见，我们把他们标记为 1, 2, … T. 开始时色板上原有的颜色就为1号色。 面对如此复杂的问题，阿宝向你求助，你能帮助他吗？

输入输出格式

输入格式：

第一行有3个整数 L (1 <= L <= 100000), T (1 <= T <= 30) 和 O (1 <= O <= 100000)。 在这里O表示事件数。
接下来 O 行, 每行以 “C A B C” 或 “P A B” 得形式表示所要做的事情(这里 A, B, C 为整数, 可能A> B，这样的话需要你交换A和B)

输出格式：

对于老师的提问，做出相应的回答。每行一个整数。

看着看着就睡着了，醒了以后发现这题这么水，人在困的时候会变傻？

这题看上去好吓人啊，但第二眼看就可以发现t<=30，那么我们就可以状态压缩一下，如果一个数二进制的第i位为1，则这个数代表的区间里有第i个颜色的格子。
状压完毕。
之后我们再来看怎么套到线段树上，无非就是确定上推和下推规则，先看上推，我们可以直接按位于一下（因为只要求左右区间一个有这种颜色），再来下推，由于颜色可以覆盖，那么直接把原来的值给覆盖掉，lazy标记也是如此。
上代码：

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
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll sum[400001],n,t,c,i,ad[400001];
inline void pushup(ll rt){
    sum[rt]=sum[rt<<1]|sum[rt<<1|1];
}
inline void build(ll rt,ll l,ll r){
    if (l==r){
        sum[rt]=1<<1;
        return;
    }
    int m=(l+r)>>1;
    build(rt<<1,l,m);
    build(rt<<1|1,m+1,r);
    pushup(rt);
}
inline void pushdown(ll rt,ll l,ll r){
    if (ad[rt]){
        sum[rt<<1]=(1<<ad[rt]);
        sum[rt<<1|1]=(1<<ad[rt]);
        ad[rt<<1]=ad[rt];
        ad[rt<<1|1]=ad[rt];
        ad[rt]=0;
    }
}
inline void update(ll rt,ll l,ll r,ll x,ll y,ll k){
    if (l>y||x>r) return;
    if (x<=l&&r<=y){
        sum[rt]=(1<<k);
        ad[rt]=k;
        return;
    }
    pushdown(rt,l,r);
    ll m=(l+r)>>1;
    if (m>=x) update(rt<<1,l,m,x,y,k);
    if (m<y) update(rt<<1|1,m+1,r,x,y,k);
    pushup(rt);
}
inline int query(ll rt,ll l,ll r,ll x,ll y){
    if (l>y||x>r) return 0;
    if (x<=l&&r<=y)    return sum[rt];
    pushdown(rt,l,r);
    ll m=(l+r)>>1,ans=0;
    if (m>=x) ans|=query(rt<<1,l,m,x,y);
    if (m<y) ans|=query(rt<<1|1,m+1,r,x,y);
    return ans;
}
int main(){
    char u; ll x,y,k;
    scanf("%lld%lld%lld",&n,&c,&t);
    build(1,1,n);
    while (t--){
        cin>>u;
        if(u=='C'){
            scanf("%lld%lld%lld",&x,&y,&k);
            if (x>y) swap(x,y);
            update(1,1,n,x,y,k);
        }
        else{
            scanf("%lld%lld",&x,&y);
            if (x>y) swap(x,y);
            ll p=query(1,1,n,x,y),ans=0;
            for (i=1; i<=c; i++) if (p&(1<<i)) ans++;
            printf("%lld\n",ans);
        }
    }
    return 0;
}

洛谷 P1637 三元上升子序列

题目描述

Erwin最近对一种叫”thair”的东西巨感兴趣。。。

在含有n个整数的序列a1,a2……an中，

三个数被称作”thair”当且仅当i<j<k且ai<aj<ak

求一个序列中”thair”的个数。

输入输出格式

输入格式：

开始一个正整数n,

以后n个数a1~an。

输出格式：

“thair”的个数

首先，n2的做法显而易见，枚举三元组中间那个点，在它两边找比他小和大的数的个数乘起来（这个暴力有60！），我们可以发现，这个东西就是逆序对。

然后我们可以用线段树或树状数组维护一个桶，以求一个数x前面比它小的数为例，就是在1到x之间求和，然后再把x加入桶里。

由于数据范围比较大，我们需要离散化，一定有数字相同，所以我们要去重（蜜汁押韵）

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
struct node{
    ll rank,z;
}a[30001];
ll b[30001],n,i,o[200001],ans,c[30001],j;
inline bool cmp(node c,node d){
    return c.z<d.z;
}
inline void pushup(ll rt){
    o[rt]=o[rt<<1]+o[rt<<1|1];
}
void update(ll rt,ll l,ll r,ll x){
    if (l>x||r<x) return;
    if (l==x&&r==x){
        o[rt]++;
        return;
    }
    ll m=(l+r)>>1;
    if (x<=m) update(rt<<1,l,m,x);
    if (x>m) update(rt<<1|1,m+1,r,x);
    pushup(rt);
}
ll query(ll rt,ll l,ll r,ll x,ll y){
    if (l>y||x>r) return 0;
    if (x<=l&&r<=y)    return o[rt];
    ll m=(r+l)>>1,ret=0;
    if (x<=m) ret+=query(rt<<1,l,m,x,y);
    if (m<y) ret+=query(rt<<1|1,m+1,r,x,y);
    return ret;
}
int main(){
    scanf("%lld",&n);
    for (i=1; i<=n; i++){
        scanf("%lld",&a[i].z);
        a[i].rank=i;
    }
    sort(a+1,a+n+1,cmp);
    j=1;
    for (i=1; i<=n; i++){
        b[a[i].rank]=j;
        if (a[i].z!=a[i+1].z) j++;
    }
    j--;
    for (i=1; i<=n-1; i++){
        update(1,1,n,b[i]);
        if (b[i]==1) continue;
        c[i]=query(1,1,n,1,b[i]-1);
    }
    memset(o,0,sizeof(o));
    for (i=n; i>=2; i--){
        update(1,1,n,b[i]);
        if (b[i]==j) continue;
        ans+=c[i]*query(1,1,n,b[i]+1,n);
    }
    printf("%lld",ans);
    return 0;
}

洛谷 P4145 上帝造题的七分钟2 / 花神游历各国

题目描述

“第一分钟，X说，要有数列，于是便给定了一个正整数数列。

第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。

第三分钟，k说，要能查询，于是便有了求一段数的和的操作。

第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。

第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。

第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。”

——《上帝造题的七分钟·第二部》

所以这个神圣的任务就交给你了。

输入输出格式

输入格式：

第一行一个整数 n ，代表数列中数的个数。

第二行 n 个正整数，表示初始状态下数列中的数。

第三行一个整数 m ，表示有 m 次操作。

接下来 m 行每行三个整数k,l,r，

  • k=0表示给 [l,r] 中的每个数开平方(下取整)
  • k=1表示询问 [l,r] 中各个数的和。

数据中有可能 l>r ，所以遇到这种情况请交换l和r。

输出格式：

对于询问操作，每行输出一个回答。

说明

对于30%的数据，1≤n,m≤1000 ，数列中的数不超过 32767 。

对于100%的数据，1≤n,m≤100000 ，1≤l,r≤n ，数列中的数大于0 ，且不超过 10^12 。

注意l有可能大于r，遇到这种情况请交换l,r。

区间开平方？？？这个。。我这个蒟蒻只能想到暴力了。

那我们就考虑优化这个暴力好了，我们发现这个开平方只要求向下取整，那么开到最小也只会变成一，于是如果一个区间内只有一我们就不开了。

怎么判断一个区间是不是只有一呢？由于都是正整数，我们可以考虑最大值，主要是可以和区间和一起维护，而且由于我们是暴力修改，也不用下推。

那么我们就可以用线段树切了这道题。

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
#include<cmath>
#include<cstdio>
#include<iostream>
#define ll long long
#define re register
#ifdef ONLINE_JUDGE
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){if(A==B){B=(A=ss)+fread(ss,1,1<<17,stdin);if(A==B)return EOF;}return*A++;}
template<class T>inline void read(T&x){
    static char c;static int y;
    for(c=gc(),x=0,y=1;c<48||57<c;c=gc())if(c=='-')y=-1;
    for(;48<=c&&c<=57;c=gc())x=((x+(x<<2))<<1)+(c^'0');
    x*=y;
}
#else
void read(ll&x){scanf("%lld",&x);}
#endif
using namespace std;
ll n,a[100001],t,sum[400001],maxn[400001];
inline void pushup(ll rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    maxn[rt]=max(maxn[rt<<1],maxn[rt<<1|1]);
}
void build(ll rt,ll l,ll r){
    if (l==r){
        sum[rt]=a[l];
        maxn[rt]=a[l];
        return;
    }
    ll m=(l+r)>>1;
    build(rt<<1,l,m);
    build(rt<<1|1,m+1,r);
    pushup(rt);
}
void update(ll rt,ll l,ll r,ll x,ll y){
    if (x>r||l>y) return;
    if (l==r){
        sum[rt]=sqrt(sum[rt]);
        maxn[rt]=sqrt(maxn[rt]);
        return;
    }
    ll m=(l+r)>>1;
    if(maxn[rt<<1]>1&&m>=x) update(rt<<1,l,m,x,y);
    if (maxn[rt<<1|1]>1&&m<y) update(rt<<1|1,m+1,r,x,y);
    pushup(rt);
}
ll query(ll rt,ll l,ll r,ll x,ll y){
    if (l>y||x>r) return 0;
    if (x<=l&&r<=y) return sum[rt];
    ll m=(l+r)>>1,ret=0;
    if (m>=x) ret+=query(rt<<1,l,m,x,y);
    if (m<y) ret+=query(rt<<1|1,m+1,r,x,y);
    return ret;
}
int main(){
    ll b,x,y;
    read(n);
    for (re int i=1; i<=n; i++) read(a[i]);
    read(t);
    build(1,1,n);
    while (t--){
        read(b); read(x); read(y);
        if (x>y) swap(x,y);
        if (!b)
            update(1,1,n,x,y);
        else
            printf("%lld\n",query(1,1,n,x,y));
    }
    return 0;
}

洛谷 P4344 [SHOI2015]脑洞治疗仪

题目描述

曾经发明了自动刷题机的发明家 SHTSC 又公开了他的新发明：脑洞治疗仪——一种可以治疗他因为发明而日益增大的脑洞的神秘装置。

为了简单起见，我们将大脑视作一个 01 序列。 1 代表这个位置的脑组织正常工作， 0 代表这是一块脑洞。

1
1      0      1      0      0      0      1      1      1      0

脑洞治疗仪修补某一块脑洞的基本工作原理就是将另一块连续区域挖出，将其中正常工作的脑组织填补在这块脑洞中。（所以脑洞治疗仪是脑洞的治疗仪？）

例如，用上面第 8 号位置到第 10 号位置去修补第 1 号位置到第 4 号位置的脑洞，我们就会得到：

1
1      1      1      1      0      0      1      0      0      0

如果再用第 1 号位置到第 4 号位置去修补第 8 号位置到第 10 号位置：

1
0      0      0      0      0      0      1      1      1      1

这是因为脑洞治疗仪会把多余出来的脑组织直接扔掉。

如果再用第 7 号位置到第 10 号位置去填补第 1 号位置到第 6 号位置：

1
1      1      1      1      0      0      0      0      0      0

这是因为如果新脑洞挖出来的脑组织不够多，脑洞治疗仪仅会尽量填补位置比较靠前的脑洞。

假定初始时 SHTSC 并没有脑洞，给出一些挖脑洞和脑洞治疗的操作序列，你需要即时回答 SHTSC 的问题：在大脑某个区间中最大的连续脑洞区域有多大。

输入输出格式

输入格式：

第一行两个整数 n 、m，表示 SHTSC 的大脑可分为从 1 到 n 编号的 n 个连续区域，有 m 个操作。

以下 m 行每行是下列三种格式之一：

  • 0 l r ：SHTSC 挖了一个范围为 [l,r] 的脑洞。
  • 1 l_0 r_0 l_1 r_1 ：SHTSC 进行了一次脑洞治疗，用从 l_0 到 r_0 的脑组织修补 l_1 到 r_1 的脑洞。
  • 2 l r ：SHTSC 询问 [l,r] 区间内最大的脑洞有多大。

上述区间均在 [1,n] 范围内。

输出格式：

对于每个询问，输出一行一个整数，表示询问区间内最大连续脑洞区域有多大。

调了将近一个下午终于A了这道题，似乎没有我想的那么难？？？

肯定是要用线段树的，那我们来看怎么实现。

0操作：区间修改，把板子写上改一下，完。。

1操作：首先模拟题意，把l0到r0的脑细胞取出来（区间求和+区间修改），然后在l1到r1区间找出几个连续的0把脑细胞补上

怎么找0呢？首先暴力肯定是不行的，由于连续最长的0满足单调性，我们可以二分查找。

而这个二分还有一个前提就是当前序列的起点得是0，不然怎么也找不到。

那怎么办呢？由于起点不是零就是一，我们可以先二分找以起点开头连续最长的1序列，然后把它的终点后面一个元素（一定是0）作为0序列的起点，这样就找到一个以当前起点连续最长的0，然后把它补上（区间修改成一）。

这是如果还能补，我们就又面临当时的那个问题，循环一下就好了。

2操作：我们会了一操作，这个自然也会了。

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
#include<cstdio>
#include<iostream>
#ifdef ONLINE_JUDGE
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){if(A==B){B=(A=ss)+fread(ss,1,1<<17,stdin);if(A==B)return EOF;}return*A++;}
template<class T>inline void read(T&x){
    static char c;static int y;
    for(c=gc(),x=0,y=1;c<48||57<c;c=gc())if(c=='-')y=-1;
    for(;48<=c&&c<=57;c=gc())x=((x+(x<<2))<<1)+(c^'0');
    x*=y;
}
#else
void read(int &x){scanf("%d",&x);}
#endif
using namespace std;
int ad[800001],sum[800001],n,t;
inline void write(int x){if(x>9) write(x/10);putchar(x%10^48);}
inline void pushup(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int rt,int l,int r){
    if (l==r){
        sum[rt]=1;
        return;
    }
    int m=(l+r)>>1;
    build(rt<<1,l,m);
    build(rt<<1|1,m+1,r);
    pushup(rt);
}
inline void pushdown(int rt,int l,int r){
    if (ad[rt]){
        int m=(l+r)>>1;
        ad[rt]--;
        sum[rt<<1]=ad[rt]*(m-l+1);
        sum[rt<<1|1]=ad[rt]*(r-m);
        ad[rt<<1]=ad[rt]+1;
        ad[rt<<1|1]=ad[rt]+1;
        ad[rt]=0;
    }
}
void update(int rt,int l,int r,int x,int y,int k){
    if (l>y||x>r) return;
    if (x<=l&&r<=y){
        ad[rt]=k+1;
        sum[rt]=k*(r-l+1);
        return;
    }
    pushdown(rt,l,r);
    int m=(l+r)>>1;
    if (m>=x) update(rt<<1,l,m,x,y,k);
    if (m<y) update(rt<<1|1,m+1,r,x,y,k);
    pushup(rt);
}
int query(int rt,int l,int r,int x,int y){
    if (l>y||x>r) return 0;
    if (x<=l&&r<=y) return sum[rt];
    pushdown(rt,l,r);
    int m=(l+r)>>1,ret=0;
    if (m>=x) ret+=query(rt<<1,l,m,x,y);
    if (m<y) ret+=query(rt<<1|1,m+1,r,x,y);
    return ret;
}
inline int ef(int x,int y,int k){
    int l=0,r=y-x,mid;
    if (x>y) return -1;
    while (l<=r){
        mid=(l+r)>>1;
        if (query(1,1,n,x,x+mid)==k*(mid+1)) l=mid+1;
        else r=mid-1;
    }
    return l;
}
int main(){
    int x,y,b,c,d;
    read(n); read(t);
    build(1,1,n);
    while (t--){
        read(b),read(x),read(y);
        if (b==0){
            update(1,1,n,x,y,0);
        }
        if (b==1){
            read(c),read(d);
            int num=query(1,1,n,x,y),p=0;
            update(1,1,n,x,y,0);
            if (num>=(d-c+1)-query(1,1,n,c,d)){
                update(1,1,n,c,d,1); continue;
            }
            if (num==0) continue;
            while (1){
                if (query(1,1,n,c,c)==1){
                    p=ef(c,d,1); c+=p; 
                }
                p=ef(c,d,0);
                if (p==-1) break;
                if (p>num){
                    update(1,1,n,c,c+num-1,1);
                    break;
                }
                else{
                    update(1,1,n,c,c+p-1,1);
                    num-=p; c+=p;
                }
            }
        }
        if (b==2){
            int ans=0,p=0;
            while (1){
                if (query(1,1,n,x,x)==1){
                    p=ef(x,y,1); x+=p;
                }
                p=ef(x,y,0);
                if (p==-1) break;
                ans=max(ans,p);
                x+=p; if (x>y) break;
            }
            write(ans); puts("");
        }
    }
    return 0;
}

洛谷P1712 [NOI2016]区间

题目描述

在数轴上有 N 个闭区间 [l1,r1],[l2,r2],…,[ln,rn] 。现在要从中选出 M 个区间，使得这 M 个区间共同包含至少一个位置。换句话说，就是使得存在一个 x ，使得对于每一个被选中的区间 [li,ri] ，都有 li≤x≤ri 。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li ，即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1 。

输入输出格式

输入格式：

第一行包含两个正整数 N,M 用空格隔开，意义如上文所述。保证 1≤M≤N

接下来 N 行，每行表示一个区间，包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。

N<=500000,M<=200000,0≤li≤ri≤109

输出格式：

只有一行，包含一个正整数，即最小花费。

首先我们肯定知道，如果要添加一个区间的话肯定是区间加的，那我一开始的想法就是找到被覆盖m次以上的点，同时在覆盖的时候记下每个点所在的最大和最小的区间。

然而这个算法很难实现，每个点在的最大和最小的区间难以用线段树维护。

那我们换一个做法，枚举能构成答案的区间，，这是个N2的步骤，为了方便计算答案，我们先对区间按长度排个序，这样我们就有一个N2 log N的算法。

接下来考虑优化，想一下前面那个算法有什么浪费的地方？

假设我们在从第i个区间选起，一直选了j个区间，此时符合要求了，我们选完收工，线段树清零。

到了第i+1个区间，好像也至少要选到第j个区间，这么一看，我们只要把第i个区间删了就好了。（有点像滑动窗口？）

这样大概就完了吗，还有几个小问题。

Q：怎么判断是否有点被覆盖了m次？

A：这个可以维护一个最大值，这样只要看根节点就好了，都不用写查询函数。

Q：为什么你没有说离散化和去重？

A：这。。。有人会忘吗？

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
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
#define re register
#ifdef ONLINE_JUDGE
char ss[1<<17],*A=ss,*B=ss;
inline char gc(){if(A==B){B=(A=ss)+fread(ss,1,1<<17,stdin);if(A==B)return EOF;}return*A++;}
template<class T>inline void read(T&x){
    static char c;static int y;
    for(c=gc(),x=0,y=1;c<48||57<c;c=gc())if(c=='-')y=-1;
    for(;48<=c&&c<=57;c=gc())x=((x+(x<<2))<<1)+(c^'0');
    x*=y;
}
#else
void read(ll&x){scanf("%lld",&x);}
#endif
using namespace std;
struct node{
    ll l,r,z;
}qg[500001];
ll a[1500010],sum[4000010],ad[4000010];
ll n,m,tail,head,ans,size,minn,maxn;
inline bool cmp(node c,node d){
    return c.z<d.z;
}
inline void pushdown(ll rt){
    if (ad[rt]){
        sum[rt<<1]+=ad[rt];
        sum[rt<<1|1]+=ad[rt];
        ad[rt<<1]+=ad[rt];
        ad[rt<<1|1]+=ad[rt];
        ad[rt]=0;
    }
}
void update(ll rt,ll l,ll r,ll x,ll y,ll k){
    if (x>r||l>y) return;
    if (x<=l&&r<=y){
        ad[rt]+=k;
        sum[rt]+=k;
        return;
    }
    pushdown(rt);
    ll mid=(l+r)>>1;
    update(rt<<1,l,mid,x,y,k);
    update(rt<<1|1,mid+1,r,x,y,k);
    sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}
int main(){
    ll x,y;
    read(n); read(m);
    for (re int i=1; i<=n; i++){
        read(x); read(y);
        a[i*2]=x; a[i*2+1]=y;
        qg[i].l=x; qg[i].r=y; qg[i].z=y-x;
    }
    sort(a+1,a+n*2+2);
    size=unique(a+1,a+n*2+1)-(a+1);
    sort(qg+1,qg+n+1,cmp);
    for (re int i=1; i<=n; i++){
        qg[i].l=lower_bound(a+1,a+size+1,qg[i].l)-a;
        qg[i].r=lower_bound(a+1,a+size+1,qg[i].r)-a;
        minn=min(minn,qg[i].l); maxn=max(maxn,qg[i].r);
    }
    head=0; tail=0;
    ans=1e9;
    while (tail<n){
        while (sum[1]<m&&tail<=n){
        tail++; update(1,minn,maxn,qg[tail].l,qg[tail].r,1);}
        if (sum[1]<m) break;
        while (sum[1]>=m&&tail>=head){
        head++; update(1,minn,maxn,qg[head].l,qg[head].r,-1);}
        ans=min(ans,qg[tail].z-qg[head].z);
    }
    if (ans==1e9) ans=-1;
    printf("%lld",ans);
    return 0;
}

本文标题:线段树练习（也有树状数组）

文章作者:Taduro

发布时间:2018年12月11日 - 12时40分

最后更新:2018年12月11日 - 18时19分

原始链接:http://dftyem.github.io/2018/12/11/线段树练习（也有树状数组）/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 线段树练习（也有树状数组）
    1. 1.1. 洛谷 P2184 贪婪大陆
    2. 1.2. 洛谷 P3870 [TJOI2009]开关+P2846 [USACO08NOV]光开关Light Switching+P2574 XOR的艺术（三道重题）
    3. 1.3. 洛谷 P1471 方差
    4. 1.4. 洛谷 P1438 无聊的数列
    5. 1.5. 洛谷 P1558 色板游戏
    6. 1.6. 洛谷 P1637 三元上升子序列
    7. 1.7. 洛谷 P4145 上帝造题的七分钟2 / 花神游历各国
    8. 1.8. 洛谷 P4344 [SHOI2015]脑洞治疗仪
    9. 1.9. 洛谷P1712 [NOI2016]区间
,
载入天数...载入时分秒... 字数统计：75.7k