线段树应用

摘要

啃一下线段树的课件。不过 SYF 是真的强,放一个课件中的 Scene:

提起线段树,大家肯定想起了那端令人窒息的经历:

  1. 看题:WOC,树套树套树套树?
  2. 写题:TMD,这得写上一年啊!
  3. 看榜:报警了,为什么高中生这么快就写完了?
  4. 提交:天呐我怎么 WA 了,这用头调啊!
  5. 赛后:为什么题解都是 “树套树套树套树即可”?
  6. 反思:emmmm,我一定要找一个写数据结构的队友。

非常遗憾,SYF 作为一名曾 OI 选手,他每次看到线段树都十分开心:

  1. 看题:裸题,树套树套树套树即可!
  2. 写题:比想起来好写多了,400 行就写完了!
  3. 看榜:奇怪,怎么还没有队过?
  4. 提交:哎,好无奈,又是一血……
  5. 赛后:线段树还有我不会做的?
  6. 反思:为什么这场不多来几道呢?

emmmm

简单应用

未被覆盖区间

[HihoCoder1079] 离散化

若干个区间按时间顺序放下,问最后有多少个区间没有被遮挡。

L 的范围较大,考虑离散化,区间长度降为 .

对每个区间,打 log 个标记。查询的时侯判断是否有标记即可。

#include<bits/stdc++.h>
using namespace std;

const int SZ=500005;
int n,l,tot,pst[SZ][2];
int a[SZ],cnt,ans;

struct my_hash_map{
    struct data{int u,v,nex;};
    data e[SZ];
    int head[SZ],cnt;
    int hash(int u){return u%SZ;}
    int& operator[](int u){
        int hu=hash(u);
        for(int i=head[hu];i;i=e[i].nex)if(e[i].u==u)return e[i].v;
        e[++cnt]=(data){u,0,head[hu]};
        return head[hu]=cnt,e[cnt].v;
    }
};
my_hash_map h;

int s[1<<19],upd_f;
int vio_upd(int l,int r,int rt){
    s[rt]=1;
    if(l==r)return 0;
    int mid=(l+r)>>1;
    vio_upd(l,mid,rt<<1),vio_upd(mid+1,r,rt<<1|1);
}
int lst_upd(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R){
        if(s[rt]==0)upd_f=true,vio_upd(l,r,rt);
        return 0;
    }
    int mid=(l+r)>>1;
    if(!(R<l||mid<L))lst_upd(L,R,l,mid,rt<<1);
    if(!(R<mid+1||r<L))lst_upd(L,R,mid+1,r,rt<<1|1);
    s[rt]=(s[rt<<1]&&s[rt<<1|1]);
}


int main(){
    scanf("%d%d",&n,&l);
    a[cnt]=++l;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&pst[i][0],&pst[i][1]);
        a[++cnt]=++pst[i][0],a[++cnt]=++pst[i][1];
    }
    sort(a,a+cnt+1);
    for(int i=0;i<=cnt;i++)    if(a[i]!=a[i-1])h[a[i]]=++tot;
    for(int i=n;i>=1;i--){
        upd_f=false;
        lst_upd(h[pst[i][0]],h[pst[i][1]]-1,1,h[l],1);
        ans+=upd_f;
    }
    printf("%d",ans);
    return 0;
}

维护段

给定长度为 n 的序列 A,Q 次操作,两种类型:

  1. 1 x v 将 A_x 变成 v.
  2. 2 l r 询问区间 [l,r] 有多少段不同的数。比如 2233224 有 4 段不同的数。

.

每个结点维护段数,区间左右端的数。

对于操作 1,根据变成的数以及左右两边的树数判断段数增减。合并时,根据左右端点的数判断增减。

对于操作 2,直接查询。

矩形面积并

平面上有 n 个矩形 ,求矩形面积并。 .

矩形面积并.png

将矩形拆分成上下界 ,并排序。从上往下遍历,遇到上界就添加区间覆盖,遇到下界就撤销区间覆盖。每次查询全局被覆盖过的区间,高度为当前纵坐标与下一个界的距离。

#include<bits/stdc++.h>
using namespace std;
int n,cnt,tot;
struct data{int x,l,r,v;};//row,l,r,up or down
data rtg[202];
bool cmp(data d1,data d2){return d1.x<d2.x;}

const int SZ=1<<18;
int s[SZ],tg[SZ];

