CF1614E Divan and a Cottage

题目大意

给定 $n$ 天的气温 $T_i$，设第 $i$ 天温度为 $P$，则第 $i+1$ 天的温度为：

• $P+1(P<T_i)$

• $P-1(P>T_i)$

• $P(P=T_i)$

对第 $i$ 天有 $k_i$ 个询问，问若第 $0$ 天的温度为 $x$ ，那么第 $i$ 天的温度是多少。

强制在线。

解题思路

显然，所有初始的室温变化后的结果满足单调。

那用一棵动态开点值域线段树维护所有初始的室温变化后的结果即可。

具体地，每次插入一个气温 $T_i$ 后，在线段树上二分以得到变化后的室温为 $T_i$ 的区间 $\left[l,r\right]$，之后 $[-1,l)$ 区间 $+1$，$\left(r,MaxT+1\right]$ 区间 $-1$ 即可。

时间复杂度 $\mathcal{O}(n\log w)$，其中 $w$ 为值域。

CODE

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

inline ll read()
{
    ll x = 0, f = 1;
    char c = getchar();
    while ((c < '0' || c > '9') && (c != '-'))
        c = getchar();
    if (c == '-')
        f = -1, c = getchar();
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x * f;
}

const int N = 2e5 + 10, mod = 1e9 + 1;

int n, m;

const int M = 4e7 + 10;

int tot, mn[M], mx[M], tag[M], ls[M], rs[M];

inline int New(int l, int r)
{
    ++tot, mn[tot] = l, mx[tot] = r;
    return tot;
}

inline void upd(int u, int x)
{
    mn[u] += x, mx[u] += x, tag[u] += x;
}

inline void push_down(int u, int l, int r, int mid)
{
    if (!tag[u])
        return;
    if (!ls[u])
        ls[u] = New(l, mid);
    if (!rs[u])
        rs[u] = New(mid + 1, r);
    upd(ls[u], tag[u]), upd(rs[u], tag[u]);
    tag[u] = 0;
}

inline void update(int &u, int l, int r, int ql, int qr, int x)
{
    if (ql > qr)
        return;
    if (!u)
        u = New(l, r);
    if (l >= ql && r <= qr)
    {
        upd(u, x);
        return;
    }
    int mid = l + r >> 1;
    push_down(u, l, r, mid);
    if (ql <= mid)
        update(ls[u], l, mid, ql, qr, x);
    if (qr > mid)
        update(rs[u], mid + 1, r, ql, qr, x);
    mn[u] = min(!ls[u] ? l : mn[ls[u]], !rs[u] ? mid + 1 : mn[rs[u]]);
    mx[u] = max(!ls[u] ? mid : mx[ls[u]], !rs[u] ? r : mx[rs[u]]);
}

inline int Findl(int u, int l, int r, int x)
{
    if ((!u ? l : mn[u]) >= x)
        return -1;
    if (l == r)
        return l;
    int mid = l + r >> 1;
    push_down(u, l, r, mid);
    int ret = Findl(rs[u], mid + 1, r, x);
    if (ret != -1)
        return ret;
    return Findl(ls[u], l, mid, x);
}

inline int Findr(int u, int l, int r, int x)
{
    if ((!u ? r : mx[u]) <= x)
        return mod;
    if (l == r)
        return l;
    int mid = l + r >> 1;
    push_down(u, l, r, mid);
    int ret = Findr(ls[u], l, mid, x);
    if (ret != mod)
        return ret;
    return Findr(rs[u], mid + 1, r, x);
}

inline int Query(int u, int l, int r, int ql)
{
    if (l == r)
        return !u ? l : mn[u];
    int mid = l + r >> 1;
    push_down(u, l, r, mid);
    if (ql <= mid)
        return Query(ls[u], l, mid, ql);
    return Query(rs[u], mid + 1, r, ql);
}

signed main()
{
    n = read();
    ll lasans = 0;
    int rt = 0;
    for(int i = 1; i <= n; ++i)
    {
        int x = read();
        int l = Findl(rt, 0, 1e9, x), r = Findr(rt, 0, 1e9, x);
        update(rt, 0, 1e9, 0, l, +1);
        update(rt, 0, 1e9, r, 1e9, -1);
        m = read();
        for(int j = 1; j <= m; ++j)
        {
            int x = (read() + lasans) % mod;
            printf("%lld\n", lasans = Query(rt, 0, 1e9, x));
        }
    }
}