首页 > 其他分享 >P9376 题解

P9376 题解

时间:2023-05-30 21:56:20浏览次数:48  
标签:sz cur rs int 题解 01trie ls P9376

首先考虑怎么暴力。

考虑把每个数进行 \(B\) 进制分解,然后我们惊奇的发现这两个操作就是把最低位去掉和往最低位后面插入一个数。

然后我们顺藤摸瓜,把每个数的分解扔到 Trie 树上,我们发现我们要找到一个节点,使得所有单词节点到其的距离之和最短,答案就是这个最短距离。

这里直接考虑一个 Trie 树上 dp,记所有单词节点到节点 \(i\) 的最短距离为 \(dp_i\),然后直接去转移。

然后考虑找找性质。

记 \(sz_i\) 表示以节点 \(i\) 为根的子树内单词节点数量,我们发现节点 \(i\) 的转移如下 \(dp_i = dp_{fa_i} - sz_j + (sz_1 - sz_j)\)。

又因为 \(sz_i \leq sz_{fa_i}\),所以只有当节点 \(i\) 满足 \(sz_i \times 2 > sz_1\) 进入到以 \(i\) 为根的子树转移才最优。

而我们又发现对于一个节点满足条件的子节点至多只有 \(1\) 个

也就是说如果把最优答案在树上的转移画出来,并称其为最优路径,那么首先这一定是一条从根出发的路径,而且以这条路径所代表的数为前缀的数一定超过总数的一半

然后有两种优化方向。

第一种是利用可持久化 Trie 树预处理,然后直接在 Trie 上利用刚刚的性质暴力 \(\log_{B} V\) 查询,缺点是对于每个 \(B\) 都要建一棵树。

第二种是因为我们只在乎最优路径上的转移,所以我们随机抽取 \(\log n\) 个节点放到 Trie 树上,显然因为这个性质类似于绝对众数的性质,因此最优的转移路径不在 Trie 上出现的可能只有 \(\frac{1}{n}\)。那么多抽取几个节点就可以基本保证一定会出现。

那么转移路径找出来了,现在问题是转移中 \(sz_i\) 怎么求?

我们有发现 \(sz_i\) 等价于 \(B\) 进制下以从根节点到节点 \(i\) 所表示的数为前缀的数的数量,而这个可以枚举这个前缀后面有几位数转变成一个连续区间上查询权值为 \([L,R]\) 的数的数量,这个可以直接主席树来搞。这么做缺点是复杂度是 \(n \log_{B}^3 V\)。

考虑到 \(\log_{2} n\) 一般远大于 \(\log_{3} n\)。

所以结合两种算法,用第一种算法解决 \(B = 2\) 的询问,用第二种算法解决其他询问。

那么就做完了。