void push_down(int l,int r,int rt){
    int mid=(l+r)>>1;
    s[rt<<1]+=tg[rt]*(mid-l+1),tg[rt<<1]+=tg[rt];
    s[rt<<1|1]+=tg[rt]*(r-mid),tg[rt<<1|1]+=tg[rt];
    tg[rt]=0;
}
void push_up(int rt){s[rt]=s[rt<<1]+s[rt<<1|1];}

int lst_add(int L,int R,int v,int l,int r,int rt){
    if(R<l||r<L)return 0;
    if(L<=l&&r<=R)return tg[rt]+=v,s[rt]+=v*(r-l+1);
    push_down(l,r,rt);
    int mid=(l+r)>>1;
    lst_add(L,R,v,l,mid,rt<<1),lst_add(L,R,v,mid+1,r,rt<<1|1);
    push_up(rt);
}
int lst_sum(int L,int R,int l,int r,int rt){
    if(R<l||r<L)return 0;
    if(L<=l&&r<=R)return s[rt];
    push_down(l,r,rt);
    int mid=(l+r)>>1;
    return lst_sum(L,R,l,mid,rt<<1)+lst_sum(L,R,mid+1,r,rt<<1|1);
}

int main(){
    scanf("%d",&n);
    for(int i=1,a,b,c,d;i<=n;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        rtg[++cnt]=(data){a,b,d,1};//up
        rtg[++cnt]=(data){c,b,d,-1};//down
    }
    sort(rtg+1,rtg+cnt+1,cmp);
    for(int i=1;i<=n;i++){
        lst_add(rtg[i].l,rtg[i].r,rtg[i].v,1,100000,1);
        tot+=lst_sum(1,100000,1,100000,1)*(rtg[i+1].x-rtg[i].x);
    }
    printf("%d",tot);
    return 0;
}

一类性质相似的应用

区间取模1

支持区间对x取模,询问区间和。

每一次取模,如果这个数有变换变化,至少变成原来的一半。每次暴力找到需要修改的数,可以维护区间最大值来辅助。复杂度

区间取模2

支持区间对 取模,区间覆盖,询问区间和。

如果直接做的话,区间覆盖会大大增加复杂度。每一次区间覆盖后,一段区间就变成了相同的数。于是我们考虑把它们缩成一个点。这样在区间取模的时侯可能会分裂一个点成两个部分。每一次操作增加 个点,而每个点更改 次。用平衡树维护区间和,复杂度仍是

区间取欧拉函数

支持区间取欧拉函数,区间覆盖,询问区间和。

欧拉函数由一个性质:奇数变偶数,偶数除以2。这样就转化成了上一道题了。复杂度仍是 的。

区间开根1

LG4145 花神游历各国

给定长度为 n 的序列 A,Q 次操作,两种类型:

  1. 1 x v 区间求和
  2. 2 l r 将区间内每个数开平方并向下取整。

.

考虑到 的范围以内,开 次方后就变成了 1。因此维护区间最大值,当最大值是 1 时,就直接返回。区间求和照常维护。复杂度

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100005;
ll n,m,a[N];
ll s[1<<18],mx[1<<18];

inline ll max(ll a,ll b){return a>b?a:b;}
inline void push_up(ll rt){
    s[rt]=s[rt<<1]+s[rt<<1|1];
    mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
}
ll lst_build(ll l,ll r,ll rt){
    if(l==r)return s[rt]=mx[rt]=a[l];
    ll mid=(l+r)>>1;
    lst_build(l,mid,rt<<1),lst_build(mid+1,r,rt<<1|1);
    push_up(rt);
}
ll vio_sqrt(ll l,ll r,ll rt){
    if(mx[rt]==1)return 0;
    if(l==r)return s[rt]=sqrt(s[rt]),mx[rt]=s[rt];
    ll mid=(l+r)>>1;
    vio_sqrt(l,mid,rt<<1),vio_sqrt(mid+1,r,rt<<1|1);
    push_up(rt);
}
ll lst_sqrt(ll L,ll R,ll l,ll r,ll rt){
    if(R<l||r<L)return 0;
    if(L<=l&&r<=R)return vio_sqrt(l,r,rt);
    ll mid=(l+r)>>1;
    lst_sqrt(L,R,l,mid,rt<<1),lst_sqrt(L,R,mid+1,r,rt<<1|1);
    push_up(rt);
}
ll lst_sum(ll L,ll R,ll l,ll r,ll rt){
    if(R<l||r<L)return 0;
    if(L<=l&&r<=R)return s[rt];
    ll mid=(l+r)>>1;
    return lst_sum(L,R,l,mid,rt<<1)+lst_sum(L,R,mid+1,r,rt<<1|1);
}
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
    scanf("%lld",&m);
    lst_build(1,n,1);
    for(ll i=1,x,p,q;i<=m;i++){
        scanf("%lld%lld%lld",&x,&p,&q);
        if(p>q)p^=q^=p^=q;
        if(x==1)printf("%lld\n",lst_sum(p,q,1,n,1));
        else lst_sqrt(p,q,1,n,1);
    }
    return 0;
}

