【CSA72G】【XSY3316】rectangle 线段树 最小生成树
2024-09-24 20:41:27
题目大意
有一个 \(n\times n\) 的矩阵 \(A\)。最开始 \(A\) 中每个元素的值都为 \(0\)。
有 \(m\) 次操作，每次给你 \(x_1,x_2,y_1,y_2,w\)，对于满足 \(x_1\leq i\leq x_2,y_1\leq j\leq y_2\) 的数对 \((i,j)\)，把 \(A_{i,j}\) 的值增加 \(w\)。
最后构造一个 \(n\) 个点的无向图 \(G\)。对于满足 \(1\leq i<j\leq n\) 的数对 \((i,j)\)，在 \(G\) 中加一条连接着 \(i,j\)，边权为 \(A_{i,j}\) 的边。
求 \(G\) 的最小生成树的边权和。
\(1\leq n,m\leq 100000,1\leq x_1\leq x_2<y_1\leq y_2\leq n,-{10}^6\leq w\leq {10}^6\)；
题解
似乎 prim 和 kruskal 算法都不太好做这道题。
还有个算法叫 boruvka。
大概就是每一轮对于每个连通块求出这个连通块与其他连通块间边权最小的边，然后把这两个连通块缩在一起。
总共会缩 \(O(\log n)\) 轮。
用扫描线+线段树处理出最小值和（连通块与最小值不同）的最小值。
这样如果最小值和 \(i\) 在同一个连通块中，就选第二个就好了。
时间复杂度：\(O(m\log^2n)\)
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<functional>
#include<cmath>
#include<vector>
#include<assert.h>
//using namespace std;
using std::min;
using std::max;
using std::swap;
using std::sort;
using std::reverse;
using std::random_shuffle;
using std::lower_bound;
using std::upper_bound;
using std::unique;
using std::vector;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
void open(const char *s){
#ifndef ONLINE_JUDGE
char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
void open2(const char *s){
#ifdef DEBUG
char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}
void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}
int upmin(int &a,int b){if(b<a){a=b;return 1;}return 0;}
int upmax(int &a,int b){if(b>a){a=b;return 1;}return 0;}
const ll inf=0x3fffffffffffffffll;
typedef std::pair<pll,pll> orzzjt;
const int N=100010;
orzzjt merge(orzzjt a,orzzjt b)
{
orzzjt c;
if(a.first<b.first)
{
c=a;
if(b.first.second!=c.first.second)
c.second=min(c.second,b.first);
else
c.second=min(c.second,b.second);
}
else
{
c=b;
if(a.first.second!=c.first.second)
c.second=min(c.second,a.first);
else
c.second=min(c.second,a.second);
}
return c;
}
int c[N];
namespace seg
{
orzzjt s[4*N];
ll t[4*N];
#define mid ((L+R)>>1)
#define lc (p<<1)
#define rc ((p<<1)|1)
void mt(int p)
{
s[p]=merge(s[lc],s[rc]);
}
void build(int p,int L,int R)
{
t[p]=0;
if(L==R)
{
s[p].first=pll(0,c[L]);
s[p].second=pll(inf,0);
return;
}
build(lc,L,mid);
build(rc,mid+1,R);
mt(p);
}
void add(int p,ll v)
{
t[p]+=v;
s[p].first.first+=v;
s[p].second.first+=v;
}
void push(int p)
{
if(t[p])
{
add(lc,t[p]);
add(rc,t[p]);
t[p]=0;
}
}
void add(int p,int l,int r,ll v,int L,int R)
{
if(l<=L&&r>=R)
{
add(p,v);
return;
}
push(p);
if(l<=mid)
add(lc,l,r,v,L,mid);
if(r>mid)
add(rc,l,r,v,mid+1,R);
mt(p);
}
orzzjt query(int p,int l,int r,int L,int R)
{
if(l<=L&&r>=R)
return s[p];
push(p);
if(r<=mid)
return query(lc,l,r,L,mid);
if(l>mid)
return query(rc,l,r,mid+1,R);
return merge(query(lc,l,r,L,mid),query(rc,l,r,mid+1,R));
}
}
struct info
{
int x,y1,y2,w;
info(int a=0,int b=0,int c=0,int d=0):x(a),y1(b),y2(c),w(d){}
};
int cmp(info a,info b)
{
return a.x<b.x;
}
info a[4*N];
int n,m;
int t;
int cnt;
int f[N];
ll ans;
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
int merge(int x,int y)
{
if(find(x)==find(y))
return 0;
f[find(x)]=find(y);
return 1;
}
pll h[N];
int e[N];
int main()
{
open("72G");
scanf("%d%d",&n,&m);
int x1,x2,y1,y2,w;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&w);
a[++t]=info(x1,y1,y2,w);
a[++t]=info(x2+1,y1,y2,-w);
a[++t]=info(y1,x1,x2,w);
a[++t]=info(y2+1,x1,x2,-w);
}
sort(a+1,a+t+1,cmp);
cnt=n;
for(int i=1;i<=n;i++)
{
f[i]=i;
c[i]=i;
e[i]=i;
}
while(cnt>1)
{
seg::build(1,1,n);
int j=1;
for(int i=1;i<=cnt;i++)
h[i]=pll(inf,inf);
for(int i=1;i<=n;i++)
{
for(;j<=t&&a[j].x==i;j++)
seg::add(1,a[j].y1,a[j].y2,a[j].w,1,n);
orzzjt s;
if(i==1)
s=seg::query(1,i+1,n,1,n);
else if(i==n)
s=seg::query(1,1,i-1,1,n);
else
s=merge(seg::query(1,1,i-1,1,n),seg::query(1,i+1,n,1,n));
if(s.first.second!=c[i])
h[c[i]]=min(h[c[i]],s.first);
else
h[c[i]]=min(h[c[i]],s.second);
}
for(;j<=t;j++)
seg::add(1,a[j].y1,a[j].y2,a[j].w,1,n);
for(int i=1;i<=cnt;i++)
if(merge(e[i],e[h[i].second]))
ans+=h[i].first;
cnt=0;
for(int i=1;i<=n;i++)
if(find(i)==i)
{
c[i]=++cnt;
e[cnt]=i;
}
for(int i=1;i<=n;i++)
c[i]=c[find(i)];
}
printf("%lld\n",ans);
return 0;
}
最新文章
- 在VMware上安装Linux(CentOS)
- 第四章ContentProvider
- 解决关于ArcGIS10.2服务手动启动的问题
- ASP.NET 5系列教程 (四)：向视图中添加服务和发布应用到公有云
- css一个图片包含多个图片|网站侧栏导航
- delphi线程的创建、挂起、激活与终止（用绘图做实验，简单又好用）
- linux 在批处理中，完整路径有空格的处理方式（加引號）
- c# 播放器 支持所有格式
- Confluence, JIRA, Fisheye
- Unity3D Layer要点
- java 多线程访问同一个对象数据保护的问题
- CSS效果：动态图标
- oc之脚本
- Linux基础学习笔记3-用户权限
- Linux服务器下安装vmware虚拟机
- java笔记 -- java运算
- 【python】关键网站
- Oracle性能优化4-索引
- WP8.1学习系列(第七章)——应用选项卡Pivot交互UX
- Git 之 git原理简介