「APIO 2019」路灯

题目

显然一个熟练的选手应该能一眼看出我们需要维护点对的答案

显然在断开或连上某一条边的时候只会对左右两边联通的点产生贡献，这个拿\(set\)维护一下就好了

那现在的问题就是怎么维护了

考虑一个非常\(sb\)的问题，我们只想知道一个点对\((x,y)\)从开始到某个时间\(t\)有多少个时间是联通的

如果\(i\)时刻\((x,y)\)突然联通了，那么我们就把答案加上\(t-i+1\)，如果\(i\)时刻\((x,y)\)突然断开了，我们就把答案减去\(t-i+1\)，正确性显然

于是我们只需要分别维护那些常数和加上了多少个当前时间就可以回答任意时刻的询问了

所以问题变成了矩阵加单点查，显然可以差分之后变成一个三维偏序问题，可以直接大力\(cdq\)，当然也可以直接上树套树

代码

#include <bits/stdc++.h>

#define L first

#define R second

#define re register

#define LL long long

#define lb(x) ((x) & (-x))

#define mp std::make_pair

#define set_it std::set<pii>::iterator

inline int read() {

    char c = getchar();

    int x = 0;

    while (c < '0' || c > '9') c = getchar();

    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - 48, c = getchar();

    return x;

}

typedef std::pair<int, int> pii;

const int maxn = 3e5 + 5;

const int M = maxn * 200;

std::set<pii> s;

int n, m, B, cnt;

char S[maxn], op[12];

int rt[maxn << 2];

LL g[M], A;

int h[M], l[M], r[M];

int ins(int now, int x, int y, int pos, int v, int w) {

    if (!now)

        now = ++cnt;

    if (x == y) {

        g[now] += v, h[now] += w;

        return now;

    }

    int mid = x + y >> 1;

    if (pos <= mid)

        l[now] = ins(l[now], x, mid, pos, v, w);

    else

        r[now] = ins(r[now], mid + 1, y, pos, v, w);

    g[now] = g[l[now]] + g[r[now]];

    h[now] = h[l[now]] + h[r[now]];

    return now;

}

void find(int now, int x, int y, int pos) {

    if (!now)

        return;

    if (x == y) {

        A += g[now];

        B += h[now];

        return;

    }

    int mid = x + y >> 1;

    if (pos <= mid)

        find(l[now], x, mid, pos);

    else

        find(r[now], mid + 1, y, pos), A += g[l[now]], B += h[l[now]];

}

void change(int x, int y, int a, int b) {

    if (y > n)

        return;

    for (re int i = x; i <= n; i += lb(i)) rt[i] = ins(rt[i], 1, n, y, a, b);

}

void query(int x, int y) {

    for (re int i = x; i; i -= lb(i)) find(rt[i], 1, n, y);

}

inline pii ask(int pos) {

    s.insert(mp(pos, n + 1));

    set_it it = s.find(mp(pos, n + 1));

    --it;

    s.erase(mp(pos, n + 1));

    return *it;

}

inline void add(int x, int y, int lx, int ry, int t, int v) {

    change(x, lx, v * (1 - t), v);

    change(x, ry + 1, v * (t - 1), -1 * v);

    change(y + 1, lx, v * (t - 1), -1 * v);

    change(y + 1, ry + 1, v * (1 - t), v);

}

inline void getAns(int t) {

    int x = read(), y = read();

    if (x > y)

        std::swap(x, y);

    A = 0, B = 0;

    query(x, y);

    printf("%d\n", A + B * t);

}

int main() {

    n = read() + 1, m = read();

    scanf("%s", S + 1);

    for (re int i = 1; i < n; i++) S[i] -= '0';

    int t = 1;

    for (re int i = 1; i <= n; i++)

        if (!S[i])

            s.insert(mp(t, i)), t = i + 1;

    for (set_it it = s.begin(); it != s.end(); ++it) add((*it).L, (*it).R, (*it).L, (*it).R, 0, 1);

    for (re int i = 1; i <= m; i++) {

        scanf("%s", op);

        if (op[0] == 'q')

            getAns(i - 1);

        if (op[0] == 't') {

            int x = read();

            pii ll = ask(x), rr = ask(x + 1);

            if (!S[x]) {

                add(ll.L, ll.R, rr.L, rr.R, i, 1);

                s.erase(ll), s.erase(rr);

                s.insert(mp(ll.L, rr.R));

            } else {

                add(ll.L, x, x + 1, rr.R, i, -1);

                s.erase(ll);

                s.insert(mp(ll.L, x));

                s.insert(mp(x + 1, rr.R));

            }

            S[x] ^= 1;

        }

    }

    return 0;

}

巴特西

「APIO 2019」路灯

最新文章

热门文章