主席樹，喵~

稍微總結一下主席樹吧

Too Difficult！搞了一天搞出一大堆怎么令人悲傷的辣雞代碼。總之先總結一下吧，以后碰到這種問題直接拿去毒害隊友好了。

UPD 5/24 茍狗是沙比

一個節點記錄三個信息：lson,rson,sum

用pid表示節點個數。

build

void build(int &k,int l,int r){k=++pid;if(l==r) return;int mid=(l+r)>>1;build(lson[k],l,mid);build(rson[k],mid+1,r);
}

change

void change(int old,int &k,int l,int r,int pos,int x){k=++pid;lson[k]=lson[old],rson[k]=rson[old],sum[k]=sum[old]+x;if(l==r) return;int mid=(l+r)>>1;if(pos<=mid) change(lson[old],lson[k],l,mid,pos,x);else change(rson[old],rson[k],mid+1,r,pos,x);
}

Lv.1 最基本的操作

  • 區間k大值
int query(int old_k,int new_k,int l,int r,int x){if(l==r) return sum[new_k]-sum[old_k]>0?l:-1;int mid=(l+r)>>1;int cntLeft = sum[lson[new_k]]-sum[lson[old_k]];if (cntLeft<x) {return query(rson[old_k],rson[new_k],mid+1,r,x-cntLeft);} else {return query(lson[old_k],lson[new_k],l,mid,x);}
}
  • 區間內有多少個數字小于等于x
int query(int new_k,int old_k,int l,int r,int x) { // cnt <= xif(x<l) return 0; // 這個地方比較喜。小心點。if(l==r) return sum[new_k]-sum[old_k];int mid=(l+r)>>1;if(mid<x) return sum[lson[new_k]]-sum[lson[old_k]]+query(rson[new_k],rson[old_k],mid+1,r,x);else return query(lson[new_k],lson[old_k],l,mid,x);
}
  • 查詢區間<=x的最大數字：上兩條的組合技。

兩道入門題：POJ2104，HDU4417

主席樹相當于對每一個前綴都維護一個線段樹，然后發現相鄰兩棵線段樹長得好像哎！所以我們可以動態開點啦！

解決問題的時候，我們通常會對每一個前綴，維護一個權值線段樹。每個值域存要維護的信息。

既然是維護每一個前綴，所以，我們不僅能拿主席樹來施展線性結構，還能施展樹狀結構！比如說我們可以查詢樹上兩點間路徑點權的k小值。

Lv.2 樹上路徑上點權k小值

栗子：SPOJ-COT

線性結構上

iterval(l,r)=T(r)-T(l-1)

樹狀結構上

path(u,v) = T(u)+T(v)-T(lca)-T(Parent of lca)

Lv.2 矩形內有多少個點

給出很多個點。Q組詢問，每組詢問查詢一個矩形內有幾個點。

按橫坐標排序，把縱坐標放到主席樹上，然后就相當于區間內有多少個數字小于等于x啦！

栗子：CF853C

把細節考慮好！還是很友好的。

