风信子(线段树)

发布时间:2024年01月23日

有一个长为 n n n 的序列 a a a

定义一个合法二元组 ( i , j ) (i,j) (i,j) 需要满足 i , j i,j i,j 为整数,且 i ≤ j i\le j ij。它的分数为 a i ? a j a_i-a_j ai??aj?

合法二元组 ( i , j ) (i,j) (i,j) 在区间 [ l , r ] [l,r] [l,r] 内,当且仅当 l ≤ i , j ≤ r l\le i,j\le r li,jr

m m m 次操作:

1 l r x:表示将序列中第 l l l 个位置到第 r r r 个位置都加上 x x x

2 l r k:表示询问选出 k k k 个不同的合法二元组,每个合法二元组都在区间 [ l , r ] [l,r] [l,r] 内,这些合法二元组的分数和最高是多少。

两个合法二元组 ( i 1 , j 1 ) (i_1,j_1) (i1?,j1?) ( i 2 , j 2 ) (i_2,j_2) (i2?,j2?) 相同,等价于 i 1 = i 2 i_1=i_2 i1?=i2? j 1 = j 2 j_1=j_2 j1?=j2?

1 ≤ n , m ≤ 1 0 5 , 1 ≤ l ≤ r ≤ n , 1 ≤ ( ∑ k ) ≤ 3 × 1 0 5 , ? 1 0 6 ≤ a i , x ≤ 1 0 6 1\le n,m\le10^5,1\le l\le r\le n,1\le(\sum k)\le3\times10^5,-10^6\le a_i,x\le10^6 1n,m105,1lrn,1(k)3×105,?106ai?,x106

50 % 50\% 50% 数据: 1 ≤ n , m ≤ 1000 1\le n,m\le1000 1n,m1000

15 % 15\% 15% 数据: k = 1 k=1 k=1


前置题:[NOI2010] 超级钢琴

50 50 50 分做法:对于每次询问都做一遍超级钢琴。

15 15 15 分做法:由于 k = 1 k=1 k=1,那么可以用线段树维护答案,答案是左右儿子的答案,左儿子最大值减右儿子最小值,这三者的最大值。

注意到超级钢琴使用了 S ( o , l , r ) S(o,l,r) S(o,l,r),表示起点为 o o o,终点范围为 [ l , r ] [l,r] [l,r],答案的最大值,然后分裂成 S ( o , l , x ? 1 ) , S ( o , x + 1 , r ) S(o,l,x-1),S(o,x+1,r) S(o,l,x?1),S(o,x+1,r) 两个区间。

这显然在此题不够用,于是我们设 S ( l , r , x , y ) S(l,r,x,y) S(l,r,x,y) 表示起点 ∈ [ l , r ] \in[l,r] [l,r]、终点 ∈ [ x , y ] \in[x,y] [x,y] 的答案。但是这么做就不好算出答案。

考虑什么样的区间好计算出答案

  1. [ l , r ] = [ x , y ] [l,r]=[x,y] [l,r]=[x,y],就是 k = 1 k=1 k=1 的做法。
  2. [ l , r ] ∩ [ x , y ] = ? [l,r]\cap[x,y]=\varnothing [l,r][x,y]=?,答案就是左区间最大值减右区间最小值。

下面分析如何把一个合法区间分裂成若干符合条件区间。(注意分出的区间不能有包含关系,不然就会算重)

  1. 第一种区间 [ l , r ] = [ x , y ] [l,r]=[x,y] [l,r]=[x,y](设 X , Y X,Y X,Y 表示最大答案在下标 X , Y X,Y X,Y 取得),将其分裂成:

    起点 ∈ [ l , X ? 1 ] \in[l,X-1] [l,X?1],终点 ∈ [ l , X ? 1 ] ( X > l ) \in[l,X-1](X>l) [l,X?1](X>l)
    起点 ∈ [ l , X ? 1 ] \in[l,X-1] [l,X?1],终点 ∈ [ X , r ] ( X > l ) \in[X,r](X>l) [X,r](X>l)
    起点 ∈ [ X , X ] \in[X,X] [X,X],终点 ∈ [ X , X ] ( X =? Y ) \in[X,X](X\not=Y) [X,X](X=Y)
    起点 ∈ [ X , X ] \in[X,X] [X,X],终点 ∈ [ X + 1 , Y ? 1 ] ( X < Y ? 1 ) \in[X+1,Y-1](X<Y-1) [X+1,Y?1](X<Y?1)
    起点 ∈ [ X , X ] \in[X,X] [X,X],终点 ∈ [ Y + 1 , r ] ( Y < r ) \in[Y+1,r](Y<r) [Y+1,r](Y<r)
    起点 ∈ [ X + 1 , r ] \in[X+1,r] [X+1,r],终点 ∈ [ X + 1 , r ] ( X < r ) \in[X+1,r](X<r) [X+1,r](X<r)

  2. 第二种区间 [ l , r ] ∩ [ x , y ] = ? [l,r]\cap[x,y]=\varnothing [l,r][x,y]=?(设 X , Y X,Y X,Y 表示最大答案在下标 X , Y X,Y X,Y 取得),将其分裂成:

    起点 ∈ [ l , X ? 1 ] \in[l,X-1] [l,X?1],终点 ∈ [ x , y ] ( X > l ) \in[x,y](X>l) [x,y](X>l)
    起点 ∈ [ X , X ] \in[X,X] [X,X],终点 ∈ [ x , Y ? 1 ] ( x < Y ) \in[x,Y-1](x<Y) [x,Y?1](x<Y)
    起点 ∈ [ X , X ] \in[X,X] [X,X],终点 ∈ [ Y + 1 , y ] ( Y < y ) \in[Y+1,y](Y<y) [Y+1,y](Y<y)
    起点 ∈ [ X + 1 , r ] \in[X+1,r] [X+1,r],终点 ∈ [ x , y ] ( X < r ) \in[x,y](X<r) [x,y](X<r)

