SP4487 GSS6 - Can you answer these queries VI

luckydrawbox · 2021-08-26 15:37:41 · 题解

块状链表

初始化

用结构体存每个块，一个块就是一个节点。建立一个虚拟的 0 节点作为起点和终点，同时建一个节点 1 开始插入数据。由于有多次插入和删除操作，所以我们要回收内存。

l	r	len	b_i	sum	lmx	rmx	mx
前一个块	后一个块	块长度	块中的元素	整块和	块内最大前缀和	块内最大后缀和	块内最大子段和

struct K{
    int l,r,len;
    ll b[2*M],sum,lmx,rmx,mx;
}a[2*M];

for(int i=1;i<=M*1.5;i++)
    nc[i]=i;
a[0].l=a[0].r=1;

基本操作

从起点的后一个块开始遍历，每次减去这个块的长度再到下一个块，如果减不下去了说明到达了目标块。

注意我这里块内是从 0 开始编号，所以 p 要再减 1。

int get(int &p){
    int kp=a[0].r;
    while(a[kp].len<p){
        p-=a[kp].len;
        kp=a[kp].r;
    }
    p--;
    return kp;
}

从内存数组中取出一个点初始化即可。

void build(int p){
    int nw=nc[++t];
    a[nw].l=p;
    a[nw].r=a[p].r;
    a[a[p].r].l=nw;
    a[p].r=nw;
    a[nw].len=0;
}

切断 p 与前后节点的联系，把 p 放入内存数组。

void del(int p){
    nc[++t]=p;
    a[a[p].l].r=a[p].r;
    a[a[p].r].l=a[p].l;
}

更新方式如下：

void update(int p){
    ll s=0;
    a[p].sum=0;
    a[p].lmx=a[p].rmx=a[p].mx=inf;
    for(int i=0;i<a[p].len;i++){
        s=max(a[p].b[i],s+a[p].b[i]);
        a[p].mx=max(a[p].mx,s);
        a[p].sum+=a[p].b[i];
        a[p].lmx=max(a[p].sum,a[p].lmx);
    }
    s=0;
    for(int i=a[p].len-1;i>=0;i--){
        s+=a[p].b[i];
        a[p].rmx=max(s,a[p].rmx);
    }
}

正常操作

在 p 节点后新建一个节点，把一半数据扔到新的节点里。

分裂完后更新这两个节点。

void split(int p){
    build(p);
    a[a[p].r].len=a[p].len/2;
    for(int i=0;i<a[a[p].r].len;i++)
        a[a[p].r].b[i]=a[p].b[a[p].len-a[a[p].r].len+i];
    a[p].len-=a[a[p].r].len;
    update(p);
    update(a[p].r);
}

把 a[p].r 节点中的元素放在 p 节点后面，更新 p 节点，删除 a[p].r 节点。

void merge(int p){
    for(int i=0;i<a[a[p].r].len;i++)
        a[p].b[a[p].len+i]=a[a[p].r].b[i];
    a[p].len+=a[a[p].r].len;
    update(p);
    del(a[p].r);
}

找到 p 所在的块，把第 p 个元素之后的元素后移，插入 x，如果是插在整个序列的末尾则需要特判一下。插入完后更新块。

如果插入完后序列长度超过限定块长的两倍，则分裂这个块。

void insert(int p,int x){
    int kp;
    if(p==sum){
        kp=a[0].l;
        a[kp].b[a[kp].len++]=x;
        update(kp);
        if(a[kp].len>len*1.6)
            split(kp);
        return;
    }
    kp=get(p);
    for(int i=a[kp].len-1;i>=p;i--)
        a[kp].b[i+1]=a[kp].b[i];
    a[kp].len++;
    a[kp].b[p]=x;
    update(kp);
    if(a[kp].len>len*1.6)
        split(kp);
}

找到 p 所在的块，把第 p 个元素之后的元素前移。

删除后如果没有元素了，删除这个节点，否则尝试与前后的块合并，要先和后面的合并再和前面的合并，顺序不能变，否则会出现这个节点没了却还是和后面的块合并的现象。