代码极丑,慎入。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int top = 100000001;
const int maxn = 1e6+114;
struct Node{
    int sz;//当前这个节点子树内有多少个单词节点
    vector <pair<int,int> > edge;//边
}Trie[maxn];
struct node{
    int sz;
    int ls,rs;
}_01trie[maxn*30];
struct NODE{
    int val;
    int ls,rs;
}SGTtree[maxn*30];
int SGTroot[maxn];
int SGTtot=1;
int SGTask(int ql,int qr,int lt,int rt,int L,int R){
    if(rt<ql||lt>qr){
        return 0;
    }
    if(ql<=lt&&rt<=qr){
        return SGTtree[R].val-SGTtree[L].val;
    }
    int mid=(lt+rt)/2;
    int res=0;
    res+=SGTask(ql,qr,lt,mid,SGTtree[L].ls,SGTtree[R].ls);
    res+=SGTask(ql,qr,mid+1,rt,SGTtree[L].rs,SGTtree[R].rs);
    return res;
}
int SGTquery(int l,int r,int cl,int cr){
    return SGTask(cl,cr,1,top,SGTroot[l-1],SGTroot[r]);
}
void SGTupdate(int cur,int lst,int lt,int rt,int pos,int v){
    SGTtree[cur].val=SGTtree[lst].val+v;
    if(lt==rt){
        return ;
    }
    int mid=(lt+rt)/2;
    if(pos<=mid){
        SGTtree[cur].rs=SGTtree[lst].rs;
        SGTtree[cur].ls=++SGTtot;
        SGTupdate(SGTtree[cur].ls,SGTtree[lst].ls,lt,mid,pos,v);
    }
    else{
        SGTtree[cur].ls=SGTtree[lst].ls;
        SGTtree[cur].rs=++SGTtot;
        SGTupdate(SGTtree[cur].rs,SGTtree[lst].rs,mid+1,rt,pos,v);
    }
}
int qpow(int a,int b){
    if(b==0) return 1;
    if(b==1) return min(a,top);
    int res=min(qpow(a,b/2),top);
    res=min(top,res*res);
    if(b%2==1) res=min(res*a,top);
    return min(top,res);
}
void SGTadd(int pos,int val){
    SGTroot[pos]=++SGTtot;
    SGTupdate(SGTroot[pos],SGTroot[pos-1],1,top,val,1);
}
int SUMQUERY(int B,int L,int R){//查询 B 进制下区间 [L,R] 所有数长度之和 
    int res=0;
    for(int k=1;k<=30;k++){
        int l=min(top,qpow(B,k-1)),r=min(top,qpow(B,k)-1);
        res+=SGTquery(L,R,l,r)*k;
        if(r==top) break;
    }
    return res;
}
int PREQUERY(int x,int B,int L,int R){//查询 B 进制下区间 [L,R] 内多少个数前缀为 x
    int res=0;
    for(int k=0;k<=30;k++){
        int l=min(top,x*qpow(B,k)),r=min(top,(x+1)*qpow(B,k)-1);
        res+=SGTquery(L,R,l,r);
        if(r==top) break;
    }
    return res;
}
int tot=1,anser;
int _01tot=1;
int sum;
int n,m;
int flag;
stack<int> s;
int root[maxn],Sum[maxn];
void _01insert(int cur,int lst){
    _01trie[cur].sz++;
    s.pop();
    if(s.size()==0) return ;
    if(s.top()==0){
        _01trie[cur].rs=_01trie[lst].rs;
        _01trie[cur].ls=++_01tot;
        _01trie[_01trie[cur].ls].sz+=_01trie[_01trie[lst].ls].sz;
        _01insert(_01trie[cur].ls,_01trie[lst].ls);
    }
    else{
        _01trie[cur].ls=_01trie[lst].ls;
        _01trie[cur].rs=++_01tot;
        _01trie[_01trie[cur].rs].sz+=_01trie[_01trie[lst].rs].sz;
        _01insert(_01trie[cur].rs,_01trie[lst].rs);
    }
}
void _01dfs(int l,int r,int ans,int L,int R){
    if(l==0&&r==0) return ;
    anser=min(anser,ans);
    if(_01trie[_01trie[r].ls].sz-_01trie[_01trie[l].ls].sz>_01trie[_01trie[r].rs].sz-_01trie[_01trie[l].rs].sz){
        _01dfs(_01trie[l].ls,_01trie[r].ls,ans-(_01trie[_01trie[r].ls].sz-_01trie[_01trie[l].ls].sz)+(_01trie[R].sz-_01trie[L].sz-(_01trie[_01trie[r].ls].sz-_01trie[_01trie[l].ls].sz)),L,R);
    }
    else{
        _01dfs(_01trie[l].rs,_01trie[r].rs,ans-(_01trie[_01trie[r].rs].sz-_01trie[_01trie[l].rs].sz)+(_01trie[R].sz-_01trie[L].sz-(_01trie[_01trie[r].rs].sz-_01trie[_01trie[l].rs].sz)),L,R);
    }
}
int _01query(int l,int r){
    anser=INT_MAX;
    _01dfs(root[l-1],root[r],Sum[r]-Sum[l-1],root[l-1],root[r]);
    return anser;
}
void _01add(int x,int B,int pos){
    while(x!=0){
        s.push(x%B);
        x/=B;
    }
    s.push(0);
    Sum[pos]=s.size()-1+Sum[pos-1];
    root[pos]=++_01tot;
    _01trie[root[pos]].sz+=_01trie[root[pos-1]].sz;
    _01insert(root[pos],root[pos-1]);
}
void insert(int cur,int val){
    Trie[cur].sz+=val;
    s.pop();
    if(s.size()==0) return ;
    for(pair<int,int> v:Trie[cur].edge){
        if(v.second==s.top()){
            insert(v.first,val);
            return ;
        }
    }
    Trie[cur].edge.push_back(make_pair(++tot,s.top()));
    insert(tot,val);
}
void add(int x,int B){
    while(x!=0){
        s.push(x%B);
        x/=B;
    }
    s.push(0);
    sum+=s.size()-1;
    insert(1,1);
}
void dfs(int cur,int ans,int PRE,int S,int B,int L,int R){
    anser=min(anser,ans);
    for(pair<int,int> v:Trie[cur].edge){
        int nxt=PRE*B+v.second;
        int g=PREQUERY(nxt,B,L,R);
        if((S-g)-g>=0) continue;
        dfs(v.first,ans-g+(S-g),nxt,S,B,L,R);
    }
}
int query(int B,int L,int R){
    anser=INT_MAX;
    dfs(1,SUMQUERY(B,L,R),0,(R-L+1),B,L,R);
    return anser;
}
void clear(){
    for(int i=1;i<=tot;i++){
        Trie[i].edge.clear();
        Trie[i].sz=0;
    }
    sum=0;
    tot=1;
}
int a[maxn];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
            cin>>a[i];
            SGTadd(i,a[i]);
            _01add(a[i],2,i);
    }       
    while(m--){
        int l,r,B;
        cin>>l>>r>>B;
        if(B==2){
            cout<<_01query(l,r)<<"\n";
        }
        else{
        clear();
        for(int j=1;j<=22;j++){
            int x=rand()%(r-l+1)+l;
            add(a[x],B);
        }
        cout<<query(B,l,r)<<'\n';
        }
    }            
}
/*
5 2
7 6 5 8 9
1 3 2
2 5 2
*/

