【清华集训 2014】玄学 (UOJ46)

题意

给定一个数列，一个取模用的数字 $m$，和一些形如 “ 将 $[l,r]$内的数 $x$变为 $(ax+b)\bmod m$” 这样的形式的操作。每次可能新增一个操作，或者询问：如果将已经出现的编号为 $[l,r]$的这些操作依次进行后，原始数列中第 $p$位的数字会变为多少。询问不会影响到原始数列。强制在线。数字个数 $n\leq 10^5$，新增操作 $m\leq 10^5$，询问个数 $q\leq 5\times 10^5$，下文将默认这些数字同阶。

初步分析

由于这些诡异的操作并不一定有逆，因此我们不能利用操作的前缀和得到答案。而且操作没有交换律，只有结合律。

这时，我们可能需要一些可以维护二维信息的数据结构。比如树套树什么的。

但是，如果在这道题上使用树套树，可能有点大材小用了。题目中的操作只会依次添加，不会修改之前的操作，并不是完整的二维信息问题。因此使用树套树意义不大。

所以，我们还可以用一些特殊的技巧解决这个问题。

在接下来的叙述中，将用函数 $f(x)$表示一个操作。

解法 1：分块的妙用

在数据结构题中，一个常见的技巧就是将修改按时间分块。比如每隔 $\sqrt n$的时间就将数据结构重建一遍。

这个技巧在这道题里也适用。我们可以每隔 $\sqrt n$的时间将新来的操作重建为一个块 (可以使用线段树)，块内维护 $\forall {i\in[1,n]},f_i(x)$，也就是每个位置在这 $\sqrt n$个操作的作用下的变化。

对于每次询问，如果其包含某些整块，我们可以 $O(1)$直接取得一整块的 $f$，对于零散的部分，暴力判断每隔 $f$是否会对答案造成影响即可。

由于每个操作只会被所在的块重建一次，每次重建复杂度又是 $O(n)​$的，因此，时间复杂度为 $O(n\log n+n\sqrt n+q\sqrt n)​$，空间复杂度为 $O(n\sqrt n)​$，都略微有点大，在 UOJ 上只能得到 $80​$分。

想想哪里对时间复杂度有浪费，我们发现，有两点：

• 1. 由于每个块内只有 $\sqrt n​$个操作，本质不同的 $f_i(x)​$实际上只有 $O(\sqrt n)​$个，因此对于 $\forall {i\in [1,n]}​$都计算 $f_i(x)​$有点浪费。
• 2. 如果我们将块分的很大，对于整块的询问将很快，但是零散部分的询问很慢。块很小，两者也会一大一小。这样很难均衡。

对于第二个问题有一个比较好的优化。我们可以同时维护两个分块，一大一小。整块用大的询问，零散部分用小的询问，岂不是很爽。这样，由于时间复杂度的上限没有变 (因为空间复杂度为 $O(n^2/s)$导致小块大小 $s$不能太小)，我们还是认为时间复杂度为 $O(n\sqrt n)$。

然而，经过尝试，小块大小为 $180$，大块大小为 $4680$时，算法在随机数据下的效率最高，已经可以通过 UOJ 的全部数据。

再考虑能否通过优化第一个问题降低复杂度。显然是可以的，并且这样一来，空间复杂度也降了下来，我们甚至可以结合第二种方法达到更低的复杂度。

考虑到每一块内本质不同的 $i$不多，只有 $O(s)$个，而且都是连续的，我们就可以直接维护这些连续段。虽然说这样会导致复杂度套上一个 $\log$，但是接下来我们可以做的 (理论上可行) 事情将使复杂度远远降低，弥补这一个 $\log$带来的影响。

我们可以效仿第一种方法， 将小块大小设为 $S$，大块大小设为 $T\times S$，在小块中，由于块数较多，需要维护本质相同的连续段，而大块则不需要。因此单次询问的时间复杂度为：
$$
O(S+T\log N+\frac{N}{ST})
$$
最小化该函数，为华丽的 $O(N^{\frac{1}{3}}\log^{\frac{1}{3}}N)​$，比普通分块的 $O(N^\frac{1}{2})​$看上去好看多了。

当然，这还不是这种方法最牛逼的地方。如果多套几层分块，(比如 $k$层)，算法的复杂度将会是 (大约是，具体是什么取决于多少层分块维护了本质相同的连续段)$O(kN^\frac{1}{k+1}\log_2^\frac{k}{2(k+1)}N)$，当 $k$取 $8$或 $7$的时候取到最小值。添加操作的单次复杂度为 $O(k\log N)$，并不是瓶颈。

解法 2：时间线段树

上一种分块方法虽然很妙，但是有点难以实现。其中两层分块的做法我用了 165 行实现。如果分块层数更多，可能 165 行之内难以解决。

我们可以继续挖掘 “本质不同的连续段很少” 这个性质，将分块算法优化成一个全新的算法。如果我们每次不重新建立一个新块，而是将相邻两个块合并成一个新块，用类似线段树的结构维护合并的过程，将会更方便。

我们将每个新的操作添加到一棵时间线段树的叶子节点处。如果一个节点满了 (即保存的操作个数等于区间长度)，则将它的操作上传到父亲节点。每次询问则像普通线段树那样，在每个节点处的 “本质不同的连续段” 内二分查找对应位置的答案即可。