void remove(int p){
    int kp=get(p);
    for(int i=p+1;i<a[kp].len;i++)
        a[kp].b[i-1]=a[kp].b[i];
    a[kp].len--;
    if(!a[kp].len){
        del(kp);
        return;
    }
    update(kp);
    if(a[kp].r&&a[kp].len+a[a[kp].r].len<1.5*len)
        merge(kp);
    if(a[kp].l&&a[kp].len+a[a[kp].l].len<1.5*len)
        merge(a[kp].l);
}

找到 p 所在的块，修改并更新块即可。

void change(int p,int x){
    int kp=get(p);
    a[kp].b[p]=x;
    update(kp);
}

对于散块，暴力去求。

对于整块，整个区间的最大子段和 mx 有以下几种情况：

- 区间边缘零散的最大子段和 ml,mr。

左右各求一遍。

- 每个块内的最大子段和 a[p].mx。

之前计算好了，遍历时直接拿来用。

- 某个整块的最大前缀和 a[p].lmx 和以这个块的左端点减 1 为右端点的最大后缀和 lmx。

遍历时顺便记录 lmx 并计算 mx=\max(mx,\max(lmx,0)+a[p].lmx)。

- 右边的散块之前的最大后缀和 lmx 和右边这个散块的最大前缀和 rmx。

计算 mx=\max(mx,lmx+rmx)。

int ask(int l,int r){
    int kl=get(l),kr=get(r);
    ll ml=inf,mr=inf,mx=inf;
    ll lmx=inf,rmx=inf,s=0,sum=0;
    if(kl==kr){
        for(int i=l;i<=r;i++){
            s=max(s+a[kl].b[i],a[kl].b[i]);
            mx=max(mx,s);
        }
        return mx;
    }
    for(int i=a[kl].len-1;i>=l;i--){
        sum+=a[kl].b[i];
        lmx=max(lmx,sum);
        s=max(s+a[kl].b[i],a[kl].b[i]);
        ml=max(ml,s);
    }
    sum=s=0;
    for(int i=0;i<=r;i++){
        sum+=a[kr].b[i];
        rmx=max(rmx,sum);
        s=max(s+a[kr].b[i],a[kr].b[i]);
        mr=max(mr,s);
    }
    mx=max(ml,mr);
    for(int p=a[kl].r;p!=kr;p=a[p].r){
        mx=max(mx,a[p].mx);
        mx=max(mx,max(lmx,(ll)0)+a[p].lmx);
        lmx=max(max(lmx,(ll)0)+a[p].sum,a[p].rmx);
    }
    mx=max(mx,lmx+rmx);
    return mx;
}

关于块长限制

在前面的插入操作中，如果某个块超出分裂的块长限制，我们会将其分裂；在前面的删除操作中，如果某个块和前后块合并起来不会超过合并的块长限制，我们会将其合并。

记我们定的块长为 len，那么所谓块长限制就是限制每块的块长不超过 x\times len，以稳定复杂度。

那么，这题分裂和合并的块长限制究竟是多少呢？

这是个很玄学的东西，你可以像我一样，把分裂的块长限制的 x 设为 1.6，把合并的块长限制的 x 设为 1.5。

总之，这是个玄之又玄的东西，分寸请自己把握。

时间复杂度大概为 O(n\sqrt n)。

代码