#include <iostream>
#include <algorithm>
using namespace std;
const int N=6000000+10;
#define f(x) (1LL*x*(x-1)/2)
typedef long long LL;
int lson[N],rson[N],sum[N],root[N],pid;
int n,q,p[N];
void build(int &k,int l,int r){k=++pid;if(l==r) return;int mid=(l+r)>>1;build(lson[k],l,mid);build(rson[k],mid+1,r);
}
void change(int old,int &k,int l,int r,int pos,int x) {k=++pid;ilson[k]=lson[old],rson[k]=rson[old],sum[k]=sum[old]+x;if(l==r) return;int mid=(l+r)>>1;if(pos<=mid) change(lson[k],lson[k],l,mid,pos,x);else change(rson[k],rson[k],mid+1,r,pos,x);
}
int query(int new_k,int old_k,int l,int r,int x) { // cnt <= xif(x<l) return 0;if(l==r) return sum[new_k]-sum[old_k];int mid=(l+r)>>1;if(mid<x) return sum[lson[new_k]]-sum[lson[old_k]]+query(rson[new_k],rson[old_k],mid+1,r,x);else return query(lson[new_k],lson[old_k],l,mid,x);
}
int count(int x1,int x2,int y1,int y2) { // if(x1>x2||y1>y2) return 0;int cnt1 = query(root[x2],root[x1-1],1,n,y1-1);int cnt2 = query(root[x2],root[x1-1],1,n,y2);return cnt2-cnt1;
} 
int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) {scanf("%d",&p[i]);}build(root[0],1,n);for(int i=1;i<=n;i++) {change(root[i-1],root[i],1,n,p[i],1);}for(int i=1;i<=q;i++){int l,d,r,u;scanf("%d%d%d%d",&l,&d,&r,&u);int LU = count(1,l-1,u+1,n);int LD = count(1,l-1,1,d-1);int RU = count(r+1,n,u+1,n);int RD = count(r+1,n,1,d-1);int L = l-1; int U = n-u; int R = n-r; int D = d-1;LL A = f(L)+f(R)+f(U)+f(D);LL B = f(LU)+f(LD)+f(RU)+f(RD);LL ret = 1LL*n*(n-1)/2-(A-B);printf("%lld\n", ret);}
}

Lv.2 區間內出現數字的個數

權值線段樹直接投降了，不過我們可以在某個元素上一次出現的位置insert -1，在當前出現的位置insert 1

種樹之前想清楚該維護什么啊！

栗子: HDU5919

題解：因為是統計區間內，每個數字第一次出現的位置。

所以我們可以倒著做。從后往前遍歷，遇到一個數字，在這個數字上一次出現的位置加上-1，當前位置加上1.

在從后往前遍歷的同時，我們對于每一個后綴建一棵線段樹。維護后綴中，每個元素第一次出現的位置。

對于每組詢問，先求出區間內有多少種不同的數字，然后查詢第(cnt+1)/2大即可。

#include <iostream>
#include <map>
using namespace std;
const int N = 10000000+10;
int lson[N],rson[N],root[N],sum[N],pid;
int T,cas;void build(int &k,int l,int r) {k=++pid;if(l==r) return;int mid=(l+r)>>1;build(lson[k],l,mid);build(rson[k],mid+1,r);
}
void update(int old,int &k,int l,int r,int pos,int x) {k=++pid; sum[k] = 0;lson[k]=lson[old], rson[k]=rson[old], sum[k]=sum[old]+x;if(l==r) return;int mid=(l+r)>>1;if (pos<=mid) update(lson[old],lson[k],l,mid,pos,x);elseupdate(rson[old],rson[k],mid+1,r,pos,x);
}
int query_x_th(int k,int l,int r,int x) {if (l == r) return l;int mid = (l+r)>>1;if (sum[lson[k]] < x) {return query_x_th(rson[k],mid+1,r,x-sum[lson[k]]);} else {return query_x_th(lson[k],l,mid,x);}
}
int count(int k,int l,int r,int L,int R) {if(L<=l&&r<=R) {return sum[k];}int mid = (l+r)>>1;int ans = 0;if (L<=mid) ans += count(lson[k],l,mid,L,R);if (R >mid) ans += count(rson[k],mid+1,r,L,R);return ans;
}int n, m, a[N];
map<int,int> las;
void init() {las.clear();pid = 0;
}
int main() {scanf("%d",&T);while (T --) {init();scanf("%d %d",&n,&m);for(int i=1;i<=n;i++) {scanf("%d", &a[i]); }build(root[n+1],1,n);for(int i=n;i>=1;i--) {update(root[i+1],root[i],1,n,i,1);if ( las.find(a[i]) != las.end() )update(root[i],root[i],1,n,las[a[i]], -1);las[a[i]] = i;}printf("Case #%d:", ++cas);int ans=0;for(int i=1;i<=m;i++) {int l, r;scanf("%d %d", &l, &r);int nl = min((l+ans)%n+1, (r+ans)%n+1);int nr = max((l+ans)%n+1, (r+ans)%n+1);int tot = count(root[nl],1,n,nl,nr);ans = query_x_th(root[nl],1,n,(tot+1)/2);printf(" %d", ans);}printf("\n");}
}