区间开根2

支持区间加,区间开根号,询问区间和。

上一道题抓住的是整数开根的值域范围求解,注意到对两个数开根后,这两个数的差会减少,即 。也就是说一组数据在开根后,这组数据的离散程度会减小,趋于统一。而区间加不会影响这个区间内的数的离散程度。于是不难想到以数的离散程度做为暴力的条件。

具体地说,如果一段区间的最大值和最小值的差小于等于1,那么我们再记录一下这个区间的最大值个数,就可以直接开方了。如果差大于1呢?暴力两边DFS即可。这样做的复杂度? 的。证明考虑差分。

一类神仙的应用

区间 GCD

支持区间加,询问区间

不具有可加性。

考虑单点加的话怎么做?直接暴力更新。更新了子结点就在父结点重新做

怎么把区间加转化为单点加?差分。

差分能否保证正确性?根据欧几里德算法,辗转相减 不变。问题转化为单点修改区间求

复杂度 .(修改的时侯是 的)

区间加斐波那契

Codeforces FF Div1 C

定义 为斐波那契数列第 项,对于序列 两种操作:

  1. 0 l r 加上 .
  2. 1 l r 区间求和,答案模 .

考虑斐波那契数列的通项公式

由于是对 取模,想到 5 的二次剩余:

于是可以得到

显然这是两个等比数列相减。因此区间加的时侯,对 log 个区间对应的结点,记录首项和公比。查询的时侯利用等比数列求和公式查询即可。(公比相同的等比数列的首项是可加的)

如果常数过大,可以预处理 的若干次幂减少询问。

复杂度 .

最大 k 子段和

Codeforces 172 Div1 D

序列 A,两种操作:

  1. 0 l r v 区间覆盖
  2. 1 l r k 在区间中找 k 个不相交的子段,使得这 k 个子段的总和最大. .

考虑当 k=1 时。即为最大子段和。每个区间结点维护左边最大,右边最大,最大子段和和区间和即可。考虑覆盖操作,记录一个覆盖标记,下传的时侯更新即可。

如果 k>1 呢?有一个贪心结论:

  1. 找出最大子段和,累加到答案中
  2. 把最大子段的区间的点权乘 -1
  3. 重复上述操作 k 次,一旦最大子段和是负数,停止。

正确性可以用费用流验证,然而笔者并不会。复杂度 .

等差子序列

BZOJ2124

n 的排列 A,问是否存在 使得 构成等差数列(Yes or no)

只需验证是否有 l=3 的情况即可,即寻找 . 相当于我们要枚举 j,判断是否存在一个数 t,使得 左边, 右边。但是这个过程的复杂度是不低的,既然题目不要求我们输出方案,我们考虑:是否无解。

我们维护一个序列 a。对于 ,在 左边的 v 的权值标记为 ,在 右边的 v 的权值标记为 1. 当 j 自増的时侯,我们可以单点修改 a 序列以维护。如果对于 j 而言找不到 的等差三元组,说明对于任意 t, 的权值是一样的(分布在 的同侧),即对于区间 ,前者倒序,后者正序,两个下标区间对应在 a 序列中的 01 序列是一样的(以长度短的区间为结束)

因此我们想要判断两个区间的数是否呈互相的倒序排列。把序列倒过来,变成判断两个区间的序列是否相同。使用线段树维护 HASH 值!

区间维护每个结点的正反方向的 HASH 值。单点修改的时侯也维护对应的 HASH 值,然后对每个 做询问,得到 HASH 值。复杂度 .

#include<cstdio>
using namespace std;
const int N=1e4+5,LST=1<<18,BASE=7;
int t,n;
int a[N],b[N];//

