CF1824D LuoTianyi and the Function 题解

· · 题解

将询问差分，转成前缀和。

考虑扫描线维护，将右端点置为 1，它的 lst 设为 0，则 g(i,r) 为 i 之后第一个 1，于是区间覆盖区间查询即可。

维护下一个 1 与当前 i 的差值，问题转化为区间加区间查询。

原问题答案即为，前缀版本历史和，套一棵区间价历史区间和线段树即可。

时间复杂度 \mathcal O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
#define F(i, a, b) for(int i = a; i <= (b); ++i)
#define F2(i, a, b) for(int i = a; i < (b); ++i)
#define dF(i, a, b) for(int i = a; i >= (b); --i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug debug("Passing [%s] in LINS %d\n", __FUNCTION__, __LINE__)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
//namespace Fread {const int SIZE = 1 << 17; char buf[SIZE], *S, *T; inline char getchar() {if (S == T) {T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n';} return *S++;}}
//namespace Fwrite {const int SIZE = 1 << 17; char buf[SIZE], *S = buf, *T = buf + SIZE; inline void flush() {fwrite(buf, 1, S - buf, stdout), S = buf;} inline void putchar(char c) {*S++ = c;if (S == T) flush();} struct NTR {~NTR() {flush();}} ztr;}
//#ifdef ONLINE_JUDGE
//#define getchar Fread::getchar
//#define putchar Fwrite::putchar
//#endif
inline int ri() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return x * f;
}
inline void wi(int x) {
    if (x < 0) {
        putchar('-'), x = -x;
    }
    if (x > 9) wi(x / 10);
    putchar(x % 10 + 48);
}
inline void wi(int x, char s) {
    wi(x), putchar(s);
}
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;
const int _ = 1e6 + 5;
int n, q;
struct node {
    int len, u, tg, mtg, s, ms;
    void add(int _tg, int _mtg, int _u) {
        ms += _u * s + _mtg * len;
        mtg += _u * tg + _mtg;
        tg += _tg;
        s += _tg * len;
        u += _u;
    }
} tr[_ << 2];
void up(int o) {
    tr[o].s = tr[o << 1].s + tr[o << 1 | 1].s;
}
void build(int o, int l, int r) {
    tr[o].len = r - l + 1;
    if (l == r) return void();
    int mid = (l + r) >> 1;
    build(o << 1, l, mid), build(o << 1 | 1, mid + 1, r);
    up(o);
}
void pd(int o) {
    if(tr[o].tg || tr[o].mtg || tr[o].u) {
        tr[o << 1].add(tr[o].tg, tr[o].mtg, tr[o].u);
        tr[o << 1 | 1].add(tr[o].tg, tr[o].mtg, tr[o].u);
        tr[o].tg = tr[o].mtg = tr[o].u = 0;
    }
}
void add(int o, int l, int r, int L, int R, int c) {
    if (L <= l && r <= R) return tr[o].add(c, 0, 0), void();
    int mid = (l + r) >> 1;
    pd(o);
    if (L <= mid) add(o << 1, l, mid, L, R, c);
    if (R > mid) add(o << 1 | 1, mid + 1, r, L, R, c);
    up(o);
}
int qry(int o, int l, int r, int L, int R) {
    if (L <= l && r <= R) return tr[o].ms;
    int mid = (l + r) >> 1, res = 0;
    pd(o);
    if (L <= mid) res = qry(o << 1, l, mid, L, R);
    if (R > mid) res += qry(o << 1 | 1, mid + 1, r, L, R);
    return res;
}
int lst[_], t[_], l[_], r[_], ans[_];
vector<pair<pair<int, int>, int>> qy[_];
signed main() {
    n = ri(), q = ri();
    int x;
    F(i, 1, n) x = ri(), lst[i] = t[x], t[x] = i;
    int y;
    F(i, 1, q) {
        int l, r;
        x = ri(), y = ri(), l = ri(), r = ri();
        qy[r].pb(make_pair(make_pair(x, y), i));
        qy[l - 1].pb(make_pair(make_pair(x, y), -i));
    }
    build(1, 1, n);
    F(i, 1, n) {
        x = lst[i], l[i] = i - 1, r[i] = i + 1;
        // delete lst[i]
        if(x) {
            // [l[x] + 1, x] += r[x] - x
            add(1, 1, n, l[x] + 1, x, r[x] - x);
            l[r[x]] = l[x], r[l[x]] = r[x];
        }
        // add i
        add(1, 1, n, i, i, i);
        tr[1].add(0, 0, 1);
        for(auto v : qy[i]) {
            int k = 1;
            if(v.se < 0) v.se = -v.se, k = -1;
            // calculate [x, y] [1, i]
            ans[v.se] += k * qry(1, 1, n, v.fi.fi, v.fi.se);
        }
    }
    F(i, 1, q) printf("%lld\n", ans[i]);
    return 0;
}