P2710 数列 题解

· · 题解

P2710 数列 题解

题目传送门。

块状链表！！！

虽然是块状链表但是比大多数平衡树都跑得快！

题意

略。

思路

首先我们想到了平衡树。

但是为了显得与众不同一点，我偏偏就要用块状链表。

首先块状链表的常规操作读者们在这里看吧，我参考了这里的写法（这篇文章不是我写的，侵权请联系删除）。

考虑剩下几个操作。

首先根据这个题类似的操作，每个块要记录 \texttt{sum,lis,llis,rlis}，表示块和、LIS、从左往右的 LIS 和从右往左的 LIS。

分裂和合并的时候需要对块暴力重新计算上述东西，复杂度正确是因为我们一次修改只会至多两次分裂和合并。

然后要给每一个块打上 \texttt{rev} 和 \texttt{cov} 标记，下传的时候规定 \texttt{cov} 优先级高。

考虑翻转。

把散块分裂成两个，然后就变成全部都是整块了。

整块打翻转标记，并且颠倒顺序即可。

考虑求 LIS。

同样的把散块分裂成两个，然后就变成全部都是整块了。

然后不是很好描述，看代码吧（其中所有整块的编号保存在 vec 中，ans 即为答案）：

int ans=a[vec[0]].lis,maxx=a[vec[0]].rlis;
for(int i=1;i<vec.size();i++)
{
    ans=max(ans,max(a[vec[i]].lis,maxx+a[vec[i]].llis));
    maxx=max(maxx+a[vec[i]].sum,a[vec[i]].rlis);
}
return ans;

求和和查询区间和就是整块加，散块暴力即可，不需要分裂块。

有一个单点查，其实等价于区间查，长度为 1 而已。

然后注意特判每一个操作，在同一个块内的情况，暴力修改即可。

块的大小取 B=\sqrt n，时间复杂度大约是 O(n\sqrt n)，常数比平衡树小得多。

