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)


相关推荐

  • Head First Java(中文版)

    Head First Java(中文版)网站更多书籍点击进入>>CiCi岛下载电子版仅供预览及学习交流使用,下载后请24小时内删除,支持正版,喜欢的请购买正版书籍电子书下载(皮皮云盘-点击“普通下载”)购买正版封页编辑推荐★第14届Jolt大奖的参赛图书。  ★《HeadFirstJava》使纸质图书成为了你所见过的*接近GUI的事物,使学习Java成为一种风尚。  ★Java技术无所不在——如果…

  • 不是单组分组函数

    不是单组分组函数问题:一:SELECT tablespace_name, SUM(bytes) freeFROM dba_free_space不是单组分组函数原因: 1、如果程序中使用了分组函数,则有两种情况可以使用:程序中存在group by,并指定了分组条件,这样可以将分组条件一起查询出来改为:  SELECT tablespace_name, SUM(bytes) freeFROM dba_free_spa…

  • Java学习笔记–StringTokenizer的使用「建议收藏」

    Java学习笔记–StringTokenizer的使用「建议收藏」拓展:Pattern.split替代String.splithttp://www.cnblogs.com/gnivor/p/4386978.htmlStringTokenizer是一个用来分隔St

  • nv12 yuv_yv12格式是什么

    nv12 yuv_yv12格式是什么用videoCapture和IAMStreamConfig拿到的支持的格式列表。发现支持2中图像格式,YV12和NV12。具体是怎么样的内存分布不知道。查了些文档。自己修改了几个图。看出了点端倪YV12先看看http://www.fourcc.org/yuv.php上比较标准的定义:YV12Thisistheformatofchoicef…

  • mysql截取中文字符_mysql截取字符串函数-Go语言中文社区

    mysql截取中文字符_mysql截取字符串函数-Go语言中文社区目标将rull字段值的0.1g*14粒/1.5mg*30片/100ml(氨甲环酸0.5g:氯化钠0.84g)*1瓶中的mg/g/ml开头的数字取出设置到另外一个字段上去SELECTidfromsheet2whererulllike’%ml%’;SELECTid,count,LEFT(rull,LOCATE(‘g’,rull)-1)fromsheet2w…

  • landset8各波段_landsat8波段

    landset8各波段_landsat8波段Landsat8的不同波段组合说明(2013-08-0811:32:56)转载▼标签:landsat8oli陆地成像仪杂谈分类:遥感技术LandsatTM(ETM+)7个波段可以组合很多RGB方案用于不同地物的解译,Landsat8的OLI陆地成像仪包括9个波段,可以组合更多的RGB方案。OLI包括了ETM+传感器所有的波段,为了避免大气吸收特征,OLI对波段进行了重新调整,比较大的调整是OL…

发表回复

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

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