线段树专题

___balalida___ · 2021-06-24 17:53:02 · 个人记录

是的，你没看错

提前声明一下，这里的题自评是蓝以下的

如果觉得简单就可以右转A班了

0.线段树

主要考虑三点

区间+区间

tag+tag

区间+tag

其中没有区间修改的话只需要考虑第一个

如果可以在短时间内搞定上面三个，理论上线段树可以维护的是任何东西

如果觉得简单就可以右转B班了

1.normal

直接上题

提前声明一下：并不是所有的题都要用到线段树，不要被线段树限制住思维，不过我可以保证所有题用到的是线段树及一下的数据结构（除非特殊声明）

原因竟然是我不会主席树，不会slay，不会LCT

P1637

三个数被称作thair当且仅当i<j<k且a_i<a_j<a_k

求一个序列中thair的个数

sol

设f[i][j]为以a[j]为结尾的长度为i的上升子序列的个数

对a离散化然后把f[i-1][j]扔进树状数组，查询直接getsum即可

注意：树状数组0位置不能存东西！特判即可

P6186

给你一个序列，有两种操作：交换连续两个，求如果进行k次冒泡排序的逆序对数

sol

c[i]表示第i个数前面有几个比他大的，那么逆序对的数量就是\sum_{i=1}^n c[i]

小于等于k的变为0，其余的减k

这个东西怎么处理呢，开两个“权值”树状数组，一个维护\sum v，一个维护\sum x*v

CF242E XOR on Segment

给你一个序列，每次对区间异或上x或求区间和

sol

这是不是叫2维线段树？不清楚

见到异或，常见操作有拆位和线性基，这题拆位

用cnt[x][p]表示第p位上的该区间的1的个数

对于每一位，区间异或相当于是将区间0变1,1变0，这很好维护

然后求和就是对每一位求和就好了

P6492

这是一道经典的线段树

给你一个01串，每次翻转（0变1,1变0，下同）或查询一个区间的最长相同连续串长度

sol

难在tag+tag（其实也不难）

len[i]：线段树中第 i 个节点所维护的区间的长度；
L[i]：线段树中第 i 个节点所维护的区间的左端点；(0/1)
R[i]：线段树中第 i 个节点所维护的区间的右端点；(0/1)
S[i]：线段树中第 i 个节点所维护的区间的最左端开始最长的符合条件的区间长度（前缀）；
H[i]：线段树中第 i 个节点所维护的区间的最右端开始最长的符合条件的区间长度（后缀）；
ans[i]：线段树中第 i 个节点所维护的区间的最长符合条件的区间长度；

那么这样维护随随便便就可以tag合并了

void pushup(ll rt){
    if(R[LC]^L[RC])ans[rt]=max(H[LC]+S[RC],max(ans[LC],ans[RC]));
    else ans[rt]=max(ans[LC],ans[RC]);
    L[rt]=L[LC];R[rt]=R[RC];
    if(S[LC]==len[LC]&&R[LC]^L[RC])S[rt]=S[LC]+S[RC];
    else S[rt]=S[LC];
    if(H[RC]==len[RC]&&R[LC]^L[RC])H[rt]=H[LC]+H[RC];
    else H[rt]=H[RC];
}

练习：P2894

CF620E New Year Tree

给你一棵树，每个点有颜色，每次操作更改一个子树的颜色或查询一颗子树里面有几种颜色，c<=60

sol

暴力树剖

看到数据范围就可以想到压位

每个（线段树）点存这个区间的颜色集合即可

CF240F TorCoder

给定一个长为n的由a到z组成的字符串,有m次操作，每次操作将[l,r]这些位置的字符进行重排，得到字典序最小的回文字符串，如果无法操作就不进行，求m次操作后的字符串

sol

还是类似二维的？

经典的26颗线段树

对于一段区间，统计其每个字母个数，如果有一个奇数个的就一定放在最中间，否则无法操作

然后就以"aabbcc...ccbbaa"的形式排列字典序最小

那么这26颗线段树维护的是该区间内该字符的数量

每次修改只要全部清零再分到左边右边两段即可

练习：CF558E

CF431E Chemistry Experiment

别看它是一道黑题

1 p x：倒掉试管p的水银修改为x ml。 2 v：将v ml水任意分配至nn支试管里，最小化有水的试管中最大体积，输出这个最小值，这个操作只是一次假想，不会真的把水倒进试管里。

sol

线段树二分和线段树上二分不是同一个东西

线段树二分你可以理解成线段树只是一个黑箱，你在外面二分

而线段树上二分则是在线段树的节点上随机游走

维护一颗权值线段树，以h_i为下标，主要维护两个值，是元素个数和元素和

左边的节点数×mid−左边的元素和是否大于当前的水量来考虑走左边还是右边

