题解 P3278 【[SCOI2013]多项式的运算 】

· · 题解

这道题的题面，emm...，我也不想吐槽什么了

进入正题！

分析：

要求：

维护一个无穷多项式，次数≤100001

需要满足区间加法，区间移动，和查询（次数较少可O(n)查询）

这种区间修改问题，可以用看起来可以用线段树，树状数组，Splay，Treap，块状链表骗分，等等

但是是不是都可以用呢？

线段树和树状数组先排除，因为本蒟蒻还不会用线段树和树状数组直接区间移动（欢迎大神来写）

那么Splay和Treap选择那个呢？

当然要祭出 序列之王 Splay 了~

Treap也可以啦，但是本文暂时不讨论

首先介绍一下建图思路：

将中序遍历来代表次数，用key值来保存系数，build二分建图即可（就是快！）

等下就会知道为什么这样建图了

具体操作，具体分析

mul操作&add操作

目的：

1.将x^L到x^R这些项的系数乘上某个定值v

2.将x^L到x^R这些项的系数加上某个定值v

对于已经入门splay的人来说很easy吧

先将l-1旋至root，将r+1旋至ch[root][1]，于是需要操作的区间就是以ch[r][0]为root的子树

我们在ch[r][0]上打上乘法标记和加法标记即可

注意：

下传标记时记得先乘再加

而且下传乘法标记时，不仅需要更新子节点的key值，加法标记也需要一同更新

mulx操作

目的：

将x^L到x^R这些项乘上x变量

这个做法就比较巧妙了

我们需要将这个区间的次数都+1，想一想算式的变化，发现：

将这个序列向右平移一位，然后将r和r+1合并即可

那么我们建图时以中序遍历来代表次数的操作就派上用场了

我们找到操作序列中最左侧的一个点（中序遍历时最靠前的点）

为它增加一个key值为0的左儿子，即将l后面的整个序列中序遍历向后推移了一位

我们找到操作序列中最右侧的一个点（中序遍历时最靠后的点）

将其与r+1合并即可，即将r后面的整个序列中序遍历向前推移了一位

这样我们就平移完成了！

query操作

目的：

将某个定值v代入多项式F(x)，并输出代入后多项式的值，之后多项式还原为代入前的状况

因为这个操作的次数不会超过10次，直接O(n)遍历查询即可

自认为代码可读性比较好~dalao勿喷

