【题解】[Scoi2013] 多项式的运算 splay BZOJ – 3323 LUOGU – 3278

于由XZYQvQ发布

1. 题目

2. 题解

可以说这题令我非常 angry。。。

其实不难，就一个 splay 区间加&区间乘，结果写我这么久！

我屮艸芔茻，因为在学校写的时候思路被中断了，所以代码就写得非常 Silly B 且不可 debug。。。

浪费我好多时间哟 QvQ

最后回家以后一下子就写出来惹 QvQ

其实我们只要灵活地运用 splay 的提取区间操作就行了。

对于区间加和区间乘应该没啥好说的。

唯一要注意的地方是要先下放乘法标记，再下放加法标记！

下放标记 (push_down) 的代码：

void M(LL a){e[a].d%=MOD,e[a].ptag%=MOD,e[a].mtag%=MOD;}
//整个节点 a 都取模，防爆
void pdown(LL a)
{
    LL l=e[a].s[0],r=e[a].s[1],t;
    if((t=e[a].mtag)!=1)//mtag 是乘法标记
    {
        if(l)e[l].d*=t,e[l].ptag*=t,e[l].mtag*=t,M(l);//d 是系数
        if(r)e[r].d*=t,e[r].ptag*=t,e[r].mtag*=t,M(r);
        e[a].mtag=1;
    }
    if(t=e[a].ptag)//ptag 是加法标记
    {
        if(l)e[l].d+=t,e[l].ptag+=t,M(l);
        if(r)e[r].d+=t,e[r].ptag+=t,M(r);
        e[a].ptag=0;
    }
}

然后区间次数加一的话，就等于将区间右端点的值加到区间右端点的右边的点上，再把区间右端点的值归零，最后区间顺时针旋转 1 个位置即可。

对此，我们可以先提取出只有右端点一个元素的区间（即区间 [r,r]），然后切断它与整个序列的联系，接着提取出只有左端点一个元素的区间（即区间 [l,l]），并 push_down 左儿子！并 push_down 左儿子！并 push_down 左儿子！（重要的事情说三遍！一定要记得 push_down！我? 前面就忘了！）。这时候左端点对应的节点没有左儿子，直接把已经与序列切断联系的右端点接到左端点的左儿子上，就相当于把区间旋转了 1 个位置。然后再提取出只有原来区间右端点右边的那个节点的区间（即区间 [r+1,r+1]），并把这个节点的值加上刚刚的右端点的值，并把刚刚的右端点的值设为 0。

于是我们就很愉悦♂地实现了这个 mulx 操作啦！

这个操作的代码：

void get_seg(LL&l,LL&r)//提取区间 [l,r]
{
    l=find_by_order(l),r=find_by_order(r+2);
    splay(l,0),splay(r,l); 
}
void work_mulx()
{
    LL l,r,t1,t2,tmp;
    IN(l),IN(r),l++,r++;//我的 splay 下标从 1 开始，所以所有位置都+1
    t1=t2=r,get_seg(t1,t2),tmp=e[t2].s[0];//提取区间 [r,r]
    e[t2].s[0]=e[tmp].f=0,pup(t2),pup(t1);//断开右端点与序列的联系
    t1=t2=l,get_seg(t1,t2),pdown(e[t2].s[0]);//提取区间 [l,l] 并 push_down！
    e[e[t2].s[0]].s[0]=tmp,e[tmp].f=e[t2].s[0];//把右端点接到左端点左边
    pup(e[t2].s[0]),pup(t2),pup(t1);//push_up 一下 QvQ
    t1=t2=r+1,get_seg(t1,t2);//提取区间 [r+1,r+1]
    e[e[t2].s[0]].d+=e[tmp].d,e[tmp].d=0;//加上右端点的值并清空右端点的值
}

这个故事告诉我们要灵活运用 splay 的获取区间操作 QvQ

查询操作就递归就行了，中序遍历。查询操作代码如下：

LL query(LL a)
{
    if(!a)return 0;
    pdown(a);//记得下放标记
    LL tot=query(e[a].s[0]);//遍历左子树
    tot=(tot+(e[a].d*xi)%MOD)%MOD,xi=xi*X%MOD;
    //X 是自变量 x 的值，xi 是累计到当前节点时 X 的 i 次方
    tot=(tot+query(e[a].s[1]))%MOD;//遍历右子树
    return tot;
}

还有一点小细节：

  • 一开始建树应该建大小为 $10^5+n+2$的大小的树，那个 2 是两个哨兵节点，初始节点值为 0（节点值保存系数），多了节点没关系的 QvQ，不影响答案
  • 记得开 long long QvQ 坑死惹！

