首先考慮怎么暴力，
考慮把每個數進行 \(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
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/553870.html
標籤：其他
上一篇：AtCoder Beginner Contest 303
下一篇：返回列表