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

news/2024/7/24 11:25:39

这题有以下几个步骤
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;
}

转载于:https://www.cnblogs.com/luowentao/p/10815744.html


http://www.niftyadmin.cn/n/1169963.html

相关文章

poj 2135 (基础费用流)

题意&#xff1a;从1到n再到1&#xff0c;每条边只能走一次&#xff0c;求最短距离。 建图&#xff1a;每条边只能走一次就是流量是1&#xff0c;添加源点与1相连&#xff0c;容量为2,费用为0&#xff0c;n与汇点相连容量为2,费用为0&#xff1b; 求增广路用SPFA最短路求&#…

C#实现水晶报表绑定数据并实现打印4-条形码

看了上几篇文章 加上自己的调试可以打出来了 大概记录下流程 1、在dataset中加入列code 类型System.Byte[] &#xff0c;并将此列拉至水晶报表某位置 2、安装BarcodeX并添加 barcodex.ocx 引用 3、新建 from 并拉一个 barcode过来 4、获取数据并赋值 barcodex.Caption “12345…

[USACO2004] Open提交作业(区间DP)

Description 贝西在哞哞大学选修了C门课&#xff0c;她要把这些课的作业交给老师&#xff0c;然后去车站和同学们一 起回家。老师们在办公室里&#xff0c;办公室要等他们下课后才开&#xff0c;第i门课的办公室在Ti时刻后开放。 所有的办公室都在一条走廊上&#xff0c;这条走…

JS中的BOM与DOM

BOM&#xff08;Broswer Object Model&#xff09; 定时器: 执行一次的定时器 var taskidwindow.setTimeout(function,ms); 关闭:window.clearTimeout(taskid); 执行无数次的定时器 var taskidwindow.setInteval(function,ms); 关闭:window.clearInteval(function,ms); 框窗…

map标签的详细使用参数

map标签必须成对出现&#xff0c;即 <map> ....</map> 同时map必须和area配合使用。 img标签里的usermap属性值必须与map标签里的id和name值完全一致 area标签&#xff1a;定义图片的点击区域 area 是单标签&#xff0c;不成对。 属性&#xff1a; accesskey 快捷键…

BarcodeX(ActiveX打印控件) v5.3.0.80 免费版使用

下载 地址 &#xff1a;https://www.xiazaila.com/soft/39537.html 转载&#xff1a;https://www.xiazaila.com/soft/39537.html BarcodeX是一款active打印控件&#xff0c;软件可以识别所有类型的条形码&#xff0c;识别之后就可以导出为位图、元文件和到剪贴板等&#xff0c…

IIS发布网站、发布webservice的重要说明

本文主要讲IIS发布网站、发布webservice的重要步骤、注意事项。 一、IIS发布网站、发布webservice 1.打开IIS管理器&#xff0c;如下图 2.在【网站】上点击右键&#xff0c;添加网站&#xff0c;设置如下图&#xff1a; 如果需要使用域名访问网站&#xff0c;则必须先购买域名并…

比较两个UNIX文本文件,找出新增内容(diff和comm命令)(转)

欢迎来到小码哥的博客博客搬家啦 blog.ma6174.com比较两个UNIX文本文件&#xff0c;找出新增内容&#xff08;diff和comm命令&#xff09;(转) 本文转自 http://blog.xuyuan.me/2011/03/17/unix_diff.html 最近项目中遇到一个奇怪的bug&#xff0c;仔细检查后发现是由一行简单代…