K – Ragdoll

K – Ragdollhttps://codeforces.com/gym/102832/problem/KOncetherewasalovelyragdollcat,namedLittleZara,wholikedtreesandmath.OnedayshemetthedogeAdam.Adamhadjustplantedsometreeseachconsistingofonlyonenode.Thenodeswerenumberedfrom11.

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

https://codeforces.com/gym/102832/problem/K

Once there was a lovely ragdoll cat, named Little Zara, who liked trees and math. One day she met the doge Adam. Adam had just planted some trees each consisting of only one node. The nodes were numbered from 11 to nn, and the ii-th node was assigned a value aiai. Adam liked pairing tree nodes, but he disliked some node pairs. A pair of nodes (i,j)(i,j) was considered bad if ii and jj were in the same tree and gcd(ai,aj)=ai⊕ajgcd⁡(ai,aj)=ai⊕aj, where gcd(x,y)gcd⁡(x,y) denotes the greatest common divisor (GCD) of integers xx and yy, and ⊕⊕ denotes the bitwise XOR operation. Adam wondered how many bad pairs there were in his forest.

Zara was good at solving problems about trees and math, so she could answer Adam’s question in a short time. However, Adam was so naughty a dog that he would repeatedly change the forest slightly and ask Zara his question again after the change.

The changes Adam might make are listed here:

  1. Adam plants a new tree with only one node numbered xx and assigned a value vv.
  2. Adam uses magic to merge the tree containing the node xx and the one containing the node yy. If xx and yy are in the same tree before the operation, the magic fails and has no effect.
  3. Adam changes the value of node xx to vv.

 

Now you are expected to help Zara answer all questions Adam asked, in order that they could sing and dance together happily.

Input

The first line contains two integers nn and mm (1≤n≤1051≤n≤105, 1≤m≤2×1051≤m≤2×105), representing the number of nodes in the original forest and the number of changes Adam would make, respectively.

The next line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤2×1051≤ai≤2×105).

Each of the next mm lines describes a change Adam made, starting with an integer tt (1≤t≤31≤t≤3) representing the type of the change.

 

  • If t=1t=1, it will be followed by two integers xx and vv (n<x≤n+mn<x≤n+m, 1≤v≤2×1051≤v≤2×105). It is guaranteed that xx’s are distinct in all changes of the first type.
  • If t=2t=2, it will be followed by two integers xx and yy (1≤x,y≤n+m1≤x,y≤n+m). It is guaranteed that the node xx and yy already exist in the forest.
  • If t=3t=3, it will be followed by two integers xx and vv. (1≤x≤n+m1≤x≤n+m, 1≤v≤2×1051≤v≤2×105). It is guaranteed that the node xx already exists in the forest.

 

Output

For each change Adam made, print one line with a single integer, representing the number of bad pairs in the forest after the change.

Examples

Input

3 6
3 2 1
2 1 2
1 5 3
2 1 2
2 3 2
2 5 1
3 3 2

Jetbrains全家桶1年46,售后保障稳定

Output

1
1
1
1
2
4

Input

10 6
6 6 4 7 7 4 6 4 6 5
2 5 1
2 10 7
2 8 7
2 7 2
2 6 2
2 9 1

Output

1
1
3
4
7
8

代码:

