题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=4388
题解
模拟Prim算法？
原题所述的过程就是Prim算法求最大生成树的过程。于是我们可以知道起始点并没有影响。
那么就用数据结构模拟Prim算法吧。
首先离散化所有区间，每个区间只需要一个点和外面相连，其余点均按照覆盖该点区间的最大权值与这个点相连。因此简单利用线段树即可求出这一部分的答案。
对于剩下的部分，用维护\(T\)表示目前没有加入的点，先加入左边\(1\)号点，同时用大根堆维护已加入点和未加入点之间的连边（也就是有一部分已加入一部分未加入的区间）
每次从堆中取出一个区间，随便找一个该区间内还在\(T\)集中的点（若不存在就什么都不干），把它从\(T\)集中删掉，顺便把包含它的所有没访问过的区间加入队列
这个可以使用线段树实现，两棵线段树分别维护两边的点，把每个区间拆成\(\log\)段，放到线段树的每个节点上，顺便维护每个区间内依然存在的点的最大值（或最小值，目的就是随便找一个点），每次删掉一个点的时候删掉线段树从根到它的所有区间并扔进堆里，并且把这个点标记为不存在（最大值改成\(0\)）.
这一部分使用vector实现可能会MLE，可以使用链表实现。
总时间复杂度\(O(n\log n)\).
代码
#include<bits/stdc++.h>
#define llong long long
#define pii pair<int,int>
#define mkpr make_pair
using namespace std;
const int N = 2e5;
const int SIZ = 3.5e6;
struct Element
{
int lx,ly,rx,ry; llong w;
bool operator <(const Element &arg) const {return w>arg.w;}
} qr[N+3];
priority_queue<pii> pq;
bool del[N+3];
struct SegmentTree
{
struct List
{
int nxt,val;
} li[SIZ+3];
struct SgTNode
{
int fe;
int maxi;
} sgt[(N<<2)+3];
int siz;
void build(int u,int le,int ri)
{
sgt[u].maxi = ri;
if(le==ri) {return;}
int mid = (le+ri)>>1;
build(u<<1,le,mid); build(u<<1|1,mid+1,ri);
}
void insert(int u,int le,int ri,int lb,int rb,int x)
{
if(lb>rb) {return;}
if(le>=lb && ri<=rb) {siz++; li[siz].nxt = sgt[u].fe; li[siz].val = x; sgt[u].fe = siz; return;}
int mid = (le+ri)>>1;
if(lb<=mid) {insert(u<<1,le,mid,lb,rb,x);}
if(rb>mid) {insert(u<<1|1,mid+1,ri,lb,rb,x);}
}
int query(int u,int le,int ri,int lb,int rb)
{
if(lb>rb) {return 0;}
if(le>=lb && ri<=rb) {return sgt[u].maxi;}
int mid = (le+ri)>>1,ret = 0;
if(lb<=mid) {ret = max(ret,query(u<<1,le,mid,lb,rb));}
if(rb>mid) {ret = max(ret,query(u<<1|1,mid+1,ri,lb,rb));}
return ret;
}
void delet(int u,int le,int ri,int pos)
{
for(int &i=sgt[u].fe; i; i=li[i].nxt)
{
if(!del[li[i].val]) {del[li[i].val] = true; pq.push(mkpr(qr[li[i].val].w,li[i].val));}
}
if(le==ri) {sgt[u].maxi = 0; return;}
int mid = (le+ri)>>1;
if(pos<=mid) {delet(u<<1,le,mid,pos);}
else {delet(u<<1|1,mid+1,ri,pos);}
sgt[u].maxi = max(sgt[u<<1].maxi,sgt[u<<1|1].maxi);
}
} sgt1,sgt2;
struct SegmentTree2
{
int maxi[(N<<2)+3];
void insert(int u,int le,int ri,int lb,int rb,int x)
{
if(lb>rb) return;
if(le>=lb && ri<=rb) {maxi[u] = max(maxi[u],x); return;}
int mid = (le+ri)>>1;
if(lb<=mid) {insert(u<<1,le,mid,lb,rb,x);}
if(rb>mid) {insert(u<<1|1,mid+1,ri,lb,rb,x);}
}
int query(int u,int le,int ri,int pos)
{
if(le==ri) {return maxi[u];}
int mid = (le+ri)>>1;
if(pos<=mid) {return max(maxi[u],query(u<<1,le,mid,pos));}
else {return max(maxi[u],query(u<<1|1,mid+1,ri,pos));}
}
} sgt3,sgt4;
vector<int> discx,discy;
int n,m,q;
llong ans;
int getdiscx(int x) {return lower_bound(discx.begin(),discx.end(),x)-discx.begin();}
int getdiscy(int x) {return lower_bound(discy.begin(),discy.end(),x)-discy.begin();}
int main()
{
scanf("%d%d%*d%d",&n,&m,&q);
for(int i=1; i<=q; i++)
{
scanf("%d%d%d%d%lld",&qr[i].lx,&qr[i].rx,&qr[i].ly,&qr[i].ry,&qr[i].w);
discx.push_back(qr[i].lx-1),discx.push_back(qr[i].rx),discy.push_back(qr[i].ly-1),discy.push_back(qr[i].ry);
}
discx.push_back(0),discy.push_back(0);
sort(discx.begin(),discx.end()); discx.erase(unique(discx.begin(),discx.end()),discx.end());
sort(discy.begin(),discy.end()); discy.erase(unique(discy.begin(),discy.end()),discy.end());
for(int i=1; i<=q; i++)
{
qr[i].lx = getdiscx(qr[i].lx-1)+1,qr[i].rx = getdiscx(qr[i].rx),qr[i].ly = getdiscy(qr[i].ly-1)+1,qr[i].ry = getdiscy(qr[i].ry);
}
n = discx.size()-1,m = discy.size()-1;
sgt1.build(1,1,n); sgt2.build(1,1,m);
for(int i=1; i<=q; i++)
{
sgt3.insert(1,1,n,qr[i].lx,qr[i].rx,qr[i].w);
sgt4.insert(1,1,m,qr[i].ly,qr[i].ry,qr[i].w);
sgt1.insert(1,1,n,qr[i].lx,qr[i].rx,i);
sgt2.insert(1,1,m,qr[i].ly,qr[i].ry,i);
}
for(int i=1; i<=n; i++)
{
ans += 1ll*sgt3.query(1,1,n,i)*(discx[i]-discx[i-1]-1ll);
}
for(int i=1; i<=m; i++)
{
ans += 1ll*sgt4.query(1,1,m,i)*(discy[i]-discy[i-1]-1ll);
}
sgt1.delet(1,1,n,1);
while(!pq.empty())
{
int i = pq.top().second; pq.pop();
int ux = sgt1.query(1,1,n,qr[i].lx,qr[i].rx);
if(ux)
{
ans += qr[i].w;
sgt1.delet(1,1,n,ux);
pq.push(mkpr(qr[i].w,i));
continue;
}
int uy = sgt2.query(1,1,m,qr[i].ly,qr[i].ry);
if(uy)
{
ans += qr[i].w;
sgt2.delet(1,1,m,uy);
pq.push(mkpr(qr[i].w,i));
}
}
if(sgt1.sgt[1].maxi||sgt2.sgt[1].maxi) {puts("-1"); return 0;}
printf("%lld\n",ans);
return 0;
}