P2042 [NOI2005] 维护数列 题解
KobeBeanBryantCox · · 题解
P2042 [NOI2005] 维护数列 题解
题目传送门。
块状链表！！！
虽然是块状链表但是比大多数平衡树都跑得快！
题意
略。
思路
首先我们想到了平衡树。
但是为了显得与众不同一点，我偏偏就要用块状链表。
首先块状链表的常规操作读者们在这里看吧，我参考了这里的写法（这篇文章不是我写的，侵权请联系删除）。
考虑剩下几个操作。
首先根据这个题类似的操作，每个块要记录
分裂和合并的时候需要对块暴力重新计算上述东西，复杂度正确是因为我们一次修改只会至多两次分裂和合并。
然后要给每一个块打上
考虑翻转。
把散块分裂成两个，然后就变成全部都是整块了。
整块打翻转标记，并且颠倒顺序即可。
考虑求 LIS（这里我们假装查询的是区间 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);
}
return ans;求和和查询区间和就是整块加，散块暴力即可，不需要分裂块。
然后注意特判每一个操作，在同一个块内的情况，暴力修改即可。
块的大小取
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=5e5+10,B=707;
struct block_list
{
struct node
{
int siz,nex;int s[B<<2];
int sum,lis,llis,rlis;
int rev,cov;
node(){cov=1e9;} // 注意不能设成 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=1e9;
}
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!=1e9)
{
for(int i=0;i<a[x].siz;i++)a[x].s[i]=a[x].cov;
a[x].cov=1e9,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() // 这里我就没有写成区间的形式了
{
vector<int>vec;
for(int i=a[0].nex;i!=-1;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);
}
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!="MAX-SUM")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 out(seq.querylis()),putchar('\n');
}
return 0;
}挺难调的，细节超多，放一个有调试信息的版本。
有个双倍经验，也差不多。
如果有错误或者不清楚欢迎评论或私信指出。