AC 代码

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
int in()
{
    int k=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void out(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
const int N=2e5+10,B=447;
struct block_list
{
    struct node
    {
        int siz,nex;int s[B<<2];
        int sum,lis,llis,rlis;
        int rev,cov;
        node(){cov=2e9;} // 注意不能是 0
    }a[B<<2];
    int bin[N],tot;
    int newnode(){return bin[tot--];}
    void del(int x)
    {
        bin[++tot]=x;
        a[x].siz=a[x].sum=a[x].lis=a[x].llis=a[x].rlis=0,a[x].nex=-1;
        a[x].rev=0,a[x].cov=2e9;
    }
    block_list()
    {
        for(int i=1;i<N;i++)bin[++tot]=N-i;
        a[0].nex=-1;
    }
    int pos(int &p)
    {
        int x=0;
        for(;x!=-1&&a[x].siz<p;x=a[x].nex)p-=a[x].siz;
        return x;
    }
    void pushdown(int x)
    {
        if(a[x].cov!=2e9)
        {
            for(int i=0;i<a[x].siz;i++)a[x].s[i]=a[x].cov;
            a[x].cov=2e9,a[x].rev=0;
            return;
        }
        if(!a[x].rev)return;
        for(int i=0,j=a[x].siz-1;i<j;i++,j--)swap(a[x].s[i],a[x].s[j]);
        a[x].rev=0;
    }
    void pushup(int x)
    {
        a[x].sum=a[x].lis=a[x].llis=a[x].rlis=0;
        int n=a[x].siz;
        if(n==0)return;
        for(int i=0;i<n;i++)a[x].sum+=a[x].s[i];
        a[x].llis=a[x].s[0];
        for(int i=1,ss=a[x].s[0]+a[x].s[1];i<n;i++,ss+=a[x].s[i])a[x].llis=max(a[x].llis,ss);
        a[x].rlis=a[x].s[n-1];
        for(int i=n-2,ss=a[x].s[n-1]+a[x].s[n-2];i>=0;i--,ss+=a[x].s[i])a[x].rlis=max(a[x].rlis,ss);
        a[x].lis=a[x].s[0];
        for(int i=1,ss=a[x].s[0];i<n;i++)ss=max(ss,0)+a[x].s[i],a[x].lis=max(a[x].lis,ss);
    }
    void add(int x,int y,int len,int *s)
    {
        if(y!=-1)
        {
            pushdown(y);
            a[y].siz=len,a[y].nex=a[x].nex;
            memcpy(a[y].s,s,len*sizeof(int));
            pushup(y);
        }
        a[x].nex=y;
    }
    void merge(int x,int y)
    {
        pushdown(x),pushdown(y);
        memcpy(a[x].s+a[x].siz,a[y].s,a[y].siz*sizeof(int));
        a[x].siz+=a[y].siz,a[x].nex=a[y].nex,pushup(x),del(y);
    }
    void split(int x,int pos)
    {
        if(x==-1||pos==a[x].siz)return;
        int t=newnode();
        pushdown(x);
        add(x,t,a[x].siz-pos,a[x].s+pos);
        a[x].siz=pos,pushup(x);
    }
    void insert(int x,int len,int *s)
    {
        if(len==0)return;
        int now=pos(x),nex=now,tot=0,t=-1;
        split(now,x);
        for(;tot+B<=len;tot+=B)
        {
            t=newnode();
            add(nex,t,B,s+tot);
            nex=t;
        }
        if(tot<len)t=newnode(),add(nex,t,len-tot,s+tot);
        if(nex!=0&&t!=-1&&a[nex].siz+a[t].siz<=B)merge(nex,t);
        if(t!=-1&&a[t].nex!=-1&&a[t].siz+a[a[t].nex].siz<=B)merge(t,a[t].nex);
        if(now!=0&&a[now].nex!=-1&&a[now].siz+a[a[now].nex].siz<=B)merge(now,a[now].nex);
    }
    void erase(int x,int len)
    {
        if(len==0)return;
        int now=pos(x);split(now,x-1);
        int nex=a[now].nex;len--;
        for(;nex!=-1&&len>=a[nex].siz;nex=a[nex].nex)len-=a[nex].siz;
        if(nex!=-1)split(nex,len+1),nex=a[nex].nex;
        for(int i=a[now].nex;i!=nex;i=a[now].nex)a[now].nex=a[i].nex,del(i);
        for(;nex!=-1&&a[now].siz+a[nex].siz<=B;nex=a[nex].nex)merge(now,nex);
    }
    void modify(int p1,int len,int v)
    {
        if(len==0)return;
        int p2=p1+len-1;
        int bl=pos(p1),br=pos(p2);
        if(bl==br)
        {
            pushdown(bl);
            for(int i=p1-1;i<p2;i++)a[bl].s[i]=v;
            pushup(bl);return;
        }
        for(int i=a[bl].nex;i!=br;i=a[i].nex)
        {
            a[i].cov=v;
            a[i].sum=v*a[i].siz;
            if(v<0)a[i].lis=a[i].llis=a[i].rlis=v;
            else a[i].lis=a[i].llis=a[i].rlis=a[i].sum;
        }
        pushdown(bl),pushdown(br);
        for(p1--;p1<a[bl].siz;p1++)a[bl].s[p1]=v;
        for(p2--;p2>=0;p2--)a[br].s[p2]=v;
        pushup(bl),pushup(br);
    }
    void reverse(int p1,int len)
    {
        if(len==0)return;
        int p2=p1+len-1;
        int bl=pos(p1),br=pos(p2);
        if(bl==br)
        {
            pushdown(bl);
            for(int i=p1-1,j=p2-1;i<j;i++,j--)swap(a[bl].s[i],a[bl].s[j]);
            pushup(bl);return;
        }
        split(bl,p1-1),split(br,p2);
        int nowl=a[bl].nex,nowr=br;br=a[br].nex;
        vector<int>vec;
        a[bl].nex=-1;
        for(int i=nowl;i!=br;)
        {
            a[i].rev^=1;
            swap(a[i].llis,a[i].rlis);
            vec.push_back(i);
            int t=a[i].nex;
            a[i].nex=-1,i=t;
        }
        for(int i=bl,j=vec.size()-1;j>=0;i=a[i].nex,j--)a[i].nex=vec[j];
        a[vec[0]].nex=br;
        if(a[bl].siz+a[a[bl].nex].siz<=B)merge(bl,a[bl].nex);
        if(!vec.empty()&&br!=-1&&a[vec[0]].siz+a[br].siz<=B)merge(vec[0],br);
    }
    int querysum(int p1,int len)
    {
        if(len==0)return 0;
        int p2=p1+len-1,ans=0;
        int bl=pos(p1),br=pos(p2);
        if(bl==br)
        {
            pushdown(bl);
            for(int i=p1-1;i<p2;i++)ans+=a[bl].s[i];
            return ans;
        }
        for(int i=a[bl].nex;i!=br;i=a[i].nex)ans+=a[i].sum;
        pushdown(bl),pushdown(br);
        for(p1--;p1<a[bl].siz;p1++)ans+=a[bl].s[p1];
        for(p2--;p2>=0;p2--)ans+=a[br].s[p2];
        return ans;
    }
    int querylis(int p1,int len)
    {
        int p2=p1+len-1;
        int bl=pos(p1),br=pos(p2);
        if(bl==br)
        {
            pushdown(bl);
            int ans=a[bl].s[p1-1],maxx=ans;
            for(int i=p1;i<p2;i++)
            {
                maxx=max(maxx,0)+a[bl].s[i];
                ans=max(ans,maxx);
            }
            return ans;
        }
        split(bl,p1-1),split(br,p2);
        int nowl=a[bl].nex,nowr=br;br=a[br].nex;
        vector<int>vec;
        for(int i=nowl;i!=br;i=a[i].nex)vec.push_back(i);
        if(vec.empty())return 0;
        if(vec.size()==1)return a[vec[0]].lis;
        int ans=a[vec[0]].lis,maxx=a[vec[0]].rlis;
        for(int i=1;i<vec.size();i++)
        {
            ans=max(ans,max(a[vec[i]].lis,maxx+a[vec[i]].llis));
            maxx=max(maxx+a[vec[i]].sum,a[vec[i]].rlis);
        }
        if(a[bl].siz+a[a[bl].nex].siz<=B)merge(bl,a[bl].nex);
        if(br!=-1&&a[nowr].siz+a[br].siz<=B)merge(nowr,br);
        return ans;
    }
}seq;
int tmp[N];
int main()
{
    int n=in(),m=in();
    for(int i=0;i<n;i++)tmp[i]=in();
    seq.insert(0,n,tmp);
    while(m--)
    {
        string s="";char c=getchar();
        while(!isalpha(c))c=getchar();
        while(isalpha(c)||c=='-')s.push_back(c),c=getchar();
        int pos=0,tot=0;
        if(s!="GET")pos=in(),tot=in();
        if(s=="INSERT")
        {
            for(int i=0;i<tot;i++)tmp[i]=in();
            seq.insert(pos,tot,tmp);
        }
        else if(s=="DELETE")seq.erase(pos,tot);
        else if(s=="MAKE-SAME")seq.modify(pos,tot,in());
        else if(s=="REVERSE")seq.reverse(pos,tot);
        else if(s=="GET-SUM")out(seq.querysum(pos,tot)),putchar('\n');
        else if(s=="GET")out(seq.querysum(in(),1)),putchar('\n');
        else out(seq.querylis(pos,tot)),putchar('\n');
    }
    return 0;
}

其实挺难调的，细节超多。

有个双倍经验，也差不多。

如果有错误或者不清楚欢迎评论或私信指出。