【题解】玄学 线段树 Uoj#46 ——quhengyi11

传送门

题解

思路比较巧妙

我们根据操作的时间顺序维护一棵线段树，每个节点维护一个 $vector$，里面的每个点 $(p,a,b)$表示从上一个数 $+1$的位置到位置 $p$的所有数 $\times a + b$

具体来讲，如果我们有一个长度为 $n$的数列需要维护，一个操作区间 (当然也可以是一个操作，在线段树里体现成一个点) 里面将数列 $[2,4]$里的数 $\times 2 + 4$，那么这个点的 $vector={(1, 1, 0), (4, 2, 4), (n, 1, 0)}$

然后我们就每次将一个操作插入到这个线段树里面，查询的时候显然只需要访问 $logn$的操作区间，并且只需要取位置 $k$那个点的信息 (二分 $logn$)，所以查询一次的复杂度是 $log^2n$，因为二分的时候那个 $vector$不是严格 $n$级别的，所以这个操作的常数还很小。

那么考虑分析插入的复杂度，每次插入会影响到 $logn$个点的 $vector$，在合并子节点的 $vector$的时候复杂度是 $vector$里面的元素个数，比较糟糕的一件事情是，想象有 $10w$个操作，那么区间 $[1,5w]$，会被影响 $5w$次，然后复杂度还是一个等差数列求和，就变成了平方级别的，gg 了

其实仔细想想，上面那个操作很浪费了啦，你会发现第 $4w$个操作的时候我们并不需要维护 $[1,5w]$这个区间，当且仅当第 $5w$个操作才会影响到这个区间，并且复杂度是 $5w$，所以我们插入的操作均摊下来其实就是 $nlogn$的

$qhy$通过猫咪的第六感感觉这个证明有问题(我明天上文化课的时候再确认一下 qwq 最近总是不太自信)

(upd: 事实上这个证明应该是没有问题的，不过我最后的复杂度算错了 qwq，这里修正一下 (不过也就是一个常数的问题啦))

记 $v=2e9$（即值域）

复杂度是 $O(nlogv+nlognlogv)$

因为 $logn$那里是跑不满的所以是能跑过的啦

为了实现这个优化，你就在插入操作的时候特判一下就行了 (具体就是代码里有中文的那一行)

#include<bits/stdc++.h>
#define fo(i, a, b) for(int i = (a); i <= (b); ++i)
#define N 100005
#define inf 1000000005
#define ls u << 1
#define rs u << 1 | 1
#define pb push_back
int A, B, Q, n, m, data[N], id = 0;
struct node{
    int p, a, b;
    friend node operator + (node x, node y)
    {
        return (node) {std::min(x.p, y.p), 1ll * x.a * y.a % m, (1ll * x.b * y.a + y.b) % m};
    }
    friend bool operator < (node x, node y)
    {
        return x.p < y.p;
    }
};
std::vector<node> q[N << 2];
inline void modify (int u, int l, int r, int L, int R, int id)
{
    if (L == R)
    {
        if (l > 1) q[u].pb((node){l - 1, 1, 0});
        q[u].pb((node){r, A, B});
        if (r < n) q[u].pb((node){n, 1, 0});
        return;
    }
    int mid = L + R >> 1;
    if (id <= mid)
        modify(ls, l, r, L, mid, id);
    else
        modify(rs, l, r, mid + 1, R, id);
    if (id != R) return; //无用的更新
    int p1 = 0, p2 = 0, l1 = q[ls].size() - 1, l2 = q[rs].size() - 1;
    while (p1 <= l1 && p2 <= l2)
    {
        q[u].pb(q[ls][p1] + q[rs][p2]);
        if (q[ls][p1].p == q[rs][p2].p)
        {
            ++p1; ++p2;
        }
        else
        {
            (q[ls][p1].p < q[rs][p2].p) ? ++p1 : ++p2;
        }
    }
    while (p1 <= l1) q[u].pb(q[ls][p1++]);
    while (p2 <= l2) q[u].pb(q[rs][p2++]);
}
inline int find (int u, int pos)
{
    int l = 0, r = q[u].size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (pos <= q[u][mid].p) r = mid;
        else l = mid + 1;
    }
    return l;
}
inline node query (int u, int l, int r, int L, int R, int pos)
{
    if (l <= L && R <= r)
    {
        return q[u][find(u, pos)];
    }
    node ret = (node) {pos, 1, 0};
    int mid = L + R >> 1;
    if (l <= mid) ret = ret + query(ls, l, r, L, mid, pos);
    if (mid < r) ret = ret + query(rs, l, r, mid + 1, R, pos);
    return ret;
}
int main ()
{
    int T;
    scanf("%d", &T); T = T & 1;
    scanf("%d %d", &n, &m);
    fo (i, 1, n) scanf("%d", &data[i]);
    scanf("%d", &Q);
    int opt, l, r, ans = 0;
    node now;
    while (Q--)
    {
        scanf("%d %d %d %d", &opt, &l, &r, &A);
        if (T) {l ^= ans; r ^= ans;}
        if (opt == 1)
        {
            scanf("%d", &B);
            ++id;
            modify(1, l, r, 1, N, id);
        }
        else
        {
            if (T) A ^= ans;
            now = query(1, l, r, 1, N, A);
            ans = (1ll * data[A] * now.a + now.b) % m;
            printf("%d\n", ans);
        }
    }
    return 0;
}