走左边就r=mid，否则l=mid+1

记得动态开点

double solve(int rt,ll l,ll r,ll x){
    ll SZ=0,SUM=0;
    while(l!=r){
        ll mid=(l+r)/2;
        if(x>=mid*(SZ+sz[LC])-SUM-sum[LC])l=mid+1,SUM+=sum[LC],SZ+=sz[LC],rt=RC;
        else r=mid,rt=LC;
    }
    return l+(x-(l*(SZ+sz[LC])-SUM-sum[LC]))*1.0/SZ;
}

其实这题也可以二分+树状数组（我没试过）

和冒泡排序那题很相似

都是求<=k的和

用两个树状数组维护就好了

可行性分析：什么都没有，只有常数小（虽说时两个log）

P2184

来道简单题

若 q=1，则表示 UCN 在 [l,r] 这段区间布上一种地雷；
若 q=2，则表示小 FF 询问当前 [l,r] 区间总共有多少种地雷。

sol

我们发现每次埋的地雷都不同，所以可以瞎搞

相当于一些线段，求x位置上有多少条覆盖

很容易想到记录一个起始位置，一个终止位置，即记录[l,r]间有多少个起始点/终止点

然后不难发现这可以用树状数组维护

第一个：维护节点i之前有多少个区间的开头

第二个：维护节点j之前有多少个区间的结尾

不难证明拿sum[i]-sum[j]得到的就是i~j中间地雷的个数

P1438

又一道简单题

1 l r K D：给出一个长度等于 r-l+1 的等差数列，首项为 K，公差为 D，并将它对应加到 [l,r] 范围中的每一个数上。即：令 a_l=a_l+K,a_{l+1}=a_{l+1}+K+D\ldots a_r=a_r+K+(r-l) \times D

2 p：询问序列的第 p 个数的值 a_p

sol

看到单点查询，很容易想到转化成区间查询，差分一次

这样就变成了每次在l位置+K，[l+1,r] +D，然后区间查询

CF992E Nastya and King-Shamans

给定一个序列 a_i，记其前缀和序列为 s_i，有 q个询问，每次单点修改，询问是否存在一个 j 满足 a_i=s_{i-1}，有多解输出任意一个，无解输出 -1

sol

这题做法很多

F1：

首先不难发现这样的数的不超过logA个（指数上涨）

然后我们用线段树记录a_i-s_{i-1}的最大值，由上可得这样的位置少于logA个

还是要用到那个技巧，修改照常

void up(ll rt,ll l,ll r,ll p,ll k){
    if(l==r)return mx[rt]+=k,void();
    pushdown(rt);GM;
    if(p<=mid)up(LC,l,mid,p,k);
    else up(RC,mid+1,r,p,k);
    pushup(rt);
}
void updata(ll rt,ll l,ll r,ll ql,ll qr,ll k){
    if(ql>qr)return;
    if(ql==l&&r==qr){
        lz[rt]+=k;mx[rt]+=k;
        return;
    }GM;pushdown(rt);
    if(qr<=mid)updata(LC,l,mid,ql,qr,k);
    else if(ql>mid)updata(RC,mid+1,r,ql,qr,k);
    else updata(LC,l,mid,ql,mid,k),updata(RC,mid+1,r,mid+1,qr,k);
    pushup(rt);
}
ll query(ll rt,ll l,ll r){
    if(l==r)return mx[rt]==0?l:-1;
    if(mx[rt]<0)return -1;
    GM;pushdown(rt);
    ll tmp=query(LC,l,mid);
    if(tmp!=-1)return tmp;
    return query(RC,mid+1,r);
}

F2:线段树二分

F3:我不会的神仙做法

然而还可以用分块卡过去，我就不说了

CF1000F One Occurrence

给你一个序列，每次查询一个区间内只出现一次的数（多个输出任意一个）

sol

因为这题是主席树的题，我不会，所以暂时咕咕咕

然而我会莫队！

维护一个每个数出现次数，如果出现一次就扔到一个栈里，同时记录这个数的pos

如果这个数出现的次数不再是1，那么交换它和栈顶，弹出即可

然而Y_B_X教了我一种做法。。。

因为只有询问操作，直接离线

按照r排序，对于不同的l，我们让它匹配下一个和他相同的数，若他是最右边的，就是inf

那么查区间最大的最右边位置就好了

这个怎么做呢？遍历右子树，再遍历左子树

Y_B_X的代码：

struct tree{int l,r,mp;}t[N<<1];
void build(int l,int r,int &k){k=++tot;if(l==r)return t[k].mp=l,void();
    int mid=(l+r)>>1;build(l,mid,t[k].l);build(mid+1,r,t[k].r);}
