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

星·辉 · 2019-11-14 18:39:03 · 题解

搜索splay出来了这个题……

看了两眼，只有区间加值、区间乘值、区间右移一位、暴力查询，加上最近刚刚写了大分块，于是就有了这篇题解。

考虑mulx操作的本质：

相当于区间 [L,R-1] 右移一位再进行两个单点修改。

区间右移一位怎么做？如果正常的分块，我们会对每个在区间中的块，弹出一个数，加入一个（后面的）数。这样的好处是保证了每个块的大小在修改中不会改变。

但想要这样做，要将块中的数弹出并插入到上一个块后部，需要能够快速抵消块中tag的影响。

考虑本题中是否能够快速抵消块中tag影响。

因为有前两个操作，我们需要加法tag和乘法tag。这样一个块中的数 w 的实际值为 w\times mul + add 。考虑在不改变tag的情况下插入数 x （实际值），设插入后在块中这个数的值为 y ，则有 y\times mul + add = x 。由于这个方程是在模一个合数 20130426 情况下的，可能无整数解，故无法使用上述方法。

那怎么做？上块状链表吧。

块状链表

将每个块的大小由定长转为不定长思考。设需要右移的区间是 [l,r] ，这段区间最左和最右的散块是 B_l, B_r 。右移一位即为在第 l 个数前方插入一个数，并在第 r 个数后方删除一个数，再修改插入的那个数。即 B_l 的长度要增加 1 ， B_r 的长度减少 1 。

设块长 k ，则插入或删除块中的一个数的时间复杂度是 O(k) 的。从而单次mulx操作复杂度是 O(k + \dfrac{N}{k}) 的（ N 为多项式最大次数）。此时 k 取 \sqrt{N} 为最优。

然而插入或删除一个数之后块长就变化了，若经历大量操作后块太长或块过短（块数量太多）都会导致复杂度退化。

所以先将 k 设为 \sqrt{N} ，若某次mulx操作之后某个块的长度大于 2k ，就将其拆成两个块；某个块的长度小于 \dfrac{k}{2} ，就将它与下一个块合并。

这样就可以保证复杂度不会退化了。

实现时，细节较多。

虽然时间复杂度是 O(n\sqrt{n}) ，但是却还能勉强进第一页……果然平衡树的常数还是太大了……

#include<bits/stdc++.h>
namespace my_std{
    using namespace std;
    #define reg register
    #define Rint register int
    #define FOR(i,a,b) for(register int i=(a),ed_##i=(b);i<=ed_##i;++i)
    #define ROF(i,a,b) for(register int i=(a),ed_##i=(b);i>=ed_##i;--i)
    #define FORit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)+1;i!=ed_##i;++i)
    #define ROFit(templ,arr,i,a,b) for(register templ *i=(arr)+(a),*ed_##i=(arr)+(b)-1;i!=ed_##i;--i)
    #define MEM(x,v) memset(x,v,sizeof(x))
    #define Templ(T) template<typename T>
    inline int read(){
        int ans=0,f=1;char c=getchar();
        while(!isdigit(c)){ f^=(c=='-'); c=getchar(); }
        for(;isdigit(c);c=getchar()) ans=(ans<<1)+(ans<<3)+(c^48); return f?ans:-ans;
    }
    const int mod = 20130426, N = 100010, BN = 330, BLO = 325;
    inline void inc(int &x, const int &y){ x += y; if(x >= mod) x -= mod; }
    inline int ksm(int x, int y){
        x %= mod;
        int res=1;
        for(; y; y >>= 1, x = 1ll * x * x % mod) if(y & 1) res = 1ll * res * x % mod;
        return res;
    }
}
using namespace my_std;

int n;

struct Block;
inline void del_Block(Block *B);
inline Block *new_Block();

struct Block{
    Block *nxt;
    int a[BN << 1], add, mul, cnt, beg;
    inline void init(){
        nxt = nullptr;
        MEM(a, 0);
        add = 0, mul = 1, beg = 0, cnt = 0;
        return; 
    }
    inline void push_down(){
        if(mul == 1 && add == 0) return;
        FOR(i, 1, cnt) a[i] = (1ll * a[i] * mul + add) % mod;
        mul = 1, add = 0;
        return;
    }
    inline void split(){//将过大的块拆成两个
        reg Block *to = nxt;
        nxt = new_Block();
        nxt->init();
        nxt->nxt = to;
        nxt->beg = beg + BLO;
        nxt->add = add, nxt->mul = mul;
        nxt->cnt = cnt - BLO, cnt = BLO;
        FOR(i, 1, nxt->cnt) nxt->a[i] = a[i + BLO];
        return;
    }
    inline void merge(){//将过小的块与后面合并
        reg Block *to = nxt, *toto = nullptr;
        if(to == nullptr) return;
        toto = to->nxt;
        this->push_down(), to->push_down();
        if(cnt + to->cnt >= (BLO << 1)){//如果合并之后大小又过大了，就不合并，从下一个块中挖一段到这个块中
            FOR(i, 1, BLO - cnt) a[i + cnt] = to->a[i];
            FOR(i, BLO - cnt + 1, to->cnt) to->a[i - BLO + cnt] = to->a[i];
            to->cnt += cnt - BLO, to->beg -= cnt - BLO;
            cnt = BLO;
            return;
        }
        FOR(i, 1, to->cnt) a[i + cnt] = to->a[i];
        nxt = toto;
        cnt += to->cnt;
        to->nxt = nullptr;
        del_Block(to);
        return;
    }
    inline void check(){
        if(cnt > (BLO << 1)) return split();
        if(cnt <= (BLO >> 1)) return merge();
        return;
    }
};
Block *St, *del[BN << 1];//合并的时候需要垃圾回收
int dtop;

