P7707 「Wdsr-2.7」百花齐放的太阳花田 题解

· · 题解

官方题解的卡空间方式是人？

发现 \text{Sub 3} 只会问一个前缀，先想想这个怎么做。

修改只会在尾部加数，非常契合“前缀”这个事情。加数时，对于当前前缀，加的这个数只会影响 x\geqslant h 的询问。

那么我们可以对每个前缀开一颗线段树维护每个 x 对应的答案，用珂朵莉维护每个 x 对应的结尾元素，此时需要 +1 的区间即为所有结尾元素与新加的 t 不同的 x。

回看整个题，尝试将询问区间变为两个前缀相减。但是这样可能会多减一个跨过 l-1,l 间空隙的断点，再用一颗线段树二分求一下 l 前 / 后第一个 h\leqslant x 的位置即可。

总时间复杂度 O(n'\log V)，空间复杂度 O(n'\log V)，会被卡空间。

然后有神秘优化：因为是可持久化线段树，区间加 / 单点查带 tag，空间不如单点加 / 区间查；更新前缀的答案时会存在大量的区间首尾相连，可以合成一个。

::::success[Code]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace IO {
    constexpr int bufsize = 230005;
    char buf[bufsize], *f1, *f2;
    char gtchar() {return f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++;}
    template<typename T> void read(T &ret)
    {
        int f = ret = 0;
        char ch = gtchar();
        while(!isdigit(ch)) f = ch == '-', ch = gtchar();
        while(isdigit(ch)) ret = (ret << 3) + (ret << 1) + (ch ^ 48), ch = gtchar();
        if(f) ret = -ret;
    }
    template<typename T, typename ...t> void read(T &a, t &...b) {read(a), read(b...);}
}using IO::read;
template<typename t, typename T = t> void chmax(t &a, const T &b) {if(a < b) a = b;}
template<typename t, typename T = t> void chmin(t &a, const T &b) {if(a > b) a = b;}
constexpr int maxn = 5e5 + 5, V = 1e9;
int n, m, K, lstans, h[maxn], t[maxn];
struct seg {
    int mn[maxn << 2];
    void pushup(int k) {mn[k] = min(mn[k << 1], mn[k << 1 | 1]);}
    void modify(int k, int sl, int sr, int q, int val)
    {
        if(sl == sr) return void(mn[k] = val);
        int mid = sl + sr >> 1;
        q <= mid? modify(k << 1, sl, mid, q, val)
        : modify(k << 1 | 1, mid + 1, sr, q, val);
        pushup(k);
    }
    int queryfir(int k, int sl, int sr, int ql, int qr, int val)// 1st <=val
    {
        if(mn[k] > val) return -1;
        if(sl == sr) return sl;
        int mid = sl + sr >> 1;
        if(ql <= mid)
        {
            int t = queryfir(k << 1, sl, mid, ql, qr, val);
            if(~t) return t;
        }
        if(qr > mid) return queryfir(k << 1 | 1, mid + 1, sr, ql, qr, val);
        return -1;
    }
    int querylst(int k, int sl, int sr, int ql, int qr, int val)// 1st <=val
    {
        if(mn[k] > val) return -1;
        if(sl == sr) return sl;
        int mid = sl + sr >> 1;
        if(qr > mid)
        {
            int t = querylst(k << 1 | 1, mid + 1, sr, ql, qr, val);
            if(~t) return t;
        }
        if(ql <= mid) return querylst(k << 1, sl, mid, ql, qr, val);
        return -1;
    }
}Th;
struct preseg {
    struct node {
        int l, r, v;
    }s[maxn * 50];//!
    int cnt;
    #define l(k) s[k].l
    #define r(k) s[k].r
    #define v(k) s[k].v
    void modify(int &nk, int k, int sl, int sr, int q, int delta)
    {
        if(nk == k) s[nk = ++cnt] = s[k];
        v(nk) += delta;
        if(sl == sr) return;
        int mid = sl + sr >> 1;
        q <= mid? modify(l(nk), l(k), sl, mid, q, delta)
            : modify(r(nk), r(k), mid + 1, sr, q, delta);
    }
    int query(int k, int sl, int sr, int ql, int qr)
    {
        if(!k || ql <= sl && sr <= qr) return v(k);
        int mid = sl + sr >> 1, ret = 0;
        if(ql <= mid) ret = query(l(k), sl, mid, ql, qr);
        if(qr > mid) ret += query(r(k), mid + 1, sr, ql, qr);
        return ret;
    }
    #undef l
    #undef r
    #undef v
}Tans;
int rt[maxn];
struct Chtholly {
    struct node {
        int l, r, v;
        friend bool operator < (node a, node b) {return a.l < b.l;}
    };
    int lim;
    set<node> S;
    void init(int LIM) {S.insert({1, lim = LIM, -1});}
    auto split(int x)//[x,...)
    {
        if(x > lim) return S.end();
        auto it = prev(S.upper_bound({x, lim + 1, -1}));
        if(it->l == x) return it;
        int l = it->l, r = it->r, v = it->v;
        S.erase(it); S.insert({l, x - 1, v});
        return S.insert({x, r, v}).first;
    }
    void append(int k, int val, int kind)
    {
        rt[k] = rt[k - 1];
        auto itl = split(val);
        vector<int> vec;
        for(auto it = itl; it != S.end(); ++it) if(it->v != kind)
        {
            if(vec.size() && vec.back() == it->l) vec.pop_back();
            else vec.push_back(it->l);
            vec.push_back(it->r + 1);
        }
        for(int i = 0, j = 1; i < vec.size(); i++, j = -j)
            if(vec[i] <= V) Tans.modify(rt[k], rt[k - 1], 1, V, vec[i], j);
        S.erase(itl, S.end());
        S.insert({val, lim, kind});
    }
}Tlst;
void append(int nh, int nt)
{
    ++n, h[n] = nh, t[n] = nt;
    Tlst.append(n, nh, nt);
    Th.modify(1, 1, maxn - 5, n, nh);
}
int query(int r, int x) {return Tans.query(rt[r], 1, V, 1, x);}
int query(int l, int r, int x)
{
    // printf("r:%d\n", query(r, x));
    if(l == 1) return query(r, x);
    int ans = query(r, x) - query(l - 1, x);
    int lst = Th.querylst(1, 1, maxn - 5, 1, l - 1, x), fir = Th.queryfir(1, 1, maxn - 5, l, r, x);
    if(lst != -1 && fir != -1 && t[lst] == t[fir]) ++ans;
    return ans;
}
int main()
{
    Tlst.init(V);
    read(n, m, K);
    for(int i = 1; i <= n; i++) read(h[i]);
    for(int i = 1; i <= n; i++) read(t[i]);
    int nn = n; n = 0;
    for(int i = 1; i <= nn; i++) append(h[i], t[i]);
    assert(nn == n);
    for(int i = 1, op, l, r, x; i <= m; i++)
    {
        read(op, l, r);
        l ^= K * lstans, r ^= K * lstans;
        if(op == 1)// qry
        {
            read(x), x ^= K * lstans;
            printf("%d\n", lstans = query(l, r, x));
        }
        else append(l, r);
    }
    return 0;
}

::::