void pushup(int k){if(w[t[t[k].l].mp]<w[t[t[k].r].mp])t[k].mp=t[t[k].l].mp;else t[k].mp=t[t[k].r].mp;}
void update(int l,int r,int k,int pos){if(l==r)return;int mid=(l+r)>>1;
    if(pos<=mid)update(l,mid,t[k].l,pos);else update(mid+1,r,t[k].r,pos);pushup(k);}
int inquiry(int l,int r,int k,int x,int y){
    if(x<=l&&r<=y)return t[k].mp;
    int mid=(l+r)>>1,tmp1=0,tmp2=0;
    if(x<=mid)tmp1=inquiry(l,mid,t[k].l,x,y);
    if(mid<y)tmp2=inquiry(mid+1,r,t[k].r,x,y);
    if(w[tmp1]<w[tmp2])return tmp1;return tmp2;
}
main(){
    scanf("%d",&n);build(1,n,rt);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);nn=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+n+1,a[i])-b;scanf("%d",&m);
    for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),add(y,x,i);w[0]=n+1;
    for(int i=1;i<=n;i++){
        int pp=pre[a[i]];pre[a[i]]=i;
        w[w[i]=pp]=n+1;if(pp)update(1,n,rt,pp);update(1,n,rt,i);
        for(int j=h[i];j;j=nextn[j]){
            int tmp=inquiry(1,n,rt,to[j],i);
            if(w[tmp]<to[j])ans[id[j]]=b[a[tmp]];
        }
    }
    for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}

为什么会想到这种套路呢？因为这样的题还可以是强制在线的，都是这样想然后用主席树处理

练手题：P3567 [POI2014]KUR-Couriers

CF1149C Tree Generator™

给你一棵树的括号序列，输出它的直径，每次修改交换两个括号

sol

引理1.1 若从序列中任取一段连续子序列，从中去掉所有匹配括号后，剩下的括号组成的路径一定为一条链，链长为剩下的子序列长

引理1.2 树上直径长度即为任意区间去掉匹配括号后的长度的最大值

若我们给”(”赋值 +1，给”)”赋值 -1，则：

引理1.3 最长去匹配区间 = 最大的（将区间分成两段）后面的权值和 - 前面的权值和

解释一下

首先括号匹配是完全没用的，直接消掉

那么剩下的只有三种情况，自己手玩就好了

然后怎么处理两个区间的差最大？线段树！

我们选择维护九个变量：区间和，左/右连续选值最大/小值，从左/右连续选值Δ最大值，选择整个区间Δ最大值，无限制连续选值Δ最大值

void pushup(ll rt){
    sum[rt]=sum[LC]+sum[RC];
    lmx[rt]=max(lmx[LC],sum[LC]+lmx[RC]),rmx[rt]=max(rmx[RC],sum[RC]+rmx[LC]);
    lmn[rt]=min(lmn[LC],sum[LC]+lmn[RC]),rmn[rt]=min(rmn[RC],sum[RC]+rmn[LC]);
    la[rt]=max(max(la[LC],la[RC]-sum[LC]),ans[LC]+lmx[RC]);
    ra[rt]=max(max(ra[RC],ra[LC]+sum[RC]),ans[RC]-rmn[LC]);
    ans[rt]=max(ans[LC]+sum[RC],ans[RC]-sum[LC]);//total
    aaa[rt]=max(max(aaa[LC],aaa[RC]),max(la[RC]-rmn[LC],ra[LC]+lmx[RC]));
}

-----------------------------------------CF1422F Boring Queries

给你一个序列，求静态区间lcm

sol

如果这是gcd，就可以直接用区间存，因为gcd只增不减

但是这是lcm，如果不取模的话需要高精度，显然会T掉

有人说有一种套路就是遇到强制在线的考虑离线

对于离线询问，对右端点排序，每往左添加一个数，考虑会不会有贡献

这样对于两个数a_i,a_j(i<j)，质因子p对应的指数分别为x,y,若x<y，则a_i一定不会更新答案。这样的a_i可以直接丢掉

我们发现这非常类似单调栈的过程

但是我们还有区间左端点的限制，这可以用线段树维护一下

回到在线的，可以用主席树

-----------------------CF1004F Sonya and Bitwise OR

CF1114F Please, another Queries on Array?

区间乘求区间乘积的phi

然后a_i \leq 300

sol

这应该是最显眼的事了吧

一看质因子不到60个（真的吗

然后\varphi(x)=\prod{{S_i-1}\over{S_i}}

然后会发现这种个数最多8个，直接预处理

然后发现300内刚好有62个质数，ll刚好存的下

然后暴力压位？没了

注意一定要(1ll<<i)

P4145

区间开平方区间求和

sol

开平方的次数是有限的，1e12的数开方6次就变成了1，所以需要修改的次数实际上很少，用并查集可以跳过小于等于1的数，然后。。。树状数组单点修改即可

