首页 > 其他分享 >题解:UVA1479 Graph and Queries

题解:UVA1479 Graph and Queries

时间:2024-08-25 21:05:58浏览次数:9  
标签:val int 题解 tr cin fa Queries UVA1479 find

分析

先看删边操作。

由于并不保证是森林,所以我们没有好的方法来在线维护删边相关的操作。

所以,我们可以套路地把询问离线,然后倒着操作。

删边变成加边。

需要注意的是权值的修改,记录时要把当前权值和修改的权值反过来。

然后我们发现这个操作很经典,维护方式和 [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

相关文章

  • 题解:P7475 「C.E.L.U-02」简易输入法
    题意给定词典\(\text{U}\),每次询问读入一个字符串\(s\),以及一个整数\(x\)对于这个字符串有以下几种情形:设\(s_i\in\text{U}\)且\(s\)为\(s_i\)的前缀的个数为\(a\)。当\(a\gex\)时,请输出按照以输出次数从大到小为第一关键字,以字典序为第二关键字排序后的第\(x......
  • 题解:P7401 [COCI2020-2021#5] Planine
    题意现有一座上下起伏的山。它可以抽象为一个包含\(n\)(\(n\)为奇数)个点\((x_i,y_i)\)以及\((x_1,-\inf)\)与\((x_n,-\inf)\)的多边形。对于所有满足\(i\neq1\),\(i\neqn\),\(i\bmod2=1\)的整数\(i\),\((x_i,y_i)\)都是山谷。现要放置若干个高度为\(h\)的点光......
  • 题解:SP1182 SORTBIT - Sorted bit squence
    题意将区间\([m,n]\)的所有整数按照其二进制位表示的数中\(1\)的数量从小到大排序。如果\(1\)的数量相同,则按照数的大小排序。求序列中第\(k\)个数。其中,负数使用补码来表示:一个负数的二进制数与其相反数的二进制数之和恰好等于\(2^{32}\)。分析考虑用uint32_t存......
  • 题解:P3266 [JLOI2015] 骗我呢
    题意有一个\(n\timesm\)的数组\(x_{i,j}(1\lei\len,1\lej\lem)\),满足:\(x_{i,j}\in[0,m]\)\(\foralli\in[1,n],\forallj\in[1,m),x_{i,j}<x_{i,j+1}\)\(\foralli\in(1,n],\forallj\in[1,m),x_{i,j}<x_{i-1,j+1}\)......
  • 题解:CF70D Professor's task
    题意实现以下两种操作:往点集\(S\)中添加一个点\((x,y)\)。询问点\((x,y)\)是否在点集\(S\)的凸包中。分析动态凸包板子。建议先完成P2521[HAOI2011]防线修建。上题维护的是上半个凸包,本题维护上下两个。将凸包中的点按\(x\)排序,通过\((x,y)\)前驱......
  • 题解:P2521 [HAOI2011] 防线修建
    题意给定若干个点,实现下列操作:删除一个点。查询上凸包的周长。分析建议先完成【模板】二维凸包。对于这个删除操作,我们没有好的方法去在线维护它。考虑离线询问。这样删除操作就变成了插入操作。插入一个新点有如下两种情况:新点在凸包内。新点在凸包外。我们回忆......
  • 题解:CF235C Cyclical Quest
    题意给定一个主串\(S\)和\(n\)个询问串,求每个询问串的所有循环同构在主串中出现的次数总和。分析后缀自动机好题。循环同构的过程可以看作从该串的头部删除一个字符,并在尾部加入一个字符。在后缀自动机上,跳parent树的过程就相当于删除头部的若干个字符。所以我们可......
  • 7z解压crc错误_7-Zip - 常见问题解答
    7z解压crc错误_7-Zip-常见问题解答7z解压crc错误_7-Zip-常见问题解答1.引言1.17-Zip简介1.2CRC错误概述2.7z文件和CRC错误2.1什么是7z文件2.2CRC错误的定义2.3CRC错误对文件的影响3.常见原因分析3.1文件传输过程中的错误3.2存储介质的损坏3.3不兼容的压......
  • 题解:P5680 [GZOI2017] 共享单车
    题目分析出题人是擅长隐藏题意的建树首先给你一张无向图,然后指定一个根节点\(k\),从根节点开始沿最短路到每一个节点。如果到某个节点有多条最短路径,选择上一个节点编号最短的。考虑记录前驱的Dijkstra。namespaceDJ{intdis[maxn],pre[maxn],val[maxn],vis[maxn]......
  • 题解:SP22382 ETFD - Euler Totient Function Depth
    题目链接:link,点击这里喵。前置知识:【模板】线性筛素数,欧拉函数,点击这里喵。题意简述:给定整数$l,r,k$,求出$[l,r]$中有多少个整数不断对自己取欧拉函数刚好$k$次结果为$1$。思路:看眼数据范围,$10^{10}$的量级显然不容我们每次暴力,故考虑预处理$\varphi(i),can(i,k),su......