首页 > 其他分享 >CF763E Timofey and our friends animals

CF763E Timofey and our friends animals

时间:2024-03-10 16:45:26浏览次数:19  
标签:rt sz int top CF763E Timofey our define

使用回滚莫队可以有效降低思维含量。

对于回滚莫队和可撤销并查集,本文不再赘述。

假设当前询问是 \([L,R]\),目前加入了 \([l,r]\) 的所有点和边。将 \(r\) 增加 \(1\) 时,连边 \((r+1,v\in[l,r])\)。

然后需要处理左边的散块。对于所有零散的 \(l\),连边 \((l,v\in[L,R])\)。上述两种加边能维护 \([L,R]\) 的并查集。并查集合并的同时修改答案。

// Title:  Timofey and our friends animals
// Source: CF763E
// Author: Jerrywang
#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define ll long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
const int N=100010;
using namespace std;

struct query
{
    int l, r, i;
} q[N]; int n, m, k, len, b[N], ans[N];
vector<query> vec[N];
vector<int> g[N];
bool cmp(query x, query y)
{
    if(b[x.l]!=b[y.l]) return b[x.l]<b[y.l];
    return x.r<y.r;
}

struct op {int u, rt, v, sz;} s[N]; int top=0;
int rt[N], sz[N];
void init()
{
    top=0; rep(i, 1, n) rt[i]=i, sz[i]=1;
}
int root(int u) {return u==rt[u]?u:root(rt[u]);}
int merge(int u, int v) // 合并连通块则返回1
{
    u=root(u), v=root(v);
    if(u==v) return 0;
    if(sz[u]>sz[v]) swap(u, v);
    s[++top]={u, rt[u], v, sz[v]};
    rt[u]=v, sz[v]+=sz[u];
    return 1;
}
void goback(int tp) // 撤销
{
    while(top>tp)
        rt[s[top].u]=s[top].rt, sz[s[top].v]=s[top].sz, top--;
}

void ins(int &res, int u, int l, int r) // 加点
{
    res++;
    for(int v:g[u]) if(l<=v && v<=r)
        res-=merge(u, v);
}

int main()
{
    scanf("%d%d%d", &n, &k, &m); len=sqrt(n);
    rep(i, 1, n) b[i]=(i-1)/len+1;
    rep(i, 1, m)
    {
        int u, v; scanf("%d%d", &u, &v);
        g[u].push_back(v), g[v].push_back(u);
    }
    scanf("%d", &m);
    rep(i, 1, m) scanf("%d%d", &q[i].l, &q[i].r), q[i].i=i;
    sort(q+1, q+m+1, cmp);
    rep(i, 1, m) vec[b[q[i].l]].push_back(q[i]);
    rep(k, 1, b[n])
    {
        int R=min(n, k*len); init();
        int r=R, res=0, res1, _top;
        for(auto t:vec[k])
        {
            if(t.r<=R)
            {
                res1=0, _top=top;
                rep(l, t.l, t.r) ins(res1, l, t.l, t.r);
                ans[t.i]=res1, goback(_top);
                continue;
            }
            while(r<t.r) ins(res, ++r, R+1, r);
            res1=res, _top=top;
            rep(l, t.l, R) ins(res1, l, t.l, r);
            ans[t.i]=res1, goback(_top);
        }
    }
    rep(i, 1, m) printf("%d\n", ans[i]);
    
    return 0;
}

标签:rt,sz,int,top,CF763E,Timofey,our,define
From: https://www.cnblogs.com/jerrywang2009/p/18064347

相关文章

  • Bootstrap Your Own Latent A New Approach to Self-Supervised Learning论文阅读笔记
    BootstrapYourOwnLatentANewApproachtoSelf-SupervisedLearning论文阅读笔记Abstract​ 我们提出了BYOL,一种新的自监督图像表示学习的方法。BYOL依赖于两个神经网络,即在线网络和目标网络,它们相互作用和相互学习。从一个图像的增广视图出发,我们训练在线网络来预测同一图......
  • tryhackme-Source(来源)
    根据题目描述,这是一个webmin的应用程序,虽然没有了解过,可以通过开源信息搜索查看通过官网可以看出,这是一个资源信息态势图信息收集使用nmap进行端口扫描暂时扫描出靶机开放两个端口22和10000端口访问10000端口发现下方提示,说明服务运行在SSLmode,也就是使用https访问进入......
  • Golang使用SSE(EventSource)
    gopackagemainimport( "fmt" "gopkg.in/antage/eventsource.v1" "log" "net/http" "time")funcmain(){ es:=eventsource.New(nil,nil) deferes.Close() http.Handle("/",http.FileServe......
  • Distance Learning Courses in MAC
    这道题目其实我们如果位运算的题目有取值范围的话(这道题目的\([x,y]\)),我们可以统计公共前缀首先对于一个数对\((x_i,y_i)\)(假设\(x_i≠y_i\)),我们先统计他们的最长公共前缀比如\(000110101\)和\(000111000\),他们的最长公共前缀就是\(000110000\)(位数都是\(32\)位,这里省略了,公共前......
  • Though Our Paths May Diverge(JSOI 2024 游记)
    Isn’titsupposedtobesunnynow?且当是JSOI2024的游记吧。省选前的精神状态处于一种微妙的平衡。确实也不断在给自己心理暗示,自己有省队水平,但是其实无论是哪边的模拟打得都属于比较稀烂的水平,有的时候真的是一题不会签不上到。跟不上zhy和黄色蜜蜂的节奏啊,大概就......
  • vscode 的sync的问题RequestFailed (UserDataSyncError) syncResource:unknown operat
    024-03-0708:58:24.361[error]RequestFailed(UserDataSyncError)syncResource:unknownoperationId:unknown:Connectionrefusedfortherequest'https://vscode-sync.trafficmanager.net/v1/manifest'.atu.D(c:\Debug\VSCode\resources\app\ou......
  • CF1935E Distance Learning Courses in MAC
    CF1935EDistanceLearningCoursesinMAC题目大意给定\(n\)个变量\(z_i\in[x_i,y_i]\),你可以在范围内任意指定\(z_i\)的值。\(q\)次查询,每次查询给定区间\([l_i,r_i]\),求用这些变量得到的二进制或最大值。思路选择\(z\in[x,y]\),贡献分为两部分(1)\([x,y]\)的......
  • 【UVM】 【source_code】 uvm_cmdline_processor
    classuvm_cmdline_processor 函数get_arg_values()用于收集命令行(commandline)中匹配的参数,便于后续处理。返回所有匹配上的参数数量,所有匹配上的参数词尾被存放在values[$]中。sourcecodefunctionintget_arg_values(stringmatch,refstringvalues[$]);  int......
  • 数据盘故障导致journalnode异常恢复
    背景环境:hdp2.6.6部署的小集群(4节点),这个投入生产后,转手了很多批次人维护,安装源介质这些通通都找不到了,目前官网无法下载hdp的安装介质,中途有坏了一个节点的系统盘,维修好了后,因为没有安装介质,一直都没有恢复。集群部署了4个jn,昨天一个节点的data1故障,导致namenode异常无法启动和ha......
  • Autowired和Resource的区别
    @Autowired是Spring框架中的注解,它可以用来标注字段、构造函数、方法等,表示需要自动装配。它可以用来注入依赖的bean。如果有多个bean符合条件,可能会抛出异常。@Resource是Java自带的注解,它可以用来标注字段、方法等,表示需要自动装配。它可以用来注入依赖的bean。如果有多个bean......