ll getf(ll x){return f[x]==x?x:f[x]=getf(f[x]);}
ll lb(ll x){return x&(-x);}
void add(ll i,ll k){for(;i<=N-110;i+=lb(i))c[i]+=k;}
ll gs(ll i){ll sum=0;for(;i>0;i-=lb(i))sum+=c[i];return sum;}
int main(){
    n=read();rep(i,1,n)a[i]=read(),add(i,a[i]);rep(i,1,n+1)f[i]=i;
    drep(___,read(),1){
        opt=read(),l=read(),r=read();if(l>r)swap(l,r);
        if(opt==1)writeln(gs(r)-gs(l-1));
        else if(opt==0)for(ll i=l,t;i<=r;t=sqrt(a[i]),add(i,t-a[i]),a[i]=t,f[i]=((a[i]<=1)?i+1:i),i=(getf(i)==i?i+1:f[i]));
    }
}

P6327

区间加区间sin和

sol

每个点存该对应区间的sincos和就行了，更新时用和差角就行了

CF446C DZY Loves Fibonacci Numbers

区间加斐波那契数列区间和

sol

%NTF

有一种很不常见的方法，貌似是题面里提示的式子

还可以用斐波那契通项式

然后还可以用根号分治？？？

这里

然后会发现在每个线段树区间上加的都是“广义”斐波那契数列

然后维护a1/a2的系数就好了

void pushup(ll rt){sum[rt]=(sum[LC]+sum[RC])%mod;}
void pushdown(ll rt,ll l,ll r){
    if(lz1[rt]==0&&lz2[rt]==0)return;GM;
    sum[LC]=(sum[LC]+f[mid-l+1]*lz1[rt]%mod+(f[mid-l+2]-1)*lz2[rt]%mod)%mod;
    sum[RC]=(sum[RC]+(f[r-l+1]-f[mid-l+1]+mod)*lz1[rt]%mod+(f[r-l+2]-f[mid-l+2]+mod)*lz2[rt]%mod)%mod;
    lz1[LC]=(lz1[LC]+lz1[rt])%mod,lz2[LC]=(lz2[LC]+lz2[rt])%mod;
    lz1[RC]=(lz1[RC]+f[mid-l]*lz1[rt]%mod+f[mid-l+1]*lz2[rt]%mod)%mod;
    lz2[RC]=(lz2[RC]+f[mid-l+1]*lz1[rt]%mod+f[mid-l+2]*lz2[rt]%mod)%mod;
    lz1[rt]=lz2[rt]=0;
}
void updata(ll rt,ll l,ll r,ll ql,ll qr){
    if(ql<=l&&r<=qr){lz1[rt]=(lz1[rt]+f[l-ql+1])%mod,lz2[rt]=(lz2[rt]+f[l-ql+2])%mod,sum[rt]=(sum[rt]+f[r-l+1]*f[l-ql+1]%mod+(f[r-l+2]-1)*f[l-ql+2]%mod)%mod;return;}
    GM;pushdown(rt,l,r);
    if(ql<=mid)updata(LC,l,mid,ql,qr);
    if(qr>mid)updata(RC,mid+1,r,ql,qr);
    pushup(rt);
}

P1471

区间加区间平均数方差

sol

偷一张图（

只需要存区间平方和和区间和就行了

P5142

------------------------------P3300 [SDOI2013]城市规划

gu

sol

P4839

你有一些桶，桶里有一些数，每次往一些桶里扔一个数或求编号在[l,r]的桶中选数的最大异或和

sol

每个节点维护一个线性基就好了，O(nlog^2n)

CF1100F Ivan and Burgers

上题题面一样，但是时间有更高要求

sol

我知道Y_B_X为什么会想到那种做法了。。。

我们还是按r排序。我们令 pos[i] 表示 [l,r] 线性基第 i 位有值的最大的l

处理答案时，如果base[i]有值，且pos[i]\geq l，那么就代表我们可以选择这一位，这样贪心地取，就是答案

结果代码还短的一匹

防挂

CF594D REQ

首先离线白送一个排序

固定r

首先phi的公式是sum*\prod_{p}{{p-1}\over p}

p只算一次

那么问题拆成了两个：求积和后半部分

第一个前缀积就好了

第二个？？？相同的只算一次？？？

想到了HH的项链，直接让树状数组里面全是1，有一个乘一个，记录上次这个质数出现的位置，用map

一旦出现过，就把前面一个乘上逆元

如果你想常数优化，可以记录每个质数的逆元以及phi

CF515E Drazil and Park

你有一个环，每个点有一个权值，则你从一个点到另外一个点的代价就是2(hx+hy)+dist(x,y)

然后每次询问有[x,y]的路是被堵住的，问你最大的代价