inline void del_Block(Block *B){
    del[dtop++] = B;
    return;
}
inline Block *new_Block(){
    return dtop ? del[--dtop] : new Block;
}

inline void Build(){
    St = new_Block();
    St->init();
    reg Block *now = St;
    FOR(i, 1, ceil(N / (double)BLO)){
        now->add = 0, now->mul = 1, now->beg = (i - 1) * BLO - 1, now->cnt = BLO;
        FOR(j, 1, now->cnt) now->a[j] = 0;
        now->nxt = (i == ed_i) ? nullptr : new_Block();
        if(now->nxt != nullptr) now->nxt->init();
        now = now->nxt;
    }
    return;
}

inline void update_add(int l, int r, int v){//add
    reg Block *now = St;

    while(now->beg + now->cnt < l) now = now->nxt;

    if(now->beg + now->cnt >= r){
        now->push_down();
        FOR(i, l - now->beg, r - now->beg) inc(now->a[i], v);
        return;
    }

    now->push_down();
    FOR(i, l - now->beg, now->cnt) inc(now->a[i], v);

    now = now->nxt;
    while(now->beg + now->cnt < r){
        inc(now->add, v);
        now = now->nxt;
    }

    now->push_down();
    FOR(i, 1, r - now->beg) inc(now->a[i], v);

    return;
}

inline void update_mul(int l, int r, int v){//mul
    reg Block *now = St;

    while(now->beg + now->cnt < l) now = now->nxt;

    if(now->beg + now->cnt >= r){
        now->push_down();
        FOR(i, l - now->beg, r - now->beg) now->a[i] = 1ll * now->a[i] * v % mod;
        return;
    }

    now->push_down();
    FOR(i, l - now->beg, now->cnt) now->a[i] = 1ll * now->a[i] * v % mod;

    now = now->nxt;
    while(now->beg + now->cnt < r){
        now->mul = 1ll * now->mul * v % mod, now->add = 1ll * now->add * v % mod;
        now = now->nxt;
    }

    now->push_down();
    FOR(i, 1, r - now->beg) now->a[i] = 1ll * now->a[i] * v % mod;

    return;
}

inline int query(int v){//暴力query
    Rint res = 0, bt = 0, Add, Mul;
    reg Block *now = St;

    while(now != nullptr){
        Add = now->add, Mul = now->mul;
        FOR(i, 1, now->cnt) inc(res, ((1ll * now->a[i] * Mul + Add) % mod) * ksm(v, bt++) % mod);
        now = now->nxt;
    }

    return res;
}

inline void update_shift(int l, int r){//mulx
    reg Block *now = St, *lst = nullptr, *x = nullptr;

    while(now->beg + now->cnt < l) now = now->nxt;

    if(now->beg + now->cnt >= r){
        now->push_down();
        inc(now->a[r - now->beg], now->a[r - now->beg - 1]);
        ROF(i, r - now->beg - 1, l - now->beg + 1) now->a[i] = now->a[i - 1];
        now->a[l - now->beg] = 0;
        return;
    }

    now->push_down();
    now->cnt++;
    ROF(i, now->cnt, l - now->beg + 1) now->a[i] = now->a[i - 1];
    now->a[l - now->beg] = 0;
    x = now;

    lst = now, now = now->nxt;
    while(now->beg + now->cnt < r){
        now->beg++;
        lst = now, now = now->nxt;
    }

    if(now->beg + 1 == r){//细节，这里如果 r 是块内的第一个数就应该把上一个块的最后一个数删除
        lst->push_down();
        now->push_down();
        inc(now->a[1], lst->a[lst->cnt]);
        lst->cnt--;
        lst->check(), x->check();
        return;
    }

    now->push_down();
    inc(now->a[r - now->beg - 1], now->a[r - now->beg]);
    now->cnt--;
    FOR(i, r - now->beg, now->cnt) now->a[i] = now->a[i + 1];
    now->beg++;
    now->check(), x->check();

}

int main(){
    n = read();
    Build();
    char opt[10];
    Rint l, r;
    FOR(i, 1, n){
        scanf("%s", opt);
        l = read();
        if(opt[0] != 'q') r = read();
        if(opt[0] == 'a'){
            update_add(l, r, read() % mod);
            continue;
        }
        if(opt[0] == 'q'){
            printf("%d\n", query(l % mod));
            continue;
        }
        if(strlen(opt) == 4){
            update_shift(l, r + 1);//为了方便将 r 加了 1
            continue;
        }
        update_mul(l, r, read() % mod);
    }
    return 0;
}