#include<bits/stdc++.h>
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1
#define endl '\n'
#define ps puts("###")
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int MAXN = 1e6+10;
const double EPS = 1e-12;
const ll mod = 1e9+7;
vector<ll>q[MAXN];
ll n,m,t,s;
ll a[MAXN];
ll fa[MAXN];
ll num[MAXN];
unordered_map<ll,ll>f[MAXN];
int fin(int x)
{
    if(fa[x]==x)
        return x;
    fa[x]=fin(fa[x]);
    return fa[x];
}
void un(int x,int y)
{
    ll p1=fin(x),p2=fin(y);
    fa[p1]=p2;
    //cout<<p1<<" "<<p2<<endl;
    for(auto i:f[p1])
    {
        ll id=i.first;
        //cout<<id<<endl;
        for(int k=0;k<q[id].size();k++)
        {
            ll u=q[id][k];
            //cout<<u<<endl;
            if(f[p2].count(u))//删了就T不知道为什么
            s+=i.second*f[p2][u];
            //cout<<s<<endl;
        }
    }
    for(auto i:f[p1])
    {
        ll id=i.first;
        f[p2][id]+=i.second;
    }
    f[p1].clear();
    num[p2]+=num[p1];
    return;
}
int main()
{
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=200000;i++)
    {
        for(int j=i+i;j<=200000;j+=i)
        {
            if((j^(j-i))==i)
            {
                q[j].push_back(i^j);
                q[i^j].push_back(j);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        f[i][a[i]]=1;
        fa[i]=i;
        num[i]=1;
    }
    s=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&t);
        if(t==1)
        {
            ll x,v;
            scanf("%lld %lld",&x,&v);
            a[x]=v;
            fa[x]=x;
            f[x][v]=1;
            num[x]=1;
            printf("%lld\n",s);
        }
        else if(t==2)
        {
            ll x,y;
            scanf("%lld %lld",&x,&y);
            ll p1,p2;
            p1=fin(x);
            p2=fin(y);
            if(p1!=p2)
            {
                if(num[p1]<num[p2])
                un(p1,p2);
                else
                un(p2,p1);
            }

            printf("%lld\n",s);
        }
        else if(t==3)
        {
            ll x,v;
            scanf("%lld %lld",&x,&v);
            for(int k=0;k<q[a[x]].size();k++)
            {
                ll u=q[a[x]][k];
                s-=f[fa[x]][u];
            }
            f[fa[x]][a[x]]--;
            a[x]=v;
            //cout<<s<<endl;
            for(int k=0;k<q[a[x]].size();k++)
            {
                ll u=q[a[x]][k];
                s+=f[fa[x]][u];
            }
            f[fa[x]][a[x]]++;
            printf("%lld\n",s);
        }
    }
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/215872.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • mysql前缀索引语句_mysql 前缀索引

    mysql前缀索引语句_mysql 前缀索引联合索引概念联合索引又叫复合索引,即一个覆盖表中两列或者以上的索引,例如:index_name(columna,columnb)1创建方式执行altertable语句时创建altertabletable_nameaddindexindex_name(column_list)1index_name是创建的联合索引的名字,可以没有,没有的话系统会根据该索引包含的第一列来赋名称;tabl…

  • spring源码搭建_积木搭建的基本技巧

    spring源码搭建_积木搭建的基本技巧一Spring源码下载官网下载(下载太慢):https://github.com/spring-projects/spring-framework/archive/v5.0.2.RELEASE.zip码云下载:https://gitee.com/mirrors/Spring-Framework/tree/v5.0.2.RELEASE/二Gradle的源码构建技巧1Gr…

  • 使用SplitContainer控件

    使用SplitContainer控件在Windows资源管理器中,当把鼠标指针移动到TreeView控件和ListView控件之间时,可以左右拖动鼠标调整TreeView控件和ListView控件在主窗口中的大小比例,以适应不同显示内容

  • Unity3d的安装

    Unity3d的安装**Unity3d的安装**1.在线安装a.获取在线安装程序第一步:进入官网:https://unity.com/cn第二步:在主页的底部点击下载第三步:来到UnityStore,拖到该页面的最底部,点击资源下面的Unity旧版本第四步:来到Unity下载存档,拖动页面可以看到很多版本的Unity第五步:选择一个版本,这里我们选择Unity2017.x中的2017.1.0…

  • nmap命令小结(一)

    nmap命令小结(一)Nmapnmap是一个非常强大的网络扫描工具,学习nmap的话,我建议大家多读一读官方文档,这里我所写的也仅仅是对Nmap中文文档的一个总结,以及一些我的个人看法。官方文档地址:http://www.nmap.com.cn/主机发现端口扫描主机发现nmap的主机发现主要是基于ICMP包的一个探测,所以用nmap的主机发现命令格式大多都是-P*;-sP:nmap仅对主机进行ping扫

  • S3C2440中断介绍

    S3C2440中断介绍1.1   S3C2440系统中断CPU和外设构成了计算机系统,CPU和外设之间通过总线进行连接,用于数据通信和控制,CPU管理监视计算机系统中所有硬件,通常以两种方式来对硬件进行管理监视:l  查询方式:CPU不停的去查询每一个硬件的当前状态,根据硬件的状态决定处理与否。好比是工厂里的检查员,不停的检查各个岗位工作状态,发现情况及时处理。这种方式实现起来简单,通常用在只有少量外设硬件的系

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号