sol

这题评分还是虚高

有两种做法，一种细节巨多

F1：

拆了，相当于求一个最大值，一个最小值，且位置不同

就看第一篇题解好了

F2：

两棵树之间的距离算到前面一棵树上

那么久非常套路地：左边最大连续，右边最大连续，最大答案，总和

CF522D Closest Equals

给您一个序列，让你求[l,r]之间一对相同元素的最小距离

sol

想象一下，如果一条线段被另一条线段覆盖，那么这条线段一定更优，直接舍去那条线段

那么我们只考虑一种元素，只需要考虑相邻两个位置组成的线段就行了

然后考虑怎么处理这些线段

sort以后去重，然后只剩下左端点右端点递增的线段，l,r unique

那么可以二分出来区间对应的线段集，ST维护长度即可

CF739C Alyona and towers

动态区间“（半）山峰”序列，区间加

sol

然后还是线段树维护一大堆东西

维护左端点、右端点、左边连续下降、右边连续上升、左边连续山峰、右边连续山峰、区间答案、tag

然后合并？记得分类讨论

void pushup(ll rt){
    L[rt]=L[LC],R[rt]=R[RC];
    lmx[rt]=lmx[LC],rmx[rt]=rmx[RC];
    if(lmx[LC]==len[LC]&&L[RC]<R[LC])lmx[rt]+=lmx[RC];
    if(rmx[RC]==len[RC]&&L[RC]>R[LC])rmx[rt]+=rmx[LC];
    lans[rt]=lans[LC];
    if(rmx[LC]==len[LC]){
        if(R[LC]<L[RC])lans[rt]+=lans[RC];
        if(R[LC]>L[RC])lans[rt]+=lmx[RC];
    }
    else if(lans[LC]==len[LC]&&R[LC]>L[RC])lans[rt]+=lmx[RC];
    rans[rt]=rans[RC];
    if(lmx[RC]==len[RC]){
        if(R[LC]>L[RC])rans[rt]+=rans[LC];
        if(R[LC]<L[RC])rans[rt]+=rmx[LC];
    }
    else if(rans[RC]==len[RC]&&R[LC]<L[RC])rans[rt]+=rmx[LC];
    ans[rt]=max(ans[LC],ans[RC]);
    if(R[LC]>L[RC])ans[rt]=max(ans[rt],rans[LC]+lmx[RC]);
    if(R[LC]<L[RC])ans[rt]=max(ans[rt],lans[RC]+rmx[LC]);
}

CF718C Sasha and Array

区间加区间求斐波那契对应项的和

sol

和上面某题简直就是情侣题

不过这题不同的是，它用矩阵快速幂

为什么？区间+区间？tag+tag？区间+tag？

这种题挺少见的

CF383C Propagating tree

给你一棵树，每次操作更改一个节点的权值或查询节点权值

当某个节点的权值增加val时，它的子节点权值都增加-val，它子节点的子节点权值增加-(-val)...... 如此一直进行到树的底部

sol

用不到线段树，这甚至连树剖都用不到（没想到吧）

这种单点查询经常转化成区间查询

想象一下，你对奇数层的权值和是正的，偶数层是负的，那么每次操作就是对整颗子树加，然后查询的话就计算出根节点到该节点的权值和就行了

P2572

自己取看吧，懒得搬

sol

板子题，都做了3道了，不说了

-----------------------------CF803G Periodic RMQ Problem

sol

------------------CF911G Mass Change Queries

sol

-----------------------------P4314

sol

-----------------------------P4062

sol

--------------------------P4247

sol

CF840D Destiny

询问区间[l,r]内是否存在出现次数严格大于\frac{r-l+1}{k}的数

sol

就是个主席树板子

一定要记住开大32倍啊

GSSs

GSS1

求区间最大字段和

sol

和以前的很多板子很像

获得成就：使用结构体封装！（据说有cache优化）

struct node{ll lm,rm,ans,sum;}t[N<<2];
node operator+(node a,node b){
    node c;
    c.sum=a.sum+b.sum;
    c.lm=max(a.lm,a.sum+b.lm);
    c.rm=max(b.rm,b.sum+a.rm);
    c.ans=max(max(a.ans,b.ans),b.lm+a.rm);
    return c;
}
void pushup(ll rt){t[rt]=t[LC]+t[RC];}
void build(ll rt,ll l,ll r){
    if(l==r){t[rt].lm=t[rt].rm=t[rt].ans=t[rt].sum=a[l];return;}GM;
    build(LC,l,mid);build(RC,mid+1,r);
    pushup(rt);
}
node query(ll rt,ll l,ll r,ll ql,ll qr){
    if(ql<=l&&r<=qr)return t[rt];GM;
    if(qr<=mid)return query(LC,l,mid,ql,qr);
    if(ql>mid)return query(RC,mid+1,r,ql,qr);
    return query(LC,l,mid,ql,qr)+query(RC,mid+1,r,ql,qr);
}