整道题の代码：

#include <bits/stdc++.h>
#define MOD (20130426)
#define NS (200100)
using namespace std;
typedef long long LL;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
LL n,root,cnt,xi,X; 
char opt[10];
struct N{LL f,s[2],d,ptag,mtag,sz;}e[NS+10];
void M(LL a){e[a].d%=MOD,e[a].ptag%=MOD,e[a].mtag%=MOD;}
LL pos(LL a){return e[e[a].f].s[1]==a;}
void pup(LL a){e[a].sz=e[e[a].s[0]].sz+e[e[a].s[1]].sz+1;}
void pdown(LL a)
{
    LL l=e[a].s[0],r=e[a].s[1],t;
    if((t=e[a].mtag)!=1)
    {
        if(l)e[l].d*=t,e[l].ptag*=t,e[l].mtag*=t,M(l);
        if(r)e[r].d*=t,e[r].ptag*=t,e[r].mtag*=t,M(r);
        e[a].mtag=1;
    }
    if(t=e[a].ptag)
    {
        if(l)e[l].d+=t,e[l].ptag+=t,M(l);
        if(r)e[r].d+=t,e[r].ptag+=t,M(r);
        e[a].ptag=0;
    }
}
LL build(LL l,LL r,LL f)
{
    if(l>r)return 0;
    LL a=++cnt,mid=(l+r)>>1;e[a].f=f,e[a].mtag=1;
    e[a].s[0]=build(l,mid-1,a),e[a].s[1]=build(mid+1,r,a);
    pup(a);return a;
}
void rot(LL a)
{
    LL f=e[a].f,g=e[f].f,p=pos(a),q=pos(f);
    pdown(f),pdown(a);
    e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    if(e[a].f=g)e[g].s[q]=a;
    pup(f),pup(a);
}
void splay(LL a,LL t)
{
    for(;e[a].f!=t;rot(a))if(e[e[a].f].f!=t)
        if(pos(a)^pos(e[a].f))rot(a);
        else rot(e[a].f);
    if(!t)root=a;
}
LL find_by_order(LL k)
{
    LL a=root;
    while(a)
    {
        pdown(a);
        if(k<=e[e[a].s[0]].sz)a=e[a].s[0];
        else
        {
            k-=e[e[a].s[0]].sz+1;
            if(!k)return a;
            a=e[a].s[1];
        }
    }
    return 0;
}
void get_seg(LL&l,LL&r)
{
    l=find_by_order(l),r=find_by_order(r+2);
    splay(l,0),splay(r,l); 
}
void work_mul()
{
    LL l,r,v,a;
    IN(l),IN(r),IN(v),l++,r++;
    get_seg(l,r),a=e[r].s[0];
    e[a].d*=v,e[a].ptag*=v,e[a].mtag*=v,M(a);
}
void work_add()
{
    LL l,r,v,a;
    IN(l),IN(r),IN(v),l++,r++;
    get_seg(l,r),a=e[r].s[0];
    e[a].d+=v,e[a].ptag+=v,M(a);
}
void work_mulx()
{
    LL l,r,t1,t2,tmp;
    IN(l),IN(r),l++,r++;
    t1=t2=r,get_seg(t1,t2),tmp=e[t2].s[0];
    e[t2].s[0]=e[tmp].f=0,pup(t2),pup(t1);
    t1=t2=l,get_seg(t1,t2),pdown(e[t2].s[0]);
    e[e[t2].s[0]].s[0]=tmp,e[tmp].f=e[t2].s[0];
    pup(e[t2].s[0]),pup(t2),pup(t1);
    t1=t2=r+1,get_seg(t1,t2);
    e[e[t2].s[0]].d+=e[tmp].d,e[tmp].d=0; 
}
LL query(LL a)
{
    if(!a)return 0;
    pdown(a);
    LL tot=query(e[a].s[0]);
    tot=(tot+(e[a].d*xi)%MOD)%MOD,xi=xi*X%MOD;
    tot=(tot+query(e[a].s[1]))%MOD;
    return tot;
}
int main()
{
    IN(n),root=build(1,NS+2,0);
    while(n--)
        if(scanf("%s",opt),opt[0]=='m')
        {
            if(opt[3]=='x')work_mulx();
            else work_mul(); 
        }
        else if(opt[0]=='a')work_add();
        else
        {
            LL l=1,r=NS;
            IN(X),get_seg(l,r),xi=1;
            printf("%lld\n",query(e[r].s[0])); 
        }
    return 0;
}
分类： 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

4 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注