到这里，你基本上已经能写出程序了，然而不幸的是，这题卡块状链表~~你怎么不早说~~，所以你可能需要大力卡常才能过。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10,M=500,inf=-2e9;
int n,m,len,t=1,nc[M*2],sum;
ll x;
char op;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
struct K{
    int l,r,len;
    ll b[2*M],sum,lmx,rmx,mx;
}a[2*M];
int get(int &p){
    int kp=a[0].r;
    while(a[kp].len<p){
        p-=a[kp].len;
        kp=a[kp].r;
    }
    p--;
    return kp;
}
void build(int p){
    int nw=nc[++t];
    a[nw].l=p;
    a[nw].r=a[p].r;
    a[a[p].r].l=nw;
    a[p].r=nw;
    a[nw].len=0;
}
void del(int p){
    nc[++t]=p;
    a[a[p].l].r=a[p].r;
    a[a[p].r].l=a[p].l;
}
void update(int p){
    ll s=0;
    a[p].sum=0;
    a[p].lmx=a[p].rmx=a[p].mx=inf;
    for(int i=0;i<a[p].len;i++){
        s=max(a[p].b[i],s+a[p].b[i]);
        a[p].mx=max(a[p].mx,s);
        a[p].sum+=a[p].b[i];
        a[p].lmx=max(a[p].sum,a[p].lmx);
    }
    s=0;
    for(int i=a[p].len-1;i>=0;i--){
        s+=a[p].b[i];
        a[p].rmx=max(s,a[p].rmx);
    }
}
void split(int p){
    build(p);
    a[a[p].r].len=a[p].len/2;
    for(int i=0;i<a[a[p].r].len;i++)
        a[a[p].r].b[i]=a[p].b[a[p].len-a[a[p].r].len+i];
    a[p].len-=a[a[p].r].len;
    update(p);
    update(a[p].r);
}
void merge(int p){
    for(int i=0;i<a[a[p].r].len;i++)
        a[p].b[a[p].len+i]=a[a[p].r].b[i];
    a[p].len+=a[a[p].r].len;
    update(p);
    del(a[p].r);
}
void insert(int p,int x){
    int kp;
    if(p==sum){
        kp=a[0].l;
        a[kp].b[a[kp].len++]=x;
        update(kp);
        if(a[kp].len>len*1.6)
            split(kp);
        return;
    }
    kp=get(p);
    for(int i=a[kp].len-1;i>=p;i--)
        a[kp].b[i+1]=a[kp].b[i];
    a[kp].len++;
    a[kp].b[p]=x;
    update(kp);
    if(a[kp].len>len*1.6)
        split(kp);
}
void remove(int p){
    int kp=get(p);
    for(int i=p+1;i<a[kp].len;i++)
        a[kp].b[i-1]=a[kp].b[i];
    a[kp].len--;
    if(!a[kp].len){
        del(kp);
        return;
    }
    update(kp);
    if(a[kp].r&&a[kp].len+a[a[kp].r].len<1.5*len)
        merge(kp);
    if(a[kp].l&&a[kp].len+a[a[kp].l].len<1.5*len)
        merge(a[kp].l);
}
void change(int p,int x){
    int kp=get(p);
    a[kp].b[p]=x;
    update(kp);
}
int ask(int l,int r){
    int kl=get(l),kr=get(r);
    ll ml=inf,mr=inf,mx=inf;
    ll lmx=inf,rmx=inf,s=0,sum=0;
    if(kl==kr){
        for(int i=l;i<=r;i++){
            s=max(s+a[kl].b[i],a[kl].b[i]);
            mx=max(mx,s);
        }
        return mx;
    }
    for(int i=a[kl].len-1;i>=l;i--){
        sum+=a[kl].b[i];
        lmx=max(lmx,sum);
        s=max(s+a[kl].b[i],a[kl].b[i]);
        ml=max(ml,s);
    }
    sum=s=0;
    for(int i=0;i<=r;i++){
        sum+=a[kr].b[i];
        rmx=max(rmx,sum);
        s=max(s+a[kr].b[i],a[kr].b[i]);
        mr=max(mr,s);
    }
    mx=max(ml,mr);
    for(int p=a[kl].r;p!=kr;p=a[p].r){
        mx=max(mx,a[p].mx);
        mx=max(mx,max(lmx,(ll)0)+a[p].lmx);
        lmx=max(max(lmx,(ll)0)+a[p].sum,a[p].rmx);
    }
    mx=max(mx,lmx+rmx);
    return mx;
}
int main(){
    for(int i=1;i<=M*1.5;i++)
        nc[i]=i;
    a[0].l=a[0].r=1;
    n=read();
    len=sqrt(n);
    for(int i=1;i<=n;i++)
        insert(++sum,read());
    m=read();
    for(int i=1;i<=m;i++){
        cin>>op;
        x=read();
        switch(op){
            case 'I':sum++;insert(x,read());break;
            case 'D':sum--;remove(x);break;
            case 'R':change(x,read());break;
            case 'Q':write(ask(x,read())),putchar('\n');break;
        }
    }
    return 0;
}