-------------------SP1557 GSS2

给出 n 个数，q 次询问，求最大子段和，相同的数只算一次

SP1557 GSS3

带修改最大字段和

同上

SP1557 GSS4

区间开平方区间和

还是线段树随便搞

如果一个区间里最大值大于1就直接continue

SP1557 GSS5

左端点在[x1,y1]，右端点在[x2,y2]的最大字段和

sol

貌似是个SB题

首先中间一段必须加，就是左边区间的右边选连续最大值，右边区间的左边连续选最大值之和

区间重叠了？分类讨论即可

剩下三道题都是非线段树的以后再讲

CF343D Water Tree

暴力树剖

CF414C Mashmokh and Reverse Operation

给出一个长度为2^n的序列，m次操作，每次操作给出一整数q，把该序列分成连续的长度均为2^q的2^{n-q}段后，把每段反转，并查询反转后的逆序对

sol

不要被线段树限制住思维

我们考虑每次操作，块与块之间的逆序对数量是不变的

那么其他块内的逆序对是变成n-x的，直接翻转

那么我们相当于是要求出每个2^i的区间的逆序对数量，然后翻转就好了

其实就是个逆序对板子

void mergesort(int l,int r,int x){
    if(l>=r)return;ll mid=(l+r)>>1;
    mergesort(l,mid,x-1);mergesort(mid+1,r,x-1);
    int i=l,j=mid+1,kkk=0;
    while(i<=mid&&j<=r)if(a[i]<a[j])cnt[x][0]+=r-j+1,i++;else j++;//顺序对 
    i=l,j=mid+1;
    while(i<=mid&&j<=r)if(a[i]>a[j])cnt[x][1]+=mid-i+1,b[++kkk]=a[j++];else b[++kkk]=a[i++];//逆序对 
    while(i<=mid)b[++kkk]=a[i++];while(j<=r)b[++kkk]=a[j++];
    rep(i,l,r)a[i]=b[i-l+1];
}
int main(){
    m=read();n=1<<m;rep(i,1,n)a[i]=read();
    mergesort(1,n,m);
    q=read();
    rep(i,1,q){
        x=read();ll ans=0;
        rep(i,1,m){
            if(i<=x)swap(cnt[i][0],cnt[i][1]);
            ans+=cnt[i][1];
        }
        writeln(ans);
    }
}

---------------------------------CF490F Treeland Tour

给出一棵带点权树，求树上最长上升子序列的长度

sol

P2824 排序

给你一个排列，每次对一个区间排序，问你x会去哪里（只有一次）

sol

好像有线段树分裂的做法

不过有种很妙的解法

想一件事：如果我知道了这个数在哪里，那么我可以用很短时间内找到它会去哪里

那么：二分答案！

怎么快速求呢？对于所有大于mid的，标记为1，否则标记为0

然后每次排序就相当于对0/1串排序，就是把一坨0放在前面，一坨1放在后面

可以理解成排队，你只在乎别人是否会挡住你，而不是具体身高

然后就是nlogn的了

等等，单调性？

如果你的身高+1，那么比你低的人+1，就是0的个数+1

最后的判断条件就是是否这个位置上是1

此时再把0/1想象成数，不论我以什么为参考标准，这个排列是不变的

然而，当我的身高增加时，某些1会变0，那么必然在某个mid上我的位置会变成0

就这样

或者说，因为最后的排列是固定的，当mid小于这个位置上的值时时1，否则是0

就这样

最终复杂度：nlog^2n

P2486 [SDOI2011]染色

挺经典的一道树剖题，拿来讲讲

直接维护左端点颜色，右端点颜色，色段个数

P7735 [NOI2021] 轻重边

没想到吧

这是一道挺好的树剖题

虽然是个LCT板子

而且是Y_B_X在生地考后给我讲势能分析时用的题

所以NOI==原题大赛

一看：这不就树剖一下就好了吗

等等：好像去掉该路径上每个终边不好搞

好像这样做行不通了

想了半天，未果

正解是这样的：

对于每次操作，对于整条链上然一种自定unique颜色

啥时候有重链呢，当两端颜色相同时

那么就变成了求色段长度-1的和

也就是链长度-色段个数

不就是上一题吗

P2633 Count on a tree

强制在线求链上第k小

sol

树剖？树剖+线段树合并？

想多了

第k小？权值树？权值树前缀和？

在树上进行前缀和？De

那么真正的树就是t[x]+t[y]-t[lca]-t[fa[lca]],开课主席树不断跳就好了

未完待续。。。

2.变形

0.重链剖分