这样实现的时间复杂度为 $O(n\log n+q\log^2n)$

代码

下面给出分块做法 (仅对上文提到的第二个问题进行了优化)

#include <algorithm>
#include <iostream>
#include <assert.h>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MX 100005
#define BS 180
#define MUL 26

using namespace std;

template <typename T> void read(T& x)
{
    x = 0; char c = getchar(); bool f = 0;
    while(!isdigit(c) && c!='-') c = getchar();
    if(c == '-') f = 1, c = getchar();
    while(isdigit(c)) x = x*10+c-'0', c = getchar();
    if(f) x = -x;
}

int type, n, m, q;

struct NODE
{
    int a, b;

    NODE (const int &a0 = 1, const int &b0 = 0) : a(a0), b(b0) {}
    NODE f(const NODE &t) const {return NODE(1ll*a*t.a%m, (1ll*b*t.a+t.b)%m);}
    inline void f_(const NODE &t) {a = 1ll*a*t.a%m, b = (1ll*b*t.a+t.b)%m;}
};

struct SEGT
{
    #define ls (a<<1)
    #define rs (a<<1|1)
    #define mid ((l+r)>>1)

    NODE tre[MX*4];

    void psd(int a)
    {
        tre[ls].f_(tre[a]);
        tre[rs].f_(tre[a]);
        tre[a] = NODE();
    }

    void add(int a, int l, int r, int ql, int qr, const NODE &x)
    {
        if(ql<=l && r<=qr) tre[a].f_(x);
        else if(ql>r || qr<l) return;
        else psd(a), add(ls, l, mid, ql, qr, x), add(rs, mid+1, r, ql, qr, x);
    }

    void get(int a, int l, int r, NODE *seq)
    {
        if(l == r) seq[l] = tre[a];
        else psd(a), get(ls, l, mid, seq), get(rs, mid+1, r, seq);
    }

    void build(int a, int l, int r)
    {
        tre[a] = NODE();
        if(l != r) build(ls, l, mid), build(rs, mid+1, r);
    }

    #undef ls
    #undef rs
    #undef mid
} T;

struct BLOCK
{
    NODE opr[MX], stk[BS*MUL+1];
    int sl[BS*MUL+1], sr[BS*MUL+1];
    int top;

    NODE qur(int l, int r, int p)
    {
        NODE ret;
        for(int i=l; i<=r; i++)
            if(sl[i]<=p && p<=sr[i])
                ret.f_(stk[i]);
        return ret;
    }

    bool push(const NODE &x, int l, int r, int lim)
    {
        stk[++top] = x;
        sl[top] = l;
        sr[top] = r;
        if(top == lim)
        {
            T.build(1, 1, n);
            for(int i=1; i<=top; i++) T.add(1, 1, n, sl[i], sr[i], stk[i]);
            T.get(1, 1, n, opr);
            return true;
        }
        return false;
    }
} B[MX/BS+2], B2[MX/BS/MUL+2];

int val[MX];

void input()
{
    read(type); read(n); read(m);
    for(int i=1; i<=n; i++) read(val[i]);
    read(q);
}

inline int block(int x, int s) {return (x-1)/s+1;}
inline int bl(int x, int s) {return s*x-s+1;}
inline int br(int x, int s) {return s*x;}

void work()
{
    int cmd, a, b, c, d, lans = 0;
    int nowb = 1, nowb2 = 1;
    for(int i=1; i<=q; i++)
    {
        read(cmd);
        if(cmd == 1)
        {
            read(a); read(b); read(c); read(d);
            if(type&1) a ^= lans, b ^= lans;
            nowb += B[nowb].push(NODE(c, d), a, b, BS);
            nowb2 += B2[nowb2].push(NODE(c, d), a, b, BS*MUL);
        }
        else
        {
            read(a); read(b); read(c);
            if(type&1) a ^= lans, b ^= lans, c ^= lans;
            NODE x(0, val[c]);
            int ba = block(a, BS), bb = block(b, BS);
            int ba2 = block(a, BS*MUL), bb2 = block(b, BS*MUL);
            if(ba == bb) x.f_(B[ba].qur(a-bl(ba, BS)+1, b-bl(ba, BS)+1, c));
            else
            {
                x.f_(B[ba].qur(a-bl(ba, BS)+1, BS, c));
                if(ba2 < bb2-1)
                {
                    for(int i=ba+1; i<=block(br(ba2, BS*MUL), BS); i++) x.f_(B[i].opr[c]);
                    for(int i=ba2+1; i<=bb2-1; i++) x.f_(B2[i].opr[c]);
                    for(int i=block(bl(bb2, BS*MUL), BS); i<=bb-1; i++) x.f_(B[i].opr[c]);
                }
                else
                {
                    for(int i=ba+1; i<=bb-1; i++) x.f_(B[i].opr[c]);
                }
                x.f_(B[bb].qur(1, b-bl(bb, BS)+1, c));
            }
            lans = x.b;
            printf("%d\n", lans);
        }
    }
}

int main()
{
    input();
    work();
    return 0;
}