2020CCPC长春站部分题解

Wesley13
• 阅读 265

F题

dsu on tree维护一个数组t[][][]。t[i][j][k]表示当前子树内a[u]=i且u的第j位是k的u的个数。

2020CCPC长春站部分题解 这个东西没办法直接维护的,但是对于2020CCPC长春站部分题解 ,你没必要知道2020CCPC长春站部分题解 是什么,假如2020CCPC长春站部分题解 的第2020CCPC长春站部分题解 位是0,那么你需要知道第2020CCPC长春站部分题解 位是1的2020CCPC长春站部分题解 的个数即可。

因此把2020CCPC长春站部分题解 直接拆成20位,就可以统计答案了。

我个人理解dsu on tree对于处理子树间的贡献和子树内的贡献这两种不同的题型有两种不同的写法,需要特别注意。

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define sz(x)  (int)x.size()
#define cl(x)  x.clear()
#define all(x)  x.begin() , x.end()
#define rep(i , x , n)  for(int i = x ; i <= n ; i ++)
#define per(i , n , x)  for(int i = n ; i >= x ; i --)
#define mem0(x)  memset(x , 0 , sizeof(x))
#define mem_1(x)  memset(x , -1 , sizeof(x))
#define mem_inf(x)  memset(x , 0x3f , sizeof(x))
#define debug(x)  cerr << #x << " = " << x << '\n'
#define ddebug(x , y)  cerr << #x << " = " << x << "   " << #y << " = " << y << '\n'
#define ios std::ios::sync_with_stdio(false) , cin.tie(0)
using namespace std ;
typedef long long ll ;
typedef long double ld ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
typedef double db ;
const int mod = 998244353 ;
const int maxn = 1e5 + 10 ;
const int maxm = 1e6 + 1e5 + 10 ;
const int inf = 0x3f3f3f3f ;
const double eps = 1e-6 ; 
int n , a[maxn] ;
int c[maxn] ;
vector<int> g[maxn] ;
ll ans = 0 ;
struct Dsu_on_tree
{
    int siz[maxn] , son[maxn] ;
    int flag ;
    int t[maxm][20][2] ; //t[i][j][k]表示a[u]=i且u的第j位是k的u的个数
    void init() 
    {
        flag = 0 ;
        memset(siz , 0 , sizeof(siz)) ;
        memset(son , 0 , sizeof(son)) ;
        memset(t , 0 , sizeof(t)) ;   
        rep(i , 0 , 19)  c[i] = (1 << i) ;
    }
    void dfs1(int f , int u)
    {
        siz[u] = 1 ;
        for(auto v : g[u])
        {
            if(v == f) continue ;
            dfs1(u , v) ; 
            siz[u] += siz[v] ;
            if(siz[v] > siz[son[u]]) son[u] = v ;
        }
    }
    void add(int u , int x)
    {
        int tmp = a[u] ;
        rep(j , 0 , 19)  t[tmp][j][u % 2] += x , u /= 2 ;
    }
    void dfs3(int fa , int u , int lca)
    {
        int s = (a[u] ^ a[lca]) ;
        int tmp = u ;
        rep(j , 0 , 19)  ans += 1ll * t[s][j][1 - (tmp % 2)] * c[j] , tmp /= 2 ;
        for(auto v : g[u])
        {
            if(v == fa)  continue ;
            dfs3(u , v , lca) ;
        }
    }
    void dfs4(int fa , int u , int x)
    {
        add(u , x) ;
        for(auto v : g[u])
        {
            if(v == fa)  continue ;
            dfs4(u , v , x) ;
        }
    }
    void calc(int f , int u , int x)
    {
        for(auto v : g[u])
        {
            if(v == f || v == flag) continue ;
            if(x == 1)  dfs3(u , v , u) ;
            dfs4(u , v , x) ;
        }
        add(u , x) ;
    }
    void dfs2(int f , int u , int keep)
    {
        for(auto v : g[u])
        {
            if(v == f || v == son[u]) continue ;
            dfs2(u , v , 0) ;
        }
        if(son[u])  dfs2(u , son[u] , 1) , flag = son[u] ;
        calc(f , u , 1) ;
        if(son[u]) flag = 0 ;
        if(!keep)  calc(f , u , -1) ;
    }
} dsu_on_tree ;
int main()
{
    ios ;
    cin >> n ;
    rep(i , 1 , n)  cin >> a[i] ;
    rep(i , 1 , n - 1)
    {
        int u , v ;
        cin >> u >> v ;
        g[u].pb(v) , g[v].pb(u) ;
    }
    dsu_on_tree.init() ;
    dsu_on_tree.dfs1(1 , 1) ;
    dsu_on_tree.dfs2(1 , 1 , 0) ;
    cout << ans << '\n' ;
    return 0 ;
}

