BZOJ3323 SCOI2013 多项式的运算

AC链接：传送门

题目分析：

　　一道比较难写的splay模板题，可以看出scoi与hnoi相比，思维难度略低。

　　首先观察操作4，题目限制操作4的个数不会超过10个，但是经过分析可以发现题目中的无穷多项式是唬人的，最多的一项只会到达2*10⁵级别，那么每一次用O(n)可以计算，最多十次仅O(10n)，因此这一部分可以暴力解决。

　　忽略操作3，那么把多项式的每一项看作splay上的第i个点，预先建好n个点会使问题变简单许多，加法和乘法可以用标记解决，那么在没有操作3的情况下有一个O(nlogn)的splay做法。

　　加入操作3，操作3在[l,r]上乘以x，仅仅只会平移一项，那么我们将这一步拆分成下面独立的几步：

　　　　1.找到第l项，第r项与第r+1项所对应的结点的值。

　　　　2.将第r+1项所对应的结点的data加上第r项所对应的结点的data。

　　　　3.旋转，提取区间[l,r]。

　　　　4.删除第r项对应的结点。

　　　　5.给区间[l,r]对应的结点打上项数+1的标记，这时候我们发现，它们在splay中的相对位置没有改变！因此这个做法是成立的。

　　　　6.补充第l项对应的结点，用删除的结点补充即可。

题目难点：

　　这道题的难点在于代码的难写程度。维护三个标记是其一大恶心之处，但是其中的项+1标记与另外两个标记是独立的。

　　另外两个标记的维护与洛谷的某道线段树练习相似。

　　我们先让有乘法标记时乘法优于加法处理，那么当每个乘法标记被打上的时候，我们需要下放结点上的加法标记。但是打加法标记时不需要下放乘法标记，这样标记下传是O(1)的。

　　

代码如下：

　　

#include<bits/stdc++.h>
#define L (t[now].ch[0])
#define R (t[now].ch[1])
using namespace std;

typedef long long ll;

const ll maxn = 300010;
const ll mod = 20130426;
struct node{
    ll data;
    ll num,ch[2],fa;
    ll lznum,lzmul,lzad;
    node(){lzmul=1;data=num=ch[0]=ch[1]=fa=lznum=lzad=0;}
}t[maxn];
ll n,root=1,nb=1;

void r0(ll now,ll dr){ // 0 left ,1 right
    ll son = t[now].ch[dr],fa = t[now].fa,gf = t[fa].fa;
    t[son].fa = fa; t[fa].ch[dr^1] = son;
    t[now].ch[dr] = fa; t[fa].fa = now; t[now].fa = gf;
    if(t[gf].ch[0] == fa && gf != 0){t[gf].ch[0] = now;return;}
    if(t[gf].ch[1] == fa && gf != 0){t[gf].ch[1] = now;return;}
    root = now;
}

void push_down1(ll now){
    t[now].num+=t[now].lznum;
    t[L].lznum+=t[now].lznum;
    t[R].lznum+=t[now].lznum;
    t[now].lznum = 0;
}

void push_down2(ll now){
    t[now].data *= t[now].lzmul; t[now].data  %= mod;
    t[L].lzmul*=t[now].lzmul; t[L].lzmul %= mod;
    t[R].lzmul*=t[now].lzmul; t[R].lzmul %= mod;
    t[L].lzad*=t[now].lzmul; t[L].lzad %= mod;
    t[R].lzad*=t[now].lzmul; t[R].lzad %= mod;
    t[now].lzmul = 1;
}

void push_down3(ll now){
    t[now].data += t[now].lzad; t[now].data %= mod;
    t[L].lzad += t[now].lzad; t[L].lzad %= mod;
    t[R].lzad += t[now].lzad; t[R].lzad %= mod;
    t[now].lzad = 0;
}

ll fdnum(ll wt,ll now){
    if(t[now].lznum)push_down1(now);
    if(t[now].lzmul != 1)push_down2(now);
    if(t[now].lzad)push_down3(now);
    if(t[now].num == wt) return now;
    if(t[now].num > wt) return fdnum(wt,L);
    else return fdnum(wt,R);
}