Code：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 21000000
#define mod 20130426
#define maxn 400000
ll ch[maxn][2],f[maxn],key[maxn],size[maxn],add[maxn],rid[maxn],num[maxn];
ll root,sz,n,ANS,q;
char str[10];
ll read() {
    ll ans=0,flag=1;
    char c=getchar();
    while( (c>'9' || c<'0') && c!='-' ) c=getchar();
    if(c=='-') flag=-1,c=getchar();
    while(c>='0' && c<='9') ans=ans*10+c-'0',c=getchar();
    return ans*flag;
}
bool get(int x) {return ch[f[x]][1]==x;}
void update(int x) {size[x]=1+size[ch[x][0]]+size[ch[x][1]];}
void clear(int x) {ch[x][0]=ch[x][1]=f[x]=key[x]=size[x]=add[x]=rid[x]=0;}
void pushdown(int x) {
    int l=ch[x][0];
    int r=ch[x][1];
    if(rid[x]!=1) {
        if(l) {
            key[l]=(key[l]*rid[x])%mod;
            add[l]=(add[l]*rid[x])%mod;
            rid[l]=(rid[l]*rid[x])%mod;
        }
        if(r) {
            key[r]=(key[r]*rid[x])%mod;
            add[r]=(add[r]*rid[x])%mod;
            rid[r]=(rid[r]*rid[x])%mod;
        }
        rid[x]=1;
    }
    if(add[x]!=0) {
        if(l) {
            key[l]=(key[l]+add[x])%mod;
            add[l]=(add[l]+add[x])%mod;
        }
        if(r) {
            key[r]=(key[r]+add[x])%mod;
            add[r]=(add[r]+add[x])%mod;
        }
        add[x]=0;
    }
    return ;
}
void rotate(int x) {
    int fa=f[x],ffa=f[fa],w=get(x);
    pushdown(fa),pushdown(x);
    ch[fa][w]=ch[x][w^1],f[ch[fa][w]]=fa;
    ch[x][w^1]=fa,f[fa]=x;
    f[x]=ffa;
    if(ffa)
        ch[ffa][ch[ffa][1]==fa]=x;
    update(fa),update(x);
    return ;
}
void splay(int x,int tar) {
    for(int fa;(fa=f[x])!=tar;rotate(x))
        if(f[fa]!=tar)
            rotate(get(x)==get(fa)?fa:x);
    if(!tar)
        root=x;
    return ;
}
int findx(int x) {
    int now=root;
    while(1) {
        pushdown(now);
        if(ch[now][0] && x<=size[ch[now][0]])
            now=ch[now][0];
        else {
            int tmp=(ch[now][0]?size[ch[now][0]]:0)+1;
            if(x<=tmp) return now;
            x-=tmp;
            now=ch[now][1];
        } 
    }
}
int build(int l,int r,int fa) {
    if(l>r) return 0;
    int mid=(l+r)>>1;
    int now=++sz;
    f[now]=fa;
    rid[now]=1;
    size[now]=1;
    ch[now][0]=build(l,mid-1,now);
    ch[now][1]=build(mid+1,r,now);
    update(now);
    return now;
}
void MUL() {
    int l=read(),r=read();
    ll v=read();
    l=findx(l+1);
    r=findx(r+3);
    splay(l,0);
    splay(r,l);
    key[ch[ch[root][1]][0]]=(key[ch[ch[root][1]][0]]*v)%mod;
    add[ch[ch[root][1]][0]]=(add[ch[ch[root][1]][0]]*v)%mod;
    rid[ch[ch[root][1]][0]]=(rid[ch[ch[root][1]][0]]*v)%mod;
    return ;
}
void ADD() {
    int l=read(),r=read();
    ll v=read();
    l=findx(l+1);
    r=findx(r+3);
    splay(l,0);
    splay(r,l);
    key[ch[ch[root][1]][0]]=(key[ch[ch[root][1]][0]]+v)%mod;
    add[ch[ch[root][1]][0]]=(add[ch[ch[root][1]][0]]+v)%mod;
    return ;
}
void MULX() {
    int l=read(),r=read();
    l=findx(l+1);
    r=findx(r+3);
    splay(l,0);
    splay(r,l);

    pushdown(l),pushdown(r);

    int now=r;
    while(ch[now][0])
        pushdown(now),now=ch[now][0];
    pushdown(now);
    ch[now][0]=++sz;
    clear(sz);
    f[sz]=now;
    rid[sz]=1;
    size[sz]=1;
    while(now)
        update(now),now=f[now];

    now=ch[r][0];
    while(ch[now][1])
        pushdown(now),now=ch[now][1];
    pushdown(now);
    key[r]=(key[r]+key[now])%mod;
    int fa=f[now],w=get(now);
    if(ch[now][0]) {
        ch[fa][w]=ch[now][0];
        f[ch[fa][w]]=fa;
    }
    else
        ch[fa][w]=0;
    clear(now);
    while(fa)
        update(fa),fa=f[fa];

    return ;
}
void print(int x) {
    pushdown(x);
    if(ch[x][0])
        print(ch[x][0]);
    if(q!=-1)
        ANS=(ANS+(num[q]*key[x])%mod)%mod;
    q++;
    if(ch[x][1])
        print(ch[x][1]);
    return ;
}
void QUERY() {
    ll v=read();
    ANS=0,q=-1;
    if(!v) {
        puts("0");
        return ;
    }
    num[0]=1;
    for(int i=1;i<=100001;i++)
        num[i]=(num[i-1]*v)%mod;
    print(root);
    printf("%lld\n",ANS);
    return ;
}
int main() {
    n=read();
    root=build(1,100100,0);
    while(n--) {
        scanf("%s",str);
        if(str[0]=='m' && strlen(str)==3)
            MUL();
        else if(str[0]=='a')
            ADD();
        else if(str[0]=='m' && strlen(str)==4)
            MULX();
        else if(str[0]=='q')
            QUERY();
    }
    return 0;
}

PS: 话说你知道2014年四川省选是什么时候么？

答案就在博客中哦~