分好区间后,直接用优先队列维护即可。

时间复杂度 O ( m log ? n + ( ∑ k ) log ? ( ∑ k ) ) O(m\log n+(\sum k)\log(\sum k)) O(mlogn+(k)log(k))

具体实现参照代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF=1e18;
const int N=1e5+10;
int n,m;
ll a[N];
struct node
{
    ll Max,Min,ans,la,num1,num2;
    pair<ll,ll> num3;
}tr[N<<2];
struct Node
{
    int l,r,x,y;
    ll aa;
    bool operator<(const Node &a)const{
        return aa<a.aa;
    }
};
void pushup(node &rt,node ls,node rs)
{
    rt.num1=ls.Max>rs.Max?ls.num1:rs.num1;
    rt.Max=max(ls.Max,rs.Max);
    rt.num2=ls.Min<rs.Min?ls.num2:rs.num2;
    rt.Min=min(ls.Min,rs.Min);
    ll x=ls.ans,y=rs.ans,z=ls.Max-rs.Min;
    if(x>=max(y,z)) rt.num3=ls.num3;
    else if(y>=max(x,z)) rt.num3=rs.num3;
    else rt.num3=make_pair(ls.num1,rs.num2);
    rt.ans=max({x,y,z});
}
void pushdown(int rt)
{
    tr[rt<<1].Max+=tr[rt].la;
    tr[rt<<1].Min+=tr[rt].la;
    tr[rt<<1].la+=tr[rt].la;
    tr[rt<<1|1].Max+=tr[rt].la;
    tr[rt<<1|1].Min+=tr[rt].la;
    tr[rt<<1|1].la+=tr[rt].la;
    tr[rt].la=0;
}
void build(int rt,int l,int r)
{
    if(l==r){
        tr[rt].Max=tr[rt].Min=a[l];
        tr[rt].num1=tr[rt].num2=l;
        tr[rt].num3=make_pair(l,l);
        return;
    }
    int mid=l+r>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(tr[rt],tr[rt<<1],tr[rt<<1|1]);
}
void update(int rt,int l,int r,int x,int y,ll d)
{
    if(r<x||y<l) return;
    if(x<=l&&r<=y){
        tr[rt].Max+=d;
        tr[rt].Min+=d;
        tr[rt].la+=d;
        return;
    }
    int mid=l+r>>1;
    pushdown(rt);
    update(rt<<1,l,mid,x,y,d);
    update(rt<<1|1,mid+1,r,x,y,d);
    pushup(tr[rt],tr[rt<<1],tr[rt<<1|1]);
}
node query(int rt,int l,int r,int x,int y)
{
    if(r<x||y<l) return {-INF,INF,-INF,0,0,0,make_pair(0,0)};
    if(x<=l&&r<=y) return tr[rt];
    int mid=l+r>>1;
    pushdown(rt);
    node aa=query(rt<<1,l,mid,x,y),bb=query(rt<<1|1,mid+1,r,x,y),ans;
    pushup(ans,aa,bb);
    return ans;
}
int main()
{
    // freopen("smart.in","r",stdin);
    // freopen("smart.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for(int i=1,op,L,R,num;i<=m;i++){
        cin>>op>>L>>R>>num;
        if(op==1) update(1,1,n,L,R,num);
        else{
            ll ans=0;
            priority_queue<Node> q;
            q.push({L,R,L,R,query(1,1,n,L,R).ans});
            while(num--){
                Node k=q.top();
                q.pop();
                ans+=k.aa;
                if(k.l==k.x&&k.r==k.y){
                    node aa=query(1,1,n,k.l,k.r);
                    int x=aa.num3.first,y=aa.num3.second;
                    if(x>k.l) q.push({k.l,x-1,k.l,x-1,query(1,1,n,k.l,x-1).ans});
                    if(x>k.l) q.push({k.l,x-1,x,k.r,query(1,1,n,k.l,x-1).Max-query(1,1,n,x,k.r).Min});
                    if(x!=y) q.push({x,x,x,x,query(1,1,n,x,x).ans});
                    if(x<y-1) q.push({x,x,x+1,y-1,query(1,1,n,x,x).Max-query(1,1,n,x+1,y-1).Min});
                    if(y<k.r) q.push({x,x,y+1,k.r,query(1,1,n,x,x).Max-query(1,1,n,y+1,k.r).Min});
                    if(x<k.r) q.push({x+1,k.r,x+1,k.r,query(1,1,n,x+1,k.r).ans});
                }
                else{
                    node aa=query(1,1,n,k.l,k.r),bb=query(1,1,n,k.x,k.y);
                    int x=aa.num1,y=bb.num2;
                    if(x>k.l) q.push({k.l,x-1,k.x,k.y,query(1,1,n,k.l,x-1).Max-query(1,1,n,k.x,k.y).Min});
                    if(k.x<y) q.push({x,x,k.x,y-1,query(1,1,n,x,x).Max-query(1,1,n,k.x,y-1).Min});
                    if(y<k.y) q.push({x,x,y+1,k.y,query(1,1,n,x,x).Max-query(1,1,n,y+1,k.y).Min});
                    if(x<k.r) q.push({x+1,k.r,k.x,k.y,query(1,1,n,x+1,k.r).Max-query(1,1,n,k.x,k.y).Min});
                }
            }
            cout<<ans<<"\n";
        }
    }
}
文章来源:https://blog.csdn.net/dygxczn/article/details/135762911
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。