(为了督促自己补题,打算以后只写补题)

1004

cdq + trie树(场上没写亏了
首先,我们把所有操作离线。对于一个询问我们可以拆分成两个询问然后前缀作差就可以。如果没有不同权值的话,我们只需要用字典树统计在这段区间内有多少个就行,多加了一个不同权值,其实就是再加了一维限制,就是当前权值下次出现的位置大于当前区间左边界才OK,所以再加一维做cdq分治 + trie统计答案即可

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include <bits/stdc++.h>

using namespace std;

#define ll long long

constexpr int N = 1e5 + 100;

struct node {
    int type;
    int x, nxt;
    int tim;
    int a, b, id;
}s[N * 3], tmp[N * 3];

int pre[N], ans[N];

bool cmp(const node &a, const node &b) {
    if (a.nxt == b.nxt) return a.type < b.type;
    return a.nxt > b.nxt;
}

constexpr int M = 3e6 + 7;
int val[M][2], cnt[M];
int idx = 0;

void cdq(int l, int r) {
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);

    merge(s + l, s + mid + 1, s + mid + 1, s + r + 1, tmp + l, cmp);

    for (int i = l; i <= r; ++i) s[i] = tmp[i];

    for (int i = l; i <= r; ++i) {
        if (s[i].tim <= mid and s[i].type == 1) {
            int now = 0;
            for (int j = 29; j >= 0; --j) {
                int w = (s[i].a >> j) & 1;
                if (not val[now][w]) {
                    val[now][w] = ++idx;
                    val[idx][0] = val[idx][1] = 0;
                    cnt[idx] = 1;
                } else ++cnt[val[now][w]];
                now = val[now][w];
            }
        }

        if (s[i].tim > mid and s[i].type > 1) {
            int num = 0, a = s[i].a, b = s[i].b, root = 0;
            for (int j = 29; j >= 0; --j) {
                int w = (a >> j) & 1;
                if ((b >> j) & 1) {
                    num += cnt[val[root][w]];
                    root = val[root][w ^ 1];
                } else {
                    root = val[root][w];
                }
                if (not root) break;
            }
            if (root) num += cnt[root];

            if (s[i].type == 2) {
                ans[s[i].id] -= num;
            } else {
                ans[s[i].id] += num;
            }
        }
    }
    idx = 0;
    cnt[0] = 0;
    val[0][0] = val[0][1] = 0;
}
int main() {
    ios::sync_with_stdio(false);

    int n; cin >> n;
    int tot = 0;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        s[++tot] = {1, i, n + 1, i, x};
        if (pre[x]) s[pre[x]].nxt = i;
        pre[x] = i;
    }

    int m; cin >> m;
    for (int i = 1; i <= m; ++i) {
        int l, r, a, b; cin >> l >> r >> a >> b;
        ++tot; s[tot] = {2, l - 1, r + 1, tot, a, b, i};
        ++tot; s[tot] = {3, r, r + 1, tot, a, b, i};
    }

    sort(s + 1, s + 1 + tot, [](const node &a, const node &b) {
        if (a.x == b.x and a.nxt == b.nxt) return a.type < b.type;
        if (a.x == b.x) return a.nxt > b.nxt;
        return a.x < b.x;
    });

    for (int i = 1; i <= tot; ++i) {
        s[i].tim = i;
    }

    cdq(1, tot);

    for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';
}

1002

把加这个操作与当前位置的下标关联起来。比如说给4到6进行加平方的操作,那么我们变成给每个位置加,然后展开维护即可

#pragma GCC optimize(2)
#pragma GCC optimize(3)

#include <bits/stdc++.h>

using namespace std;

template<typename T>
inline T read() {
    T s = 0, f = 1; int ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) {s = (s << 3) + (s << 1) + ch - 48; ch = getchar();}
    return s * f;
}
#define gn() read<int>()

#define ll long long

constexpr int N = 1e5 + 100;

vector<int> v[N];

int dep[N], f[N], siz[N], son[N], top[N];
int id[N], tot = 0;