我的另一篇文章已经详细讲解了

为什么我迁移到洛谷博客了呢？因为cnblogs不太好用

练习题

1.对应区间修改

这个时我自己总结（所以网上可能没有但是还是很经典）

大概就长这个样：

if(qr<=mid)do(LC,l,mid,ql,qr,x,v,k);
else if(ql>mid)do(RC,mid+1,r,ql,qr,x,v,k);
else do(LC,l,mid,ql,mid,x,v,k),do(RC,mid+1,r,mid+1,qr,x,v,k);

有时候区间修改不能做单点修改？如果Wa了可以试试

强调一个点：在这种方式操作时[ql,qr]总是被包含在[l,r]中的

2.线段树优化建图

用BlankAo的一张图

CF786B板子题

我不会打dijkstra

void build(ll rt,ll l,ll r){
    if(l==r)return id[l]=rt,void();GM;
    add(rt,LC,0);add(rt,RC,0);
    add((LC)+D,rt+D,0);add((RC)+D,rt+D,0);
    build(LC,l,mid);build(RC,mid+1,r);
}
void connect(ll rt,ll l,ll r,ll ql,ll qr,ll x,ll v,ll k){
    if(ql<=l&&r<=qr){
        if(k)add(rt+D,x,v);
        else add(x,rt,v);
        return;
    }
    GM;
    if(qr<=mid)connect(LC,l,mid,ql,qr,x,v,k);
    else if(ql>mid)connect(RC,mid+1,r,ql,qr,x,v,k);
    else connect(LC,l,mid,ql,mid,x,v,k),connect(RC,mid+1,r,mid+1,qr,x,v,k);
}
int main(){
    n=read();Q=read();s=read();
    build(1,1,n);
    rep(i,1,Q){
        opt=read();x=read();y=read();z=read();
        if(opt==1)add(id[x],id[y],z);
        else w=read(),connect(1,1,n,y,z,id[x],w,opt-2);
    }
    rep(i,1,n)add(id[i],id[i]+D,0),add(id[i]+D,id[i],0);
    q.push((nd){id[s],0});mem(dis,0x3f);dis[id[s]]=0;
    while(!q.empty()){
        ll u=q.top().i;q.pop();
        if(vis[u])continue;vis[u]=1;
        go(u)if(!vis[v]&&dis[v]>dis[u]+e[i].dis){
            dis[v]=dis[u]+e[i].dis;
            q.push((nd){v,dis[v]});
        }
    }
    rep(i,1,n)writesp(dis[id[i]]==inf?-1:dis[id[i]]);
}

然后我就看到了这篇日报

3.标记永久化

在可持久化线段树中，我们常常要使用区间修改操作，如果再用下传标记再向上更新的方式来实现就会变得十分麻烦

标记永久化的原理简单来说就是修改时一路更改被影响到的点，询问时则一路累加路上的标记，从而省去下传标记的操作

咋实现？

拿线段树1举例

找到ql/qr覆盖的大区间，给他们的lz + k

每次走过一个区间，给它的sum + (qr-ql+1)*k

然后查询也差不多，到全覆盖区间返回它的lzs*(r-l+1)+sum

其中lzs是从根到这个区间的lz和

这里

应用？SP11470 TTM - To the moon

对不起，这题要用到主席树

相比一般的主席树，这个要多支持一个操作，那就是区间修改

我们不能把区间里的每一条链都建出来，因为那样时间空间都不允许，所以我们可以依靠标记永久化来实现

talking is cheap, show me the code

#define N 220000
ll n,m,x,y,z,opt,a[N],cnt,tme,RT[N];
#define LC lc[rt]
#define RC rc[rt]
#define GM ll mid=(l+r)>>1
ll sum[N<<5],lz[N<<5],lc[N<<5],rc[N<<5];
void pushup(ll rt){sum[rt]=sum[LC]+sum[RC];}
void clone(ll rt,ll x){sum[rt]=sum[x];lz[rt]=lz[x];lc[rt]=lc[x];rc[rt]=rc[x];}
void build(ll &rt,ll l,ll r){
    rt=++cnt;
    if(l==r)return sum[rt]=a[l],void();GM;
    build(LC,l,mid);build(RC,mid+1,r);
    pushup(rt);
}
void updata(ll &rt,ll _rt,ll l,ll r,ll ql,ll qr,ll k){
    rt=++cnt;clone(rt,_rt);
    sum[rt]+=(qr-ql+1)*k;
    if(l==ql&&r==qr)return lz[rt]+=k,void();GM;
    if(qr<=mid)updata(LC,lc[_rt],l,mid,ql,qr,k);
    else if(ql>mid)updata(RC,rc[_rt],mid+1,r,ql,qr,k);
    else updata(LC,lc[_rt],l,mid,ql,mid,k),updata(RC,rc[_rt],mid+1,r,mid+1,qr,k);
}
ll query(ll rt,ll l,ll r,ll ql,ll qr,ll tmep){
    if(l==ql&&r==qr)return tmep*(r-l+1)+sum[rt];GM;
    if(qr<=mid)return query(LC,l,mid,ql,qr,tmep+lz[rt]);
    if(ql>mid)return query(RC,mid+1,r,ql,qr,tmep+lz[rt]);
    return query(LC,l,mid,ql,mid,tmep+lz[rt])+query(RC,mid+1,r,mid+1,qr,tmep+lz[rt]);
}
int main(){
    n=read();m=read();rep(i,1,n)a[i]=read();build(RT[0],1,n);
    rep(i,1,m){
        char ch=getc();x=read();
        if(ch=='C')y=read(),z=read(),tme++,updata(RT[tme],RT[tme-1],1,n,x,y,z);
        else if(ch=='Q')y=read(),writeln(query(RT[tme],1,n,x,y,0));
        else if(ch=='H')y=read(),z=read(),writeln(query(RT[z],1,n,x,y,0));
        else if(ch=='B')tme=x,cnt=RT[tme+1];//
        else puts("BUG");
    }
}