标签:sz,cur,rs,int,题解,01trie,ls,P9376
From: https://www.cnblogs.com/chifan-duck/p/17444584.html

相关文章

  • CODE FESTIVAL 2016 qual B E 题解
    以下\(\Sigma\)为字符集。首先单次询问\(O(|\Sigma||S|)\)的暴力是显然的:建出trie树,然后每次把对应的字符串在上边扫,加上对应位置比它小的子树的大小。然后接下来有两种方法。正解首先在线大概是没什么前途的,考虑离线,建出trie树之后在上边dfs,处理挂在每个节点上的询......
  • CF1398E Two Types of Spells 题解 set
    题目链接:https://codeforces.com/problemset/problem/1398/E题目大意你有一个集合,初始为空。有两种类型的元素,一种是普通元素,一种是强化元素,两种元素都有一个数值。有\(n\)次操作,每次操作会往集合中加入一个元素或者删除一个元素。每次操作后,你都需要确定集合中元素的一个......
  • 第十四届蓝桥杯大赛青少组全国总决赛初级组C++C++题解
    第十四届蓝桥杯大赛青少组全国总决赛初级组\(C++\)题解第一题给定一个十进制正整数\(N(1≤N≤10^9)\),请从小到大输出\(1\)~\(N\)之间(含\(1\)和\(N\))所有满足以下要求的数:这个数转换为八进制后是一个回文数;这个数是一个平方数。例如:\(N=20\),在\(1\)~\(20\)之间满足要求......
  • 山东二轮省集题解合集
    山东二轮省集题解合集Day1A打表,发现答案是\(\prod\limits_{i=1}^n(2i-1)\)。证明可以考虑拿GF推。首先有dp,\(f(i,j)\)表示到第\(i\)个括号当前左括号减右括号的个数为\(j\),转移是简单的\(f(i,j)=f(i,j+1)+f(i,j-1)\times(j-1)\)把\(f(i,j)\)写成一个形式幂级......
  • 欢乐结训赛题解
    欢乐结训赛题解A题目链接题目大意给你一个字符串,让你求字符串中最大的字母在字母表中排第几例如codeforces中s的是最大的s在字母表中排19位代码#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+10;constintmod=1e9+7;voidsolve()......
  • 第十二届蓝桥杯c++b组国赛题解(还在持续更新中...)
    试题A:带宽解题思路:由于小蓝家的网络带宽是200Mbps,即200Mb/s,所以一秒钟可以下载200Mb的内容,根据1B=8b的换算规则,所以200Mb=200/8MB=25MB。所以小蓝家的网络理论上每秒钟最多可以从网上下载25MB的内容。代码实现:#include<iostream>#include<algorithm>usingnamespacestd......
  • yarn安装报错网络问题解决方案
    yarn安装报错网络问题解决方案报错为infoThereappearstobetroublewithyournetworkconnection.Retrying...解决方案:更换安装依赖的镜像,使用淘宝镜像安装安装好后更换淘宝镜像yarnconfigsetregistryhttps://registry.npm.taobao.org移除原代理yarn......
  • Java中Collection与Collections有什么区别?Java常见面试题解析
    本文将为大家详细讲解Java中Collection与Collections的区别点,这是我们进行开发时经常用到的知识点,也是大家在学习Java中很重要的一个知识点,更是我们在面试时有可能会问到的问题!文章较长,干货满满,建议大家收藏慢慢学习。文末有本文重点总结,主页有全系列文章分享。技术类问题,欢迎大......
  • [PKUCPC2023] J. Hat Puzzle 题解
    题目链接:http://poj.openjudge.cn/campus2023/J/很荣幸参与了命题。题解的ppt版本在这儿:https://disk.pku.edu.cn:443/link/E4B484E7F3C58A45E9E4FB19C731BF4E.贴一下md版题解,要比ppt版本的简略一些:每个人能够推断出自己帽子颜色的信息,仅有两类:前面的人的帽子情况,以及其......
  • AtCoder Beginner Contest 303 题解 A - E
    A-SimilarString题目大意忽略0和o的差别以及1和l的差别比较两个字符串。解题思路可以硬求,直接写个超长的if判断一下。可以对两个字符串进行修改,0都换成o,1都换成l,然后直接比较两个字符串。ACCode硬求#include<iostream>#include<algorithm>#include<cstring>#i......