分析
先看删边操作。
由于并不保证是森林,所以我们没有好的方法来在线维护删边相关的操作。
所以,我们可以套路地把询问离线,然后倒着操作。
删边变成加边。
需要注意的是权值的修改,记录时要把当前权值和修改的权值反过来。
然后我们发现这个操作很经典,维护方式和 [HNOI2012] 永无乡 差不多。
可以使用线段树合并或者平衡树启发式合并。
连边的时候直接合并,暴力地将大小较小的平衡树合并进较大的平衡树。
用并查集维护节点信息的位置。
时间复杂度 \(O(n\log^2n)\)。
Code
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define maxn 20004
#define maxm 60004
typedef tree<pair<int, int>,
null_type,
greater<pair<int, int>>,
rb_tree_tag,
tree_order_statistics_node_update> RBT;
RBT tr[maxn];
int val[maxn], fa[maxn];
pair<int, int> e[maxm];
bool del[maxm];
vector<tuple<char, int, int>> q;
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y)
{
x=find(x);
y=find(y);
if(x==y) return;
if(tr[x].size()>tr[y].size()) swap(x, y);
fa[x]=y;
for(auto v:tr[x]) tr[y].insert(v);
tr[x].clear();
}
double solve(int n, int m)
{
for(int i=1;i<=n;i++) cin>>val[i], tr[i].clear();
iota(fa+1, fa+1+n, 1);
for(int i=1;i<=m;i++)
cin>>e[i].first>>e[i].second;
memset(del, 0, sizeof del);
q.clear();
for(;;)
{
char c;
int x, y;
cin>>c;
if(c=='E') break;
if(c=='Q') cin>>x>>y, q.emplace_back(c, x, y);
if(c=='C')
{
cin>>x>>y;
q.emplace_back(c, x, val[x]);
val[x]=y;
}
if(c=='D')
{
cin>>x;
q.emplace_back(c, x, 0);
del[x]=1;
}
}
reverse(q.begin(), q.end());
for(int i=1;i<=n;i++) tr[i].insert({val[i], i});
for(int i=1;i<=m;i++)
{
if(del[i]) continue;
merge(e[i].first, e[i].second);
}
double ans=0;
int cnt=0;
for(auto v:q)
{
auto op=get<0>(v);
auto x=get<1>(v);
auto y=get<2>(v);
if(op=='D') merge(e[x].first, e[x].second);
if(op=='Q')
{
cnt++;
ans+=tr[find(x)].find_by_order(y-1)->first;
}
if(op=='C')
{
int t=find(x);
tr[t].erase({val[x], x});
tr[t].insert({val[x]=y, x});
}
}
return ans/cnt;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
for(int i=1;;i++)
{
int n, m;
cin>>n>>m;
if(!(n|m)) return 0;
printf("Case %d: %.6f\n", i, solve(n, m));
}
}
标签:val,int,题解,tr,cin,fa,Queries,UVA1479,find
From: https://www.cnblogs.com/redacted-area/p/18379558