stack <ll> sta;
void splay(ll now,ll fwd = 0){
    ll fnow = now;
    while(fnow != fwd) sta.push(fnow),fnow=t[fnow].fa;
    while(!sta.empty()){
    ll k=sta.top();sta.pop();
    if(t[k].lznum)push_down1(k);
    if(t[k].lzmul != 1)push_down2(k);
    if(t[k].lzad)push_down3(k);
    }
    if(now == fwd)return;
    while(t[now].fa != fwd){
    if(t[t[now].fa].fa == fwd){
        if(t[t[now].fa].ch[1] == now) r0(now,0);
        else r0(now,1);
    }else{
        ll f = t[now].fa;
        if(t[f].ch[0] == now){
        if(t[t[f].fa].ch[0] == f) r0(f,1),r0(now,1);
        else r0(now,1),r0(now,0);
        }else{
        if(t[t[f].fa].ch[0] == f) r0(now,0),r0(now,1);
        else r0(f,0),r0(now,0);
        }
    }
    }
}

void insert(ll now,ll dt,ll wtis){
    while(true){
    if(t[now].lznum) push_down1(now);
    if(t[now].lzmul!=1) push_down2(now);
    if(t[now].lzad) push_down3(now);
    if(t[now].num > dt){
        if(t[now].ch[0])now = t[now].ch[0];
        else{t[now].ch[0]=wtis;t[wtis].fa = now;splay(now);break;}
    }else{
        if(t[now].ch[1])now = t[now].ch[1];
        else{t[now].ch[1]=wtis;t[wtis].fa = now;splay(now);break;}
    }
    }
}

void mul(){
    ll a,b;ll v; scanf("%lld%lld%lld",&a,&b,&v);v %= mod;
    b = fdnum(b+1,root);splay(b);
    if(a == 0){
    push_down2(t[root].ch[0]);
    push_down3(t[root].ch[0]);
    t[t[root].ch[0]].lzmul = v;
    } else{
    a = fdnum(a-1,root);splay(a,root);
    ll now = t[root].ch[0];
    push_down2(R); push_down3(R);
    t[R].lzmul = v;t[R].lzmul %= mod;
    }
}

void add(){
    ll a,b;ll v; scanf("%lld%lld%lld",&a,&b,&v);v %= mod;
    b = fdnum(b+1,root);splay(b);
    if(a == 0) t[t[root].ch[0]].lzad += v,t[t[root].ch[0]].lzad %= mod;
    else{
    a=fdnum(a-1,root);splay(a,root);
    ll now = t[root].ch[0];t[R].lzad += v;t[R].lzad %= mod;
    }
}

void mov(){
    ll a,b; scanf("%lld%lld",&a,&b);
    ll za = a,zb = b;
    splay(fdnum(b,root));
    ll nbb = fdnum(b+1,root);
    splay(nbb,root);
    t[t[t[root].ch[1]].ch[1]].fa = root;
    t[root].ch[1] = t[t[root].ch[1]].ch[1];
    t[root].data += t[nbb].data; t[root].data %= mod;
    t[nbb].ch[0] = t[nbb].ch[1] = t[nbb].fa = 0;
    t[nbb].num = a; t[nbb].data = 0; t[nbb].lznum = t[nbb].lzad = 0;
    t[nbb].lzmul = 1;
    splay(fdnum(b+2,root));
    if(a == 0){
    t[t[root].ch[0]].lznum++;
    }else{
    splay(fdnum(a-1,root),root);
    t[t[t[root].ch[0]].ch[1]].lznum++;
    }
    insert(root,a,nbb);
}

queue <ll> q;
ll sm[maxn];
int ddd[maxn];
void force(){
    ll v; scanf("%lld",&v);v %= mod;sm[0] = 1;
    for(int i=1;i<=2e5;i++) sm[i] = sm[i-1]*v,sm[i] %= mod;
    q.push(root);
    ll ans = 0;
    while(!q.empty()){
    ll k = q.front();q.pop();
    if(t[k].lznum) push_down1(k);
    if(t[k].lzmul!=1) push_down2(k);
    if(t[k].lzad) push_down3(k);
    //ddd[t[k].num] = t[k].data;
    ans += sm[t[k].num]*t[k].data;
    ans %= mod;
    if(t[k].ch[0] != 0) q.push(t[k].ch[0]);
    if(t[k].ch[1] != 0) q.push(t[k].ch[1]);
    }
    //for(int i=0;i<=10;i++) cout<<ddd[i]<<" ";
    printf("%lld
",ans);
}

void read(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
    char C = getchar(),P=getchar();
    while(P != ' '){C = P;P=getchar();}
    switch(C){
    case 'l':{mul();break;}
    case 'd':{add();break;}
    case 'x':{mov();break;}
    default:{force();}
    }
    }
}

int main(){
    for(int i=1;i<=(int)2e5+10;i++) {t[++nb].num = i;insert(root,i,nb);}
    read();
    return 0;
}