Codeforces 1140F Extending Set of Points (线段树分治+并查集)

这题有以下几个步骤

1.离线处理出每个点的作用范围

2.根据线段树得出作用范围

3.根据分治把每个范围内的点记录和处理

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 3e5 + 50;

typedef pair<int, int> pii;

#define bug cout << "bug" << endl;

vector<pii> rt[maxn << 2];

void update(int o,int l,int r,int ql,int qr,pii pi){

    //cout << "o=" << o <<" l="<<l<<" r="<<r<<" ql="<<ql<<" qr="<<qr<<endl;

    if(ql<=l&&qr>=r){

        rt[o].push_back(pi);

        return;

    }

    int mid = (l + r)/2;

    if(ql<=mid)

        update(o << 1, l, mid, ql, qr, pi);

    if(qr>mid)

        update(o << 1 | 1, mid + 1, r, ql, qr, pi);

}

int fa[maxn << 1];

ll sz[maxn << 1], szx[maxn << 1], szy[maxn << 1];

int find(int x){

    if(fa[x]==x)

        return x;

    return find(fa[x]);

}

ll value;

ll ans[maxn];

void ins(int x,int y,stack<pii> &st){

    int xx = find(x);

    int yy = find(y);

    if(xx==yy)

        return;

    if(sz[xx]<sz[yy])

        swap(xx, yy);

    st.push({xx, yy});

    value -= 1LL*szx[yy] * szy[yy];

    value -= 1LL*szx[xx] * szy[xx];

    sz[xx] += 1LL*sz[yy];

    szx[xx] += 1LL*szx[yy];

    szy[xx] += 1LL*szy[yy];

    value += 1LL*szx[xx] * szy[xx];

    fa[yy] = fa[xx];

}

void del(stack<pii> &st){

    while(!st.empty()){

        int x = st.top().first;

        int y = st.top().second;

        st.pop();

        value -= 1LL*szx[x] * szy[x];

        sz[x] -= 1LL*sz[y];

        szx[x] -= 1LL*szx[y];

        szy[x] -= 1LL*szy[y];

        fa[y] = y;

        value += 1LL*szx[x] * szy[x];

        value += 1LL*szx[y] * szy[y];

    }

}

void dfs(int o,int l,int r){

    //cout << "o=" << o << " l=" << l << " r=" << r << endl;

    stack<pii> st;

    for(auto i:rt[o]){

        int x = i.first;

        int y = i.second;

        ins(x, y, st);

    }

    if(l==r)

        ans[l] = value;

    else{

        int mid = (l + r) / 2;

        dfs(o << 1, l, mid);

        dfs(o << 1 | 1, mid + 1, r);

    }

    del(st);

}

map<pii, int> mp;

int main(){

    int q;

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    cin >> q;

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

        int x, y;

        cin >> x >> y;

        y += 3e5;

        pii pi = make_pair(x, y);

        if(mp.find(pi)==mp.end()){

            mp[pi] = i;

        }

        else{

            update(1, 1, q, mp[pi], i - 1, pi);

            mp.erase(pi);

        }

    }

    for(auto i:mp){

        update(1, 1, q, i.second, q, i.first);

    }

    for (int i = 1; i <= 3e5;i++){

        fa[i] = i;

        sz[i] = 1;

        szx[i] = 1;

    }

    for (int i = 3e5 + 1; i <= 6e5;i++){

        fa[i] = i;

        szy[i] = 1;

        sz[i] = 1;

    }

    dfs(1, 1, q);

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

        cout << ans[i] << " ";

    }

        return 0;

}

巴特西

Codeforces 1140F Extending Set of Points (线段树分治+并查集)

最新文章

热门文章