题解：P16497 东风归故里，托此报微酬

· · 题解

唐氏做法。建议不要学习，更不要场写。

但是如果你想要卡掉 findnext 的那个 \log，本篇题解非常欢迎你。

理论复杂度最优，实际效率洛谷第三。

原题就是让你求序列中的非严格前缀最大值个数。

因为只有增大而没有减小，所以每次操作 p 的时候：

设操作前，序列中非严格前缀最大值的位置是 x_1, x_2, \dots, x_k。设 x_t \le p < x_{t + 1}。

如果 a_p 在修改之后有 a_p < a_t，那么说明 p 仍然不是非严格前缀最大值的位置，不用管它。

否则，把 p 加入非严格前缀最大值位置集合中。设对于所有 i \in [t + 1, r] 都有 a_p > a_i，那么 t + 1, t + 2, \dots, r 都不再是非严格前缀最大值的位置，把它们从非严格前缀最大值位置集合中删掉。

由于每次操作最多会增加 1 个非严格前缀最大值位置，所以总非严格前缀最大值位置个数是 O(n + q) 的，所以也最多删 O(n + q) 次。考虑用 set 维护非严格前缀最大值位置集合，你就会了 O((n + q) \log n)。

看一眼时限，450ms 的意思一定是所有测试点加起来一共 450ms，这个做法显然是过不了的。考虑卡常。

考虑用 bool 表示每个位置是否是非严格前缀最大值位置。这样你可以每 64 个 bool 压成一个 unsigned long long，做到 O\left(\dfrac{n(n + q)}{w}\right)。你可以用一些位运算快速找到一个位置的上一个为 1 的位置和下一个为 1 的位置。

又考虑到你可以再次用一个长度为 O\left(\dfrac{n}{w}\right) 的 bool 数组表示每个 unsigned long long 是否不为 0，然后你又可以用长度为 O\left(\dfrac{n}{w^2}\right) 的unsigned long long 数组来表示这个 bool 数组，如此反复下去。这样最多套娃三层，因为 w^3 = 262144 > n。所以你就可以用这种方法做到 O((n + q) \log_{64} n)。

#include <cstdio>
namespace FastIn
{
    const int S = 4e6 + 7;
    char *p1, *p2, buf[S];
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, S, stdin), p1 == p2) ? EOF : *p1++)
    template <typename _T>
    inline void read(_T &x)
    {
        x = 0;
        char c = gc();
        while (c < '0' || c > '9')
            c = gc();
        for (; c >= '0' && c <= '9'; c = gc())
            x = (x << 3) + (x << 1) + (c & 15);
    }
    #undef gc
}
using FastIn::read;
const int MAXN = 2e5 + 7;
int n, m, c, ans;
long long a[MAXN];
namespace FS
{
    unsigned long long b[3][MAXN];
    inline void update(int x, const bool &val)
    {
        if (val)
            b[0][x >> 6] |= 1ull << (x & 63), x >>= 6,
            b[1][x >> 6] |= 1ull << (x & 63), x >>= 6,
            b[2][x >> 6] |= 1ull << (x & 63);
        else
        {
            b[0][x >> 6] &= ~(1ull << (x & 63));
            if (b[0][x >> 6])
                return;
            x >>= 6, b[1][x >> 6] &= ~(1ull << (x & 63));
            if (b[1][x >> 6])
                return;
            x >>= 6, b[2][x >> 6] &= ~(1ull << (x & 63));
        }
    }
    inline int findprev(int x)
    {
        int i = x >> 6;
        unsigned long long t = (b[0][i] << (63 - (x & 63))) >> (63 - (x & 63));
        if (t)
            return (i << 6) + 63 - __builtin_clzll(t);
        x = i - 1, i = x >> 6, t = (b[1][i] << (63 - (x & 63))) >> (63 - (x & 63));
        if (!t)
            x = i - 1, i = x >> 6, t = (b[2][i] << (63 - (x & 63))) >> (63 - (x & 63)),
            i = (i << 6) + 63 - __builtin_clzll(t), t = b[1][i];
        i = (i << 6) + 63 - __builtin_clzll(t), t = b[0][i];
        return (i << 6) + 63 - __builtin_clzll(t);
    }
    inline int findnext(int x)
    {
        int i = x >> 6;
        unsigned long long t = (b[0][i] >> (x & 63)) << (x & 63);
        if (t)
            return (i << 6) + __builtin_ctzll(t);
        x = i + 1, i = x >> 6, t = (b[1][i] >> (x & 63)) << (x & 63);
        if (!t)
            x = i + 1, i = x >> 6, t = (b[2][i] >> (x & 63)) << (x & 63),
            i = (i << 6) + __builtin_ctzll(t), t = b[1][i];
        i = (i << 6) + __builtin_ctzll(t), t = b[0][i];
        return (i << 6) + __builtin_ctzll(t);
    }
}
int main()
{
    read(n), read(m), read(c);
    long long premax = 0;
    for (int i = 1; i <= n; ++i)
        read(a[i]), a[i] >= premax && (FS::update(i, true), premax = a[i], ++ans);
    FS::update(0, true), FS::update(n + 1, true), a[n + 1] = 0x3f3f3f3f3f3f3f3fll;
    for (int t = 1, p, x, lst = 0; t <= m; ++t)
    {
        read(p), read(x), p ^= (c * lst) % 3, a[p] += x;
        if (a[p] < a[FS::findprev(p)])
        {
            printf("%d\n", lst = ans);
            continue;
        }
        if (FS::findnext(p) != p)
            FS::update(p, true), ++ans;
        long long ap = a[p];
        while (ap > a[FS::findnext(p + 1)])
            p = FS::findnext(p + 1), FS::update(p, false), --ans;
        printf("%d\n", lst = ans);
    }
    return 0;
}