Lv.3 主席樹的區間更新

一種不用下傳懶惰標記的姿勢：對于區間查詢，從上往下走的時候，對懶惰標記進行累加。

栗子：HDU4348

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N=6000000+10;
int lson[N],rson[N],root[N],pid;
LL sum[N],lazy[N];
int n,q,a[N];void build(int &k,int l,int r){k=++pid; lazy[k] = 0; sum[k] = 0;if(l==r) {sum[k] = a[l];lson[k] = rson[k] = 0;return;}int mid=(l+r)>>1;build(lson[k],l,mid);build(rson[k],mid+1,r);sum[k] = sum[lson[k]] + sum[rson[k]];
}
void update(int old,int &k,int l,int r,int L,int R,int x){k=++pid; lazy[k] = 0; sum[k] = 0;lazy[k]=lazy[old]; sum[k] = sum[old];lson[k]=lson[old]; rson[k]=rson[old];if(L<=l&&r<=R) {lazy[k] = lazy[old] + x;sum[k] = sum[old] + 1LL*(r-l+1)*x;return;}int mid=(l+r)>>1;if (L<=mid)update(lson[k],lson[k],l,mid,L,R,x);if (R >mid)update(rson[k],rson[k],mid+1,r,L,R,x);sum[k] = sum[lson[k]] + sum[rson[k]] + 1LL*lazy[k]*(r-l+1);
}
LL query(int k,int l,int r,int add,int L,int R) {if (L<=l&&r<=R)return sum[k] + 1LL*(r-l+1)*add;add += lazy[k];int mid=(l+r)>>1;LL ans=0;if (L<=mid) ans += query(lson[k],l,mid,add,L,R);if (R >mid) ans += query(rson[k],mid+1,r,add,L,R);return ans;
}
int stamp = 0;
void init() {stamp=0;pid=0;
}
int main(){while (~ scanf("%d%d",&n,&q)) {init();for(int i=1;i<=n;i++) scanf("%d",&a[i]);build(root[0],1,n);int id = 0;for(int i=1;i<=q;i++){char op[2]; int l,r,t;scanf("%s",op);if(op[0] == 'C') {scanf("%d%d%d",&l,&r,&t);update(root[stamp],root[stamp+1],1,n,l,r,t);stamp ++;}if(op[0] == 'Q') {scanf("%d%d",&l,&r);LL ans = query(root[stamp],1,n,0,l,r); printf("%lld\n", ans);}if(op[0] == 'H') { scanf("%d%d%d",&l,&r,&t);LL ans = query(root[t],1,n,0,l,r);printf("%lld\n", ans);}if(op[0] == 'B'){scanf("%d",&t);stamp = t;}}}
}

一些練習

CF650D

題意：動態LIS，每次修改一個位置，每次操作查詢LIS，操作相互獨立

題解：

兩種情況

第一種，更新后pos，出現在了LIS中

我們要做的是：查詢[1,pos)中，h<h[pos]的所有數字，LIS的max

可以對每一個前綴維護一個h的權值線段樹，每個節點記錄h在此值域內LIS的max

第二種，更新后pos，沒出現在LIS中

判斷一下pos是否在存在于所有的，原序列LIS中。

這個地方很有趣。

hint: dp[i]+rev_dp[i]=LIS+1