int min(int a,int b){return a<b?a:b;}
int h1[LST],h2[LST];// 正反 Hash 值

void init(int u=1,int l=1,int r=n){
    h1[u]=h2[u]=0;
    if(l==r)return;
    int mid=(l+r)>>1;
    init(u<<1,l,mid), init(u<<1|1,mid+1,r);
}
void modify(int pos,int v,int u=1,int l=1,int r=n){//0 变 1 或者 1 变 0
    int a1=pos-l+1,a2=r-pos+1;// 对于正反的相对位置
    h1[u]+=b[a1]*v, h2[u]+=b[a2]*v;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(pos<=mid)modify(pos,v,u<<1,l,mid);
    else modify(pos,v,u<<1|1,mid+1,r);
}
int query1(int L,int R,int u=1,int l=1,int r=n){
    if(L<=l&&r<=R)return h1[u]*b[l-L];
    int mid=(l+r)>>1,res=0;
    if(L<=mid)res+=query1(L,R,u<<1,l,mid);
    if(mid<R)res+=query1(L,R,u<<1|1,mid+1,r);
    return res;
}
int query2(int L,int R,int u=1,int l=1,int r=n){
    if(L<=l&&r<=R)return h2[u]*b[R-r];
    int mid=(l+r)>>1,res=0;
    if(mid<R)res+=query2(L,R,u<<1|1,mid+1,r);
    if(L<=mid)res+=query2(L,R,u<<1,l,mid);
    return res;
}

void go(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    init();// 初始化线段树
    for(int i=1;i<=n;i++)modify(a[i],1);// 初始时,所有权值都在右边
    //a[1] 显然无解,从 2 考虑
    for(int i=2;i<=n;i++){// 从 a[i-1] 变到 a[i]
        modify(a[i-1],-1);//a[i-1] 变成了左边的位置
        int len=min(a[i]-1,n-a[i]);// 序列的长度
        if(!len)continue;// 无解
        int q1=query1(a[i]-len,a[i]-1), q2=query2(a[i]+1,a[i]+len);
        if(q1!=q2){puts("Y");return;}
    }
    puts("N");
}
int main(){
    scanf("%d",&t);
    b[0]=1;
    for(int i=1;i<=10000;i++)b[i]=b[i-1]*BASE;// 自然溢出,对 2^31-1 取模
    while(t--)go();
    return 0;
}

矩阵连通块计数

BZOJ1453

一个 的黑白棋盘。操作:把 的颜色取反,每次操作后分别输出黑白连通块个数(四连通)。 .

如果没有修改操作,那么我们可以使用并查集维护连通块。那么有修改操作呢?

考虑线段树套并查集。对 n 行建立线段树。每个线段树的叶子结点是一个并查集,记录的是那一行的连通情况。同理,每个结点的并查集记录的是第 l 行到第 r 行的连通情况。

在单点修改的时侯,我们 重建该行的并查集。向上合并时只需将 [l,mid] 的下边界和 [mid+1,r] 的上边界合并。合并时用并查集复杂度是 的。总共进行 次合并,总复杂度 .

区间与或

支持区间 or x,区间 and x,询问区间最小值。

按位考虑, 的时侯会修改位。而做这两个操作时,会使得整个区间的数的对应的二进制位变得一样。这样就逐渐使得所有数的二进制位趋于相同。于是不难想到这样的算法。线段树维护这个区间的数相同的位有哪些。区间 或者区间 的时侯,如果影响到的那些位包含在区间相同位中,相当于可以直接做一个区间加的操作。 这样做的复杂度仍是 的。


  转载请注明: Sshwy's Blog 线段树应用

 上一篇
[国家集训队]Middle [国家集训队]Middle
摘要 题意:对于一个数列每次询问 ,求左端点在 右端点在 的区间的中位数的最大值。偶数的情况下标向下取整。 . 对于求这种答案在某一维度上单调的最值问题,
2019.05.21
下一篇 
NOI2005 维护数列 NOI2005 维护数列
摘要 题意:维护一个数列支持 6 种操作:在某一位置插入 / 删除 / 覆盖 / 翻转 / 求和一段数字;求整个数列的最大的连续一段的数字的和。 既然这个序列的形态变化,自然想到平衡树维护。然后,我就调了 6 小时 emmm 打覆盖和翻转
2019.05.21
  目录