首页 > 其他 > 详细

GSS3/1 - Can you answer these queries 3/1

时间:2020-01-27 22:50:53      阅读:100      评论:0      收藏:0      [点我收藏+]

这个题集好好,那天我做一下(开个大坑?)

嘛,题目难的是查询,这里就只讲查询了

根据题解,我们用线段树维护3个东西

lx:表示从lx走,所能在给定区间里面的最大值

rx:参考上面

mx:表示在给定区间中间截取一段所能取到的最大值

那么对于题目给定的查询区间(假设其为L,R)

我们用线段树去遍历这个区间(访问,,,,,比较好点吧)

如果L---R刚好对应线段树的一个区间,那么直接返回我们的mx就好了(正确性显然)

相对的,存在不对应区间的情况

考虑合并答案

对于我们线段树的每次操作相当于把一段区间一分为二

那么我们可以借用线段树的操作,维护一个在线段树维护范围内的又在L---R的部分答案

然后就可以合并

对于这个部分答案,很好维护

只要将遍历所有L---R内的线段树局部节点就可以解决

技术分享图片
#include<bits/stdc++.h>
#define MAXN 400000
using namespace std;

int n,q,date[MAXN];
int tp,mb1,mb2;
struct node{
    int sum;
    int lx,rx,mx;
}t[MAXN*4];

int up(int now){
    t[now].sum = t[now*2].sum+t[now*2+1].sum;
    t[now].lx = max(t[now*2].lx,t[now*2].sum+t[now*2+1].lx);
    t[now].rx = max(t[now*2+1].rx,t[now*2].rx+t[now*2+1].sum);
    t[now].mx = max(max(t[now*2].mx,t[now*2+1].mx),t[now*2].rx+t[now*2+1].lx);
}

int build(int ll,int rr,int now){
    if(ll==rr){
        t[now].lx = t[now].rx = t[now].mx = t[now].sum = date[ll];
        return 0;
    }
    int mid = (ll+rr)>>1;
    build(ll,mid,now*2);
    build(mid+1,rr,now*2+1);
    up(now);
}

int change(int now,int l,int r,int x,int y){//在x上改成y 
    int mid = (l+r)>>1;
    if(r<x||l>x)return 0;
    if(x==l&&x==r){
        t[now].lx = t[now].rx = t[now].mx = t[now].sum = y;
        return 0;
    }
    change(now*2+1,mid+1,r,x,y);
    change(now*2,l,mid,x,y);
    
    up(now);
    
}

node found(int ml,int mr,int now,int l,int r){
    if(l>=ml&&r<=mr){
        return t[now];        
    }     
    int mid = (l+r)>>1;
    node ans,a,b;
    if(mid<ml)return found(ml,mr,now*2+1,mid+1,r);
    if(mid>=mr)return found(ml,mr,now*2,l,mid); 
    else{
    a = found(ml,mr,now*2,l,mid);
    b = found(ml,mr,now*2+1,mid+1,r);
    ans.sum = a.sum+b.sum;
    ans.lx = max(a.lx,a.sum+b.lx);
    ans.rx = max(a.rx+b.sum,b.rx);
    ans.mx = max(a.rx+b.lx,max(a.mx,b.mx));
    return ans;    
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>date[i];
    }
    build(1,n,1);
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>tp>>mb1>>mb2;
        if(tp==1){
            node p=found(mb1,mb2,1,1,n);
        cout<<p.mx<<endl;
        }
        else{
            change(1,1,n,mb1,mb2);
        }
        
    }
}
View Code

当然,也可以用平衡树解决此问题(嘛,平衡树完全不会做....)

一般的,假设平衡树已经维护了原区间序列的编号

只要使L-1作为根节点,R+1作为根右节点,此时因为平衡树同时满足BST性质

故R的左子树就是L---R区间的编号(一开始搞懵了)

本质上在平衡树上对原序列的操作是不需要遵守BST性质的

因为与编号无关,只与编号映射的集合有关

那么考虑 提取区间后的操作....

同样的参照线段树做法...维护3个东西lx,rx,mx

(此时开始乱搞....)

嘛,直接仿造线段树的插入方式,但维护的不是区间是节点....

然后考虑旋转怎么维护那3坨东西

嘛,考虑到变的只有旋转点和旋转点父亲

直接up一下就好了

 

GSS3/1 - Can you answer these queries 3/1

原文:https://www.cnblogs.com/shatianming/p/12237036.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!