4.李超线段树

要用到标记永久化

它的每个线段树节点都存一条线段，表示这个节点对应的区间内这条线段是最优的

对于每加进一条线段，要么全部比他大，要么全部比他小，或者是上面两种情况

对于前两种，只要保留大的就好了，直接return

对于后两种，交点在哪里就扔进那边儿子

每次查询就从根到该儿子的对应的线段就好了

double f(ll x,ll y){return ln[x].k*y+ln[x].b;}
double jd(ll x,ll y){return (ln[x].b-ln[y].b)/(ln[y].k-ln[x].k);}
void updata(ll rt,ll l,ll r,ll ql,ll qr,ll k){
    GM;if(ql<=l&&r<=qr){
        if(!w[rt])return w[rt]=k,void();
        double ly=f(w[rt],l),ry=f(w[rt],r),ly1=f(k,l),ry1=f(k,r);
        if(ly1<=ly&&ry1<=ry)return;
        if(ly1>=ly&&ry1>=ry)return w[rt]=k,void();
        double pos=jd(w[rt],k);
        if(ly>=ly1){
            if(pos<=mid)updata(LC,l,mid,ql,qr,w[rt]),w[rt]=k;
            else updata(RC,mid+1,r,ql,qr,k);
        }
        else{
            if(pos<=mid)updata(LC,l,mid,ql,qr,k);
            else updata(RC,mid+1,r,ql,qr,w[rt]),w[rt]=k;
        }
        return;
    }
    if(ql<=mid)updata(LC,l,mid,ql,qr,k);
    if(qr>mid)updata(RC,mid+1,r,ql,qr,k);
}
ll chk(ll x,ll y,ll pos){return f(x,pos)>f(y,pos)?x:y;}
ll query(ll rt,ll l,ll r,ll pos){
    ll tmp=w[rt];
    if(l==r)return tmp;GM;
    if(pos<=mid)tmp=chk(tmp,query(LC,l,mid,pos),pos);
    else tmp=chk(tmp,query(RC,mid+1,r,pos),pos);
    return tmp;
}

然后我偶然发现了zzc的博客

练习：

[HEOI2013]Segment板子
[JSOI2008]Blue Mary开公司板子
[SDOI2016]游戏树剖
[CEOI2017]Building Bridges
CF932F Escape Through LeafDP还有很多我不会的做法
P4027 [NOI2007] 货币兑换DP
P2305 [NOI2014] 购票线段树套李超

5.动态开点

相信大家已经会了

为什么要这样呢？因为普通线段树中有接近一半的空间是浪费的

就是用到一个开一个：if(!rt)rt=++cnt;

6.权值线段树

here

7.扫描线

它就这样

每扫到一个区间就加入到线段树里

离散化一下就好了

8.线段树合并

三年前以及NTF的作业

9.线段树分裂

暂gu

10.吉老师线段树

好不容易找到了我一年前看到的那篇好博客

以及PB的博客

未完待续

差不多就要到此结束啦，意犹未尽的同学们可以去看看这个

数据结构专题

以及线段树专题2版权原因不公开

未来将会更新数据结构专题、DP专题、数学专题、新兴算法专题、分治专题、字符串专题、细小专题

感谢支持

施工原材料：
https://www.luogu.com.cn/training/1124#information
https://www.luogu.com.cn/blog/bfqaq/qian-tan-quan-zhi-xian-duan-shu
https://www.luogu.com.cn/blog/bfqaq/qian-tan-shu-zhuang-shuo-zu-quan-zhi-shu