K题

不妨设2020CCPC长春站部分题解 ,打表后会发现2020CCPC长春站部分题解 ,这就可以直接2020CCPC长春站部分题解 预处理出符合条件的二元组了。

但是还是不好直接做,不过如果打表技术再高超一点,会发现对于每个2020CCPC长春站部分题解 ,满足条件的2020CCPC长春站部分题解 最多只有2020CCPC长春站部分题解 个。

这样操作2就按秩合并,操作3就暴力修改。

PS:其实F题需要想到拆位,K题需要想到满足条件的二元组不是很多,才可以做。假如都想到了,那么K比F好写很多。不过如果都没想到,那这场就没了。

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define sz(x)  (int)x.size()
#define cl(x)  x.clear()
#define all(x)  x.begin() , x.end()
#define rep(i , x , n)  for(int i = x ; i <= n ; i ++)
#define per(i , n , x)  for(int i = n ; i >= x ; i --)
#define mem0(x)  memset(x , 0 , sizeof(x))
#define mem_1(x)  memset(x , -1 , sizeof(x))
#define mem_inf(x)  memset(x , 0x3f , sizeof(x))
#define debug(x)  cerr << #x << " = " << x << '\n'
#define ddebug(x , y)  cerr << #x << " = " << x << "   " << #y << " = " << y << '\n'
#define ios std::ios::sync_with_stdio(false) , cin.tie(0)
using namespace std ;
typedef long long ll ;
typedef long double ld ;
typedef pair<int , int> pii ;
typedef pair<ll , ll> pll ;
typedef double db ;
const int mod = 998244353 ;
const int maxn = 3e5 + 10 ;
const int inf = 0x3f3f3f3f ;
const double eps = 1e-6 ; 
int n , q , a[maxn] ;
vector<int> v[maxn] ;
set<pii> s[maxn] ;
ll ans = 0 ;
struct Dsu
{
    int pre[maxn] , siz[maxn] ;
    void init(int n)
    {
        for(int i = 1 ; i <= n ; i ++)  pre[i] = i , siz[i] = 1 ;
    }
    int find(int u) 
    {
        if(pre[u] == u)  return u ;
        return pre[u] = find(pre[u]) ;
    }
    void join(int x , int y)
    {
        int fx = find(x) ;
        int fy = find(y) ;
        if(fx != fy)  
        {
            if(siz[fx] <= siz[fy])  pre[fx] = fy , siz[fy] += siz[fx] ;
            else  pre[fy] = fx , siz[fx] += siz[fy] ;
        }       
    }
    ll cal(int fx , int t , int cnt)
    {
        ll res = 0 ;
        for(auto u : v[t])
        {
            auto it = s[fx].lower_bound({u , 0}) ;
            if(it != s[fx].end())
            {
                int tt = (*it).fi ;
                int num = (*it).se ;
                if(tt == u)  res += 1ll * num * cnt ;
            }
        }
        return res ;
    }
    void merge(int x , int y)
    {
        int fx = find(x) ;
        int fy = find(y) ;
        if(fx != fy)  
        {
            if(siz[fx] < siz[fy])  swap(fx , fy) ;
            pre[fy] = fx ;
            siz[fx] += siz[fy] ;
            for(auto u : s[fy])
            {
                int t = u.fi ;
                int cnt = u.se ;
                ans += cal(fx , t , cnt) ;
            }
            for(auto u : s[fy])
            {
                int t = u.fi ;
                int cnt = u.se ;
                auto it = s[fx].lower_bound({t , 0}) ;
                if(it != s[fx].end())
                {
                    int tt = (*it).fi ;
                    int num = (*it).se ;
                    if(tt == t)  s[fx].erase(it) , s[fx].insert({tt , num + cnt}) ;
                    else  s[fx].insert(u) ;
                }
                else  s[fx].insert(u) ;
            }
        }
    }
    void update(int x , int y)
    {
        int fx = find(x) ;
        auto it = s[fx].lower_bound({a[x] , 0}) ;
        int t = a[x] ;
        int num = (*it).se ;
        if(num == 1)  s[fx].erase(it) ;
        else  s[fx].erase(it) , s[fx].insert({t , num - 1}) ;
        //del
        ans -= cal(fx , a[x] , 1) ;
        //add

        a[x] = y ;
        ans += cal(fx , a[x] , 1) ;
        it = s[fx].lower_bound({a[x] , 0}) ;
        if(it == s[fx].end())  s[fx].insert({a[x] , 1}) ;
        else
        {
            int t = (*it).fi ;
            int cnt = (*it).se ;
            if(t == a[x])  s[fx].erase(it) , s[fx].insert({t , cnt + 1}) ;
            else  s[fx].insert({a[x] , 1}) ;
        }
    }
} dsu ;
void prework()
{
    dsu.init(n) ;
    rep(b , 1 , 200000)  for(int a = b + b ; a <= 200000 ; a += b)
    {
        int c = a - b ;
        if((a ^ c) == b)  v[a].pb(c) , v[c].pb(a) ;
    }
    rep(i , 1 , n)  s[i].insert({a[i] , 1}) ;
}
int main()
{
    ios ;
    cin >> n >> q ;
    rep(i , 1 , n)  cin >> a[i] ;
    n += q ;
    prework() ;
    while(q --)
    {
        int op , x , y ;
        cin >> op >> x >> y ;
        if(op == 1)  a[x] = y , s[x].insert({y , 1}) ;
        else if(op == 2)  dsu.merge(x , y) ;
        else  dsu.update(x , y) ;
        cout << ans << '\n' ;
    }
    return 0 ;
}
点赞
收藏
评论区
推荐文章
blmius blmius
1年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录 问题 用navicat导入数据时,报错: 原因这是因为当前的MySQL不支持datetime为0的情况。 解决修改sql\mode: sql\mode:SQL Mode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。 全局s
小森森 小森森
2个月前
校园表白墙微信小程序V1.0 SayLove -基于微信云开发-一键快速搭建,开箱即用
后续会继续更新,敬请期待2.0全新版本 欢迎添加左边的微信一起探讨!项目地址:](https://www.aliyun.com/activity/daily/bestoffer?userCodesskuuw5n) \2. Bug修复更新日历 2. 情侣脸功能大家不要使用了,现在阿里云的接口已经要收费了(土豪请随意), \ \ 和 注意
Wesley13 Wesley13
1年前
Java爬虫之JSoup使用教程
title: Java爬虫之JSoup使用教程 date: 2018-12-24 8:00:00 +0800 update: 2018-12-24 8:00:00 +0800 author: me cover: [https://img-blog.csdnimg.cn/20181224144920712](https://www.oschin
Stella981 Stella981
1年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置 1、virsh edit centos7 找到“memory”和“vcpu”标签,将 <name>centos7</name> <uuid>2220a6d1-a36a-4fbb-8523-e078b3dfe795</uuid>
Wesley13 Wesley13
1年前
Java日期时间API系列36
  十二时辰,古代劳动人民把一昼夜划分成十二个时段,每一个时段叫一个时辰。二十四小时和十二时辰对照表: **时辰** **时间** **24时制** 子时 深夜 11:00 - 凌晨 01:00 23:00 - 01 :00 丑时 上午 01:00 - 上午 03:00 01:00 - 03 :00 寅时 上午 03:00 - 上午 0
Wesley13 Wesley13
1年前
MySQL查询按照指定规则排序
1.按照指定(单个)字段排序 select * from table_name order id desc; 2.按照指定(多个)字段排序 select * from table_name order id desc,status desc; 3.按照指定字段和规则排序 selec
Stella981 Stella981
1年前
Android蓝牙连接汽车OBD设备
//设备连接 public class BluetoothConnect implements Runnable {     private static final UUID CONNECT_UUID = UUID.fromString("00001101-0000-1000-8000-00805F9B34FB");
Stella981 Stella981
1年前
Docker 部署SpringBoot项目不香吗?
  公众号改版后文章乱序推荐,希望你可以点击上方“**Java进阶架构师**”,点击右上角,将我们设为**★**“**星标**”!这样才不会错过每日进阶架构文章呀。   ![](http://dingyue.ws.126.net/2020/0920/b00fbfc7j00qgy5xy002kd200qo00hsg00it00cj.jpg)   **2
Stella981 Stella981
1年前
Angular material mat
Icon Icon Name mat-icon code _add\_comment_ add comment icon <mat-icon> add\_comment</mat-icon> _attach\_file_ attach file icon <mat-icon> attach\_file</mat-icon> _attach\
Wesley13 Wesley13
1年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
#### 背景描述 # Time: 2019-01-24T00:08:14.705724+08:00 # User@Host: **[**] @ [**] Id: ** # Schema: sentrymeta Last_errno: 0 Killed: 0 # Query_time: 0.315758 Lock_
helloworld_34035044 helloworld_34035044
4个月前
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。 uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid() 或 uuid(sep)参数说明:sep 布尔值,生成的uuid中是否包含分隔符'',缺省为