void predfs(int node, int fa) {
    dep[node] = dep[fa] + 1;
    siz[node] = 1;
    f[node] = fa;
    int maxn = 0;
    for (auto to : v[node]) {
        if (to == fa) continue;
        predfs(to, node); siz[node] += siz[to];
        if (siz[to] > maxn) {
            maxn = siz[to]; son[node] = to;
        }
    }
}

void dfs(int node, int topx) {
    top[node] = topx; id [node] = ++tot;
    if (son[node]) dfs(son[node], topx);
    for (auto to : v[node]) {
        if (to == f[node] or to == son[node]) continue;
        dfs(to, to);
    }
}

int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] >= dep[top[y]]) x = f[top[x]];
        else y = f[top[y]];
    }
    return dep[x] < dep[y] ? x : y;
}

int dis(int x, int y) {
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}

struct SegmentTree {
#define lson node << 1
#define rson node << 1 | 1
    array<ll, 3> val[N << 2];
    // (x + i) ^ 2,  x * x + 2 * x * i + i * i;

    void spread(int node) {
        if (val[node][0] or val[node][1] or val[node][2]) {
            val[lson][0] += val[node][0];
            val[rson][0] += val[node][0];

            val[lson][1] += val[node][1];
            val[rson][1] += val[node][1];

            val[lson][2] += val[node][2];
            val[rson][2] += val[node][2];

            val[node][0] = val[node][1] = val[node][2] = 0;
        }
    }

    void build(int node, int l, int r) {
        val[node][0] = val[node][1] = val[node][2] = 0ll;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
    }

    void change(int node, int l, int r, int L, int R, int num) {
        if (L <= l and R >= r) {
            // pre ~ pre + (r - l)
            val[node][0] += 1ll * num * num;
            val[node][1] += 2ll * num;
            val[node][2] ++;
            return;
        }
        int mid = (l + r) >> 1;
        spread(node);
        if (L <= mid) change(lson, l, mid, L, R, num);
        if (R > mid) change(rson, mid + 1, r, L, R, num);
    }

    ll query(int node, int l, int r, int idx) {
        if (l == r) {
            return 1ll * val[node][0] + 1ll * val[node][1] * idx + 1ll * val[node][2] * idx * idx;
        }
        int mid = (l + r) >> 1;
        spread(node);
        if (idx <= mid) return query(lson, l, mid, idx);
        else return query(rson, mid + 1, r, idx);
    }
} tree;

int main() {
    int n = gn();
    for (int i = 1; i < n; ++i) {
        int x = gn(), y =gn();
        v[y].emplace_back(x);
        v[x].emplace_back(y);
    }

    predfs(1, 0);
    dfs(1, 1);

    tree.build(1, 1, n);

    int q = gn();
    for (int i = 1; i <= q; ++i) {
        int type = gn();

        if (type == 1) {
            int x = gn(), y = gn();
            int idpre = 1, idlast = dis(x, y) + 1;
//            cout << idpre << ' ' << idlast << '\n';
            while(top[x] != top[y]) {
                if(dep[top[x]] >= dep[top[y]]) {
                    idpre += dis(x, top[x]);
                    // x + id[top[x]] = - idpre
                    tree.change(1, 1, n, id[top[x]], id[x],  - idpre - id[top[x]]);
                    x = f[top[x]];
                    ++ idpre;
                } else {
                    idlast -= dis(y, top[y]);
                    tree.change(1, 1, n, id[top[y]], id[y], idlast - id[top[y]]);
                    y = f[top[y]];
                    -- idlast;
                }
            }

            if (id[x] <= id[y]) {
                // x + id[x] = idpre
                tree.change(1, 1, n, id[x], id[y], idpre - id[x]);
            } else {
                //
                tree.change(1, 1, n, id[y], id[x], - idlast - id[y]);
            }

        } else {
            int x = gn();
            cout << tree.query(1, 1, n, id[x]) << '\n';
        }
    }
}