Bonus:
1. 存在一個LIS包含元素i的條件
2. 所有LIS包含元素i的條件
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;const int N = 400000+10;
const int INF = 1000000007;int bit[N];
vector<int> v;
int id(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
int get(int x) {int ans=0;while(x) {ans=max(ans,bit[x]);x-=x&-x;}return ans;
}
void upd(int pos,int x){while(pos<N) {bit[pos]=max(bit[pos],x);pos += pos&-pos;}
}
int n,m,h[N],dp[N],rdp[N],neccesary[N];
int LIS=0;
vector<int> pos[N];
void compress(int on) {v.clear();if (on == 0) {for(int i=1;i<=n;i++) v.push_back(h[i]);} else {for(int i=1;i<=n;i++) v.push_back(INF-h[i]);}sort(v.begin(), v.end());v.erase(unique(v.begin(),v.end()),v.end());
}
void LIS_Proccess() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) {scanf("%d",&h[i]);}compress(0);for(int i=1;i<=n;i++) {dp[i] = get(id(h[i])-1) + 1;upd(id(h[i]), dp[i]);LIS = max(LIS, dp[i]);}memset(bit,0,sizeof(bit));compress(1);for(int i=n;i>=1;i--) {rdp[i] = get(id(INF-h[i])-1) + 1;upd(id(INF-h[i]), rdp[i]);}for(int i=1;i<=n;i++) {if (dp[i]+rdp[i] == LIS+1) {pos[dp[i]].push_back(i);}}for(int i=1;i<=n;i++) {if (pos[i].size() == 1) {neccesary[pos[i][0]] = 1;}}}int lson[N*22],rson[N*22],val[N*22],root[N*22],pid;
int ans[N], pre[N], suf[N], p[N], x[N];
void build(int &k,int l,int r) {k=++pid; val[k]=0;if(l==r) return;int mid=(l+r)>>1;build(lson[k],l,mid);build(rson[k],mid+1,r);
}
void change(int old,int &k,int l,int r,int pos,int x) {k=++pid;lson[k]=lson[old],rson[k]=rson[old],val[k]=max(x,val[old]);if(l==r) return;int mid=(l+r)>>1;if(pos<=mid) change(lson[old],lson[k],l,mid,pos,x);else change(rson[old],rson[k],mid+1,r,pos,x);
}
int query(int k,int l,int r,int L,int R) {if(L>R) return 0;if(L<=l&&r<=R) {return val[k];}int mid=(l+r)>>1;int ans=0;if (L<=mid) ans=max(ans, query(lson[k],l,mid,L,R));if (R >mid) ans=max(ans, query(rson[k],mid+1,r,L,R));return ans;
}int main() {LIS_Proccess();// neccesary[i]: 第i位一定出現在LIS中pid=0; compress(0);build(root[0],1,v.size());for(int i=1;i<=n;i++) {change(root[i-1],root[i],1,v.size(),id(h[i]),dp[i]);}for(int i=1;i<=m;i++) {scanf("%d%d",&p[i],&x[i]);ans[i] = neccesary[p[i]] ? LIS - 1 : LIS;pre[i] = query(root[p[i]-1], 1, v.size(), 1, id(x[i])-1);}//exit(0);pid=0; compress(1);build(root[n+1],1,v.size());for(int i=n;i>=1;i--) {change(root[i+1],root[i],1,v.size(),id(INF-h[i]),rdp[i]);}for(int i=1;i<=m;i++) {suf[i] = query(root[p[i]+1], 1, v.size(), 1, id(INF-x[i])-1);ans[i] = max(ans[i], pre[i]+suf[i]+1);printf("%d\n", ans[i]);}}

以上，于4/28，mark一下。

之后，待補的坑：

  • BIT套主席樹 【學不會】
  • 主席樹的區間更新【已補】

學數據結構是不可能學數據結構的，這輩子都不可能學數據結構！

轉載于:https://www.cnblogs.com/RUSH-D-CAT/p/8965601.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/254733.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/254733.shtml
英文地址，請注明出處：http://en.pswp.cn/news/254733.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

【轉】小白級的CocoaPods安裝和使用教程

【轉】小白級的CocoaPods安裝和使用教程

原文網址&#xff1a;http://www.jianshu.com/p/e2f65848dddc 百度有很多CocoaPods的安裝教程.第一次看的時候,確實有點摸不透的感覺.經過思考,一步一步來實踐,前后花了三十幾分鐘,才順利使用..所以想了想,我還是寫一個小白級的教程吧.細到每一個細節都說明. 讓你不用10分鐘解決…
閱讀更多...
常見錯誤總結

常見錯誤總結

少打頭文件 少打using namespace std; 命名沖突&#xff0c;全局變量與局部變量命名一致&#xff0c;導致使用的值不是期望值 邊讀邊寫&#xff0c;導致改后讀&#xff0c;覆蓋寫入的值 長整數移位溢出&#xff0c;1<<63是錯誤的&#xff0c;應該寫成1ll<<63 循環變…
閱讀更多...
x264_sps_init

x264_sps_init

x264_sps_init此函數為序列量化集的初始化。主要對結構體x264_sps_t中參數的初始化。 void x264_sps_init( x264_sps_t *sps, int i_id, x264_param_t *param ) { sps->i_id i_id;首先設置序列參數集的ID b_qpprime_y_zero_transform_bypass判斷碼率控制方法是否是恒定質量…
閱讀更多...
系統架構

系統架構

系統架構
閱讀更多...
HALCON相機標定相機內參相機外參

HALCON相機標定相機內參相機外參

目錄相機標定1.相機標定是什么2.怎么使用halcon進行相機內外參標定&#xff1f;&#xff08;1&#xff09;搭建硬件1.**相機連好電腦&#xff0c;用相機廠家軟件打開相機&#xff0c;檢查一下相機是否正常。**2.**接下來使用halcon連接相機**&#xff08;2&#xff09;開始標定…
閱讀更多...
ionic更改端口號

ionic更改端口號

ionic serve -p 8888 —— 重新指定端口號為8888 serve [options] ............................... 啟動本地服務器進行開發測試 dev/testing 　　[--consolelogs|-c] ..................... 輸入app的控制臺到ionic的控制臺顯示 　　[--serverlogs|-s] .....................…
閱讀更多...
angular change the url , prevent reloading

angular change the url , prevent reloading

http://stackoverflow.com/questions/14974271/can-you-change-a-path-without-reloading-the-controller-in-angularjs $location.search({vln: $scope.vln_id}, false);會改變url中 &#xff1f; 后面的 搜索參數&#xff0c;但是controller不會重新實例化。angular 官方文檔…
閱讀更多...
Ubuntu apt-get 更新/查看軟件

Ubuntu apt-get 更新/查看軟件

ubuntu 升級軟件&#xff1a; sudo apt-get update 更新源　　sudo apt-get upgrade 更新已安裝的包　　sudo apt-get dist-upgrade 升級系統 ubuntu升級特定軟件&#xff1a; 可以用 sudo apt-get install pkgname 看軟件安裝位置:dpkg -L xxxx 查看軟件是否安裝&#xff1…
閱讀更多...
X264設定

X264設定

--aq-mode <integer> AQ method [1]- 0: Disabled- 1: Variance AQ (complexity mask)說明&#xff1a;自適應量化方法&#xff0c;可以改善某些場景過于模糊等問題&#xff0c;默認開啟- 0: 關閉- 1: 可變AQ推薦值&#xff1a;默認范例&#xff1a;--aq-mode 1--aq-stre…
閱讀更多...
C#圓形卡尺測量程序基于halcon

C#圓形卡尺測量程序基于halcon

廢話不多說上源碼 覺得帖子有用給點個贊哈 先來個效果圖 下邊的是源碼&#xff0c;自己新建一個文件粘貼進去&#xff0c;包含到您現在的項目 中。這串源碼后邊是使用方法。 using System; using System.Collections.Generic; using System.Linq; using System.Text; usin…
閱讀更多...
MySQL松散索引掃描與緊湊索引掃描

MySQL松散索引掃描與緊湊索引掃描

什么是松散索引&#xff1f; 答&#xff1a;實際上就是當MySQL 完全利用索引掃描來實現GROUP BY 的時候&#xff0c;并不需要掃描所有滿足條件的索引鍵即可完成操作得出結果。 要利用到松散索引掃描實現GROUP BY&#xff0c;需要至少滿足以下幾個條件&#xff1a;◆ GROUP BY 條…
閱讀更多...
算法馬拉松24

算法馬拉松24

算法馬拉松24 A 小C的多邊形 題意&#xff1a;n1個點的多邊形。給外圈的邊標記上1~n&#xff0c;里圈的邊也標記上1~n&#xff0c;使得對于一個外圈相鄰點與中間點構成的三角形的邊權之和都相等。\(n \le 10^6\) 題解&#xff1a;顯然每個三角形權值和為\(\frac{3(n1)}{2}\) 一…
閱讀更多...
HUD2795 線段樹（單點更新）

HUD2795 線段樹（單點更新）

題目中給出的h和w范圍均大&#xff0c;其實n的最大范圍才200000&#xff0c;所以我們建立的線段樹大小為min(h,n),線段樹的每一個節點包含一個變量c&#xff0c;記錄當前區間內還剩下的可以put on的最大長度。插入一個數時&#xff0c;如果該數大于該區間最大值&#xff0c;則返…
閱讀更多...
科維PLC運行時系統ProConOS embedded CLR 2.2 特定應用

科維PLC運行時系統ProConOS embedded CLR 2.2 特定應用

ProConOS embedded CLR是新型的開放式標準化PLC運行時系統&#xff0c;符合IEC 61131標準&#xff0c;可執行不同的自動化任務&#xff08;PLC、PAC、運動控制、CNC、機器人和傳感器&#xff09;。 　　通過采用國際標準的微軟中間語言&#xff08;依據IEC/ISO 23271標準為MSIL…
閱讀更多...
linux下vi命令大全

linux下vi命令大全

進入vi的命令 vi filename :打開或新建文件&#xff0c;并將光標置于第一行首 vi n filename &#xff1a;打開文件&#xff0c;并將光標置于第n行首 vi filename &#xff1a;打開文件&#xff0c;并將光標置于最后一行首 vi /pattern filename&#xff1a;打開文件&…
閱讀更多...
set()與get()詳細解答(C#)

set()與get()詳細解答(C#)

這幾天在搬磚時候用到了set()與get()&#xff0c;同事問了我一些問題&#xff0c;我打算在博客中總結一下。 覺得幫助到了您&#xff0c;幫我點個贊哦。 屬性訪問器 其實說白了就是操作一個屬性&#xff0c;更通俗一點說就是對一個變量的取值與賦值。 先來看get() get 訪問…
閱讀更多...
IM應用中如何計算富文本的高度

IM應用中如何計算富文本的高度

背景 在開發IM的項目過程中&#xff0c;經常會有出現一些需要計算DOM高度&#xff0c;然后超出若干行隱藏等需求。很多時候&#xff0c;需要計算高度的DOM元素都是動態生成的&#xff0c;我們無法在數據渲染前獲取到它的高度。 如果沒有任何交互&#xff0c;我們可以通過CSS來實…
閱讀更多...
G代碼 機器人的CNC實現

G代碼 機器人的CNC實現

&#xfeff;　 控制銑削工作臺和工件的NC程序&#xff0c;通過CAD軟件創建&#xff0c;這些NC程序與特定的機器類型相關。 NC程序在笛卡爾坐標系中動作的描述&#xff0c;對于需要確保一個明確的變換軸位置的關節型的機器人來說&#xff0c;缺少附加的狀態和旋轉信息。傳…
閱讀更多...
IScroll5中文API整理,用法與參考

IScroll5中文API整理,用法與參考

IScroll是移動頁面上被使用的一款仿系統滾動插件。IScroll5相對于之前的IScroll4改進了許多&#xff0c;使得大家可以更方便的定制所需的功能了。 做項目的時候正好用到了這個插件&#xff0c;自己做了一下總結&#xff0c;發在這里方便大家學習IScroll5。 官網&#xff1a;htt…
閱讀更多...
Linux?安裝USB攝像頭

Linux?安裝USB攝像頭

sudo apt-get updatesudo apt-get install fswebcamsudo apt-get install mplayersudo apt-get install alsamixer安裝完畢ls /dev查找設備是否有video0這個設備sudo mplayer tv:// 可以看到攝像內容轉載于:https://www.cnblogs.com/smartkeke/p/6820426.html
閱讀更多...
最新文章

Copyright @ 2022~2023