數(shù)據(jù)結構·序列
不要從數(shù)據(jù)結構維護信息的角度來思考問題，而是從問題本身思考需要哪些信息，數(shù)據(jù)結構只是維護信息的工具！！！
可減信息，如區(qū)間和、區(qū)間異或和
直接用前綴和實現(xiàn)，復雜度 O(n)+O(1)+O(n)。
可重復貢獻信息，如區(qū)間最值
如果序列很長，使用線段樹即可，復雜度 O(n)+O(logn)+O(n)。
如果詢問很多，但序列不是特別長，可以用倍增的 RMQ，復雜度 O(nlogn)+O(1)+O(nlogn)。
如果序列很長，詢問也很多，可以對序列線性建立笛卡爾樹轉為 LCA 問題，然后轉為正負 1 RMQ，每 logn分一段打表預處理，復雜度 O(n)+O(1)+O(n)。
僅滿足支持結合律和快速合并，如最大子段和、區(qū)間的串哈希值
一般使用線段樹實現(xiàn)，復雜度 O(n)+O(logn)+O(n)。
2.棧和隊列
2.1.STL
棧stack和隊列queue
雙端隊列deque
2.2.對頂棧（始終在序列中間某個指定位置進行修改）
int l_stack[N],r_stack[N],lidx,ridx;
if(op=='L') if(lidx) r_stack[++ridx]=l_stack[lidx--];
else if(op=='R') if(ridx) l_stack[++lidx]=r_stack[ridx--];
2.3.棧與表達式計算
2.3.1.后綴表達式（逆波蘭式）
- 建立一個存數(shù)的棧，逐一掃描后綴表達式的元素。
I.遇到一個數(shù)：將該數(shù)入棧；
II.遇到一個運算符：取出棧頂?shù)膬蓚€數(shù)計算，再將結果入棧。 - 掃描完成后，棧中恰好剩余1個數(shù)，就是最終答案。
2.3.2.中綴表達式
先將中綴表達式轉后綴表達式：
- 建立一個存運算符的棧，逐一掃描中綴表達式的元素。
I.遇到一個數(shù)：輸出該數(shù)；
II.遇到左括號：將左括號入棧；
III.遇到右括號：不斷取出棧頂并輸出，直至棧頂為左括號，然后將左括號直接出棧（不輸出括號）；
IV.遇到一個運算符：只要棧頂符號的優(yōu)先級不低于當前符號，就不斷取出棧頂并輸出，最后將當前符號入棧。 - 依次取出并輸出棧中所有剩余符號，最終的輸出序列就是轉化的后綴表達式。
再按照《2.3.1.》的方法計算。
- 代碼
//中綴表達式轉后綴表達式
int slen,sidx;
char s[N]; //后綴表達式
bool read_num; //是否正在讀數(shù)字
stack<char> op;
//計算后綴表達式
int num[N],ntop;
inline int prio(char c)//優(yōu)先級
{
if(c=='(') return 0;
if(c=='+' || c=='-') return 1;
if(c=='*' || c=='/') return 2;
}
int main()
{
//中綴表達式轉后綴表達式
char c,read[N];
scanf("%s",read+1);
int rlen=strlen(read+1),ridx=0;
while(ridx+1<=rlen)
{
c=read[++ridx];
if(isdigit(c))
{
read_num=true;
s[++slen]=c;
}
else
{
if(read_num)
{
read_num=false;
s[++slen]=' ';
}
if(c=='(') op.push(c);
else if(c==')')
{
while(op.top()!='(')
{
s[++slen]=op.top();
s[++slen]=' ';
op.pop();
}
op.pop();
}
else if(c=='^') op.push(c); //注意^的優(yōu)先級是最高的，而且^是從右向左結合的
else
{
while(op.size() && prio(op.top())>=prio(c))
{
s[++slen]=op.top();
s[++slen]=' ';
op.pop();
}
op.push(c);
}
}
}
if(read_num)
{
read_num=false;
s[++slen]=' ';
}
while(op.size())
{
s[++slen]=op.top();
s[++slen]=' ';
op.pop();
}
//計算后綴表達式
while(sidx+1<=slen)
{
if(isdigit(s[sidx+1]))
{
int x=0;
c=s[++sidx];
while(isdigit(c)) //最后會把空格吃掉
{
x=x*10+c-'0';
c=s[++sidx];
}
num[++ntop]=x;
}
else if(s[sidx+1]=='+')
{
int x1=num[ntop--],x2=num[ntop--];
num[++ntop]=x2+x1;
sidx+=2; //把空格吃掉
}
else if(s[sidx+1]=='-')
{
int x1=num[ntop--],x2=num[ntop--];
num[++ntop]=x2-x1;
sidx+=2;
}
else if(s[sidx+1]=='*')
{
int x1=num[ntop--],x2=num[ntop--];
num[++ntop]=x2*x1;
sidx+=2;
}
else if(s[sidx+1]=='/')
{
int x1=num[ntop--],x2=num[ntop--];
num[++ntop]=x2/x1;
sidx+=2;
}
else //乘方^
{
int x1=num[ntop--],x2=num[ntop--];
num[++ntop]=pow(x2,x1);
sidx+=2;
}
}
printf("%d\n",num[ntop]);
return 0;
}
2.4.單調性
優(yōu)化狀態(tài)數(shù)至\(O(N)\)。
2.4.1.單調棧（以求每個數(shù)左邊第一個比它小的數(shù)，如果不存在則輸出 ?1為例）
int n,idx,sta[N];
int main(){
cin>>n;
while(n--){
int x;
cin>>x;
while(idx&&sta[idx]>=x) idx--;
if(idx) cout<<sta[idx]<<' ';
else cout<<"-1"<<' ';
sta[++idx]=x;
}
return 0;
}
2.4.2.單調隊列（求各個長度一樣區(qū)間的最值。以滑動窗口為例）
q存的是a的下標。
隊尾插入數(shù)據(jù)，隊頭輸出答案，刪除數(shù)據(jù)可行性隊頭、最優(yōu)性隊尾。
qmin的性質：從隊尾（大）到隊頭（小）單調遞減。
qmax的性質：從隊尾（小）到隊頭（大）單調遞增。
最優(yōu)性、可行性、隊頭計算答案三者的順序應該根據(jù)題意決定：看是誰影響誰。
代碼比較
STL 手寫
deque<int> q; int q[N],hh=0,tt=-1;
!q.empty() hh<=tt
q.push_back() q[++tt]=i;
q.front(),q.back() q[hh],q[tt]
q.pop_front(),q.pop_front(); hh++,tt--;
2.4.2.1.一維單調隊列
int n,k;
int a[N];
deque<int> qmin; //STL
int qmax[N]; //手寫
//q存的是a的下標。隊尾插入數(shù)據(jù)，隊頭輸出答案，刪除數(shù)據(jù)可行性隊頭、最優(yōu)性隊尾。qmin的性質：從隊尾（大）到隊頭（小）單調遞減
//STL
void get_min(){
for(int i=1;i<=n;i++){ //隊尾插入數(shù)據(jù)，隊頭輸出答案，刪除數(shù)據(jù)可行性隊頭、最優(yōu)性隊尾
//可行性
while(!qmin.empty() && qmin.front()<=i-k) qmin.pop_front(); //當滑動窗口滑出隊頭時
//最優(yōu)性
while(!qmin.empty() && a[qmin.back()]>=a[i]) qmin.pop_back(); //當滑動窗口滑進a[i]時，從隊尾向隊頭比a[i]大的數(shù)都沒有用
qmin.push_back(i); //把i放入隊尾，影響后面輸出答案
if(i<k) continue; //當滑動窗口內不含k個數(shù)字時
cout<<a[qmin.front()]<<' '; //q的隊頭一定是答案（因為q從隊尾到隊頭單調遞減，且q的隊頭還在滑動窗口內）
}
return ;
}
//手寫單調隊列
void get_max(){
int hh=0,tt=-1;
for(int i=1;i<=n;i++){
//可行性
while(hh<=tt && qmax[hh]<=i-k) hh++;
//最優(yōu)性
while(hh<=tt && a[qmax[tt]]<=a[i]) tt--;
qmax[++tt]=i;
if(i<k) continue;
printf("%d ",a[qmax[hh]]);
}
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
get_min();
puts("");
get_max();
puts("");
return 0;
}
2.4.2.2.二維單調隊列
有一個 a×b 的整數(shù)組成的矩陣，現(xiàn)請你從中找出一個 n×n 的正方形區(qū)域，使得該區(qū)域所有數(shù)中的最大值和最小值的差最小。
我們可以預處理出每 列 的行中 最值，再對該列求一個 最值，就是該 **子矩陣 **的 最值
該 降維手段，使得一個 二維滑動窗口問題 變成了 n行+n列 的 一維滑動窗口問題
int n,m,k,ans=INF;
int w[N][N];
int row_min[N][N],row_max[N][N];
int q[N];
int a[N],b[N],c[N];
//一維單調隊列
void get_min(int aa[],int bb[],int tot)
{
int hh=0,tt=-1;
for(int i=1;i<=tot;i++)
{
while(hh<=tt && q[hh]<i-k+1) hh++;
while(hh<=tt && aa[q[tt]]>=aa[i]) tt--;
q[++tt]=i;
bb[i]=aa[q[hh]];
}
return ;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&w[i][j]);
for(int i=1;i<=n;i++)
{
get_min(w[i],row_min[i],m);
get_max(w[i],row_max[i],m);
}
for(int j=k;j<=m;j++)
{
for(int i=1;i<=n;i++) a[i]=row_min[i][j];
get_min(a,b,n);
for(int i=1;i<=n;i++) a[i]=row_max[i][j];
get_max(a,c,n);
for(int i=k;i<=n;i++) ans=min(ans,c[i]-b[i]);
}
printf("%d\n",ans);
return 0;
}
3.鏈表
適用條件：在一個數(shù)列中O(1)插入和刪除一個元素。但是隨機訪問元素是O(N)的。
注意在刪除重復的元素時，由于在刪除后該元素的左右鄰居便不會再被維護，因而后續(xù)再刪除該元素有可能導致位置的混亂。因此刪除時要打上標記防止重復刪除。
一種解題思路：先將所有數(shù)插入鏈表，再從后往前刪除。
3.1.單鏈表
主要用于樹和圖的存儲。
《數(shù)據(jù)結構·字符串和圖.鄰接表》
//head：頭結點的下標
//e[i]：節(jié)點i的值
//ne[i]：節(jié)點i的next指針是多少
//siz：頭節(jié)點所在的鏈表的大小
//idx：當前已經(jīng)用到了哪個點
int head,e[N],ne[N],idx;
void init()//初始化
{
head=-1;
idx=0;
}
void add_to_head(int a,int b,int c)//將x插到頭結點
{
e[++idx]=b;
ne[idx]=h[a];
h[a]=idx;
return ;
}
void add_after_k(int k,int x)//將x插到下標是k的點后面
{
e[++idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
return ;
}
void remove(int k)//刪除k的后面的點，k=0表示刪除頭節(jié)點
{
if(!k) head=ne[head];
else ne[k]=ne[ne[k]];
return ;
}
void merge(int x,int y)//將h[x]這條鏈合并到h[y]這條鏈
{
for(int i=h[x];i!=0;i=ne[i])
{
if(ne[i]==0)
{
ne[i]=h[y],h[y]=h[x];
break;
}
}
h[x]=0;
siz[y]+=siz[x],siz[x]=0;
return ;
}
3.2.雙鏈表
主要用于優(yōu)化某些問題。
int m;
int e[N],l[N],r[N],idx;
void init()//初始化
{
r[0]=1,l[1]=0; //0是左端點，1是右端點
idx=1;
return ;
}
void insert(int a,int x)//在節(jié)點a的右邊插入一個數(shù)x
{
e[++idx]=x;
l[idx]=a,r[idx]=r[a];
l[r[a]]=idx,r[a]=idx; //注意這里的順序不可顛倒！！！
return ;
}
void removee(int a)//刪除節(jié)點a
{
l[r[a]]=l[a];
r[l[a]]=r[a];
return ;
}
void print()//從頭到尾輸出雙鏈表
{
for(int i=r[0];i!=1;i=r[i]) printf("%d ",e[i]);
puts("");
return ;
}
int main()
{
scanf("%d",&m);
init();
while(m--)
{
string op;
int k,x;
cin>>op;
if(op=="L")//在鏈表的最左端插入數(shù)x
{
scanf("%d",&x);
// cout<<x<<endl;
insert(0,x);
}
else if(op=="R")//在鏈表的最右端插入數(shù)x
{
scanf("%d",&x);
insert(l[1],x);
}
else if(op=="D")//將第k個插入的數(shù)刪除
{
scanf("%d",&k),k++;
removee(k);
}
else if(op=="IL")//在第k個插入的數(shù)左側插入一個數(shù)
{
scanf("%d%d",&k,&x),k++;
insert(l[k],x);
}
else//在第k個插入的數(shù)右側插入一個數(shù)
{
scanf("%d%d",&k,&x),k++;
insert(k,x);
}
}
print();
return 0;
}
4.堆
適用條件：支持插入、刪除、查詢最值。
4.1.二叉堆
STLpriority_queue
《C++語言.3.2.優(yōu)先隊列priority_queue》
手寫
支持刪除操作。
但是可以被set代替。
//以小根堆為例
//u*2是左兒子，u*2+1是右兒子
int n,m;
int h[N],idx;
int ph[N],hp[N]; //ph：插入操作編號->堆中節(jié)點編號；hp：堆中節(jié)點編號->插入操作編號
void heap_swap(int a,int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
return ;
}
void down(int u)//權值大的往下走
{
int son=u;
if(u*2<=idx && h[u*2]<h[son]) son=u*2;
if(u*2+1<=idx && h[u*2+1]<h[son]) son=u*2+1;
if(u!=son)
{
heap_swap(u,son);
down(son);
}
return ;
}
void up(int u)//權值小往上走
{
while(u/2!=0 && h[u]<h[u/2])
{
heap_swap(u,u/2);
u>>=1;
}
return ;
}
int main()
{
scanf("%d",&n);
while(n--)
{
string op;
int k,x;
cin>>op;
if(op=="I")//插入一個數(shù)x
{
scanf("%d",&x);
idx++;
m++;
ph[m]=idx,hp[idx]=m;
h[idx]=x;
up(idx);
}
else if(op=="PM") printf("%d\n",h[1]);//輸出當前集合中的最小值
else if(op=="DM")//刪除當前集合中的唯一最小值
{
heap_swap(1,idx);
idx--;
down(1);
}
else if(op=="D")//刪除第k個插入的數(shù)
{
scanf("%d",&k);
k=ph[k];
heap_swap(k,idx);
idx--;
up(k),down(k); //二者必選其一
}
else//修改第k個插入的數(shù)，將其變?yōu)閤
{
scanf("%d%d",&k,&x);
k=ph[k];
h[k]=x;
up(k),down(k); //二者必選其一
}
}
return 0;
}
4.2.\(Huffman\)樹
定義
構造一顆包含n個葉子節(jié)點的k叉樹。其中第i個葉子節(jié)點帶有權值\(w_i\)，第i個葉子節(jié)點到根節(jié)點的距離是\(dis_i\)，要求最小化\(\sum(w_i*dis_i)\)。此類問題被稱為k叉\(Huffman\)樹。
int n,k,ans;
priority_queue<int,vector<int>,greater<int> >h;
int main(){
scanf("%d%d",&n,&k);
//插入葉子節(jié)點的權值
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
h.push(x);
}
//補加權值為0的葉子節(jié)點滿足貪心
while((n-1)%(k-1)!=0){
h.push(0);
n++;
}
while(h.size()>1){//直至堆的大小為1（根節(jié)點）
int sum=0;
for(int i=1;i<=k;i++){//取出權值最小的k個權值，加入sum
sum+=h.top();
h.pop();
}
ans+=sum;//\sum(w_i*dis_i)
h.push(sum);//建立一個權值為sum的被取出的k個節(jié)點的父節(jié)點p,把權值sum插入堆中
}
printf("%d\n",ans);
return 0;
}
4.3.左偏樹（可并堆）
int root[N],idx;
struct Heap
{
int l,r;
int val,dis;
}h[N];
int neww(int val)//在集合中插入一個新堆，堆中只包含一個數(shù)x
{
idx++;
h[idx].val=val,h[idx].dis=1;
return idx;
}
int merge(int x,int y)
{
if(x==0 || y==0) return x+y;
if(h[x].val>h[y].val) swap(x,y);//小根堆
h[x].r=merge(h[x].r,y);
if(h[h[x].r].dis>h[h[x].l].dis) swap(h[x].l,h[x].r);
h[x].dis=h[h[x].r].dis+1;
return x;
}
root[i]=merge(root[i],neww(val)); //在堆i中插入一個數(shù)val
root[i]=merge(h[root[i]].l,h[root[i]].r); //彈出堆i的堆頂
h[root[i]].val; //堆i的堆頂
merge(x,y); //合并堆x和堆y
- 當需要得知第x個插入的數(shù)所在的堆時，需要用到并查集
int n;
int idx;
struct Heap
{
int l,r;
int val,dis;
}h[N];
int p[N]; //需要同時維護左偏樹和并查集，他們的節(jié)點一一對應。
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
//當需要得知第x個插入的數(shù)所在的堆，需要用到并查集時，不可以少掉比較函數(shù)！！！
bool cmp(int x,int y)
{
if(h[x].val!=h[y].val) return h[x].val<h[y].val;
return x<y;
}
int merge(int x,int y)
{
if(x==0 || y==0) return x+y;
if(cmp(y,x)) swap(x,y);
h[x].r=merge(h[x].r,y);
if(h[h[x].r].dis>h[h[x].l].dis) swap(h[x].l,h[x].r);
h[x].dis=h[h[x].r].dis+1;
return x;
}
int main()
{
h[0].val=2e9; //防止空節(jié)點的干擾，這里不要忘記！！！
scanf("%d",&n);
while(n--)
{
int t,x,y;
scanf("%d",&t);
if(t==1)//在集合中插入一個新堆，堆中只包含一個數(shù)x
{
scanf("%d",&x);
idx++;
p[idx]=idx;
h[idx].val=x;
h[idx].dis=1;
}
else if(t==2)//將第x個插入的數(shù)和第y個插入的數(shù)所在的小根堆合并
{
scanf("%d%d",&x,&y);
x=find(x),y=find(y);
if(x!=y)
{
if(cmp(y,x)/*如果y比x小*/) swap(x,y);
p[y]=x;
merge(x,y);
//注意：不可以寫成merge(h[x].r,y);應改為h[x].r=merge(h[x].r,y);但這樣不如上面的寫法簡單
}
}
else if(t==3)//輸出第x個插入的數(shù)所在小根堆的最小值
{
scanf("%d",&x);
printf("%d\n",h[find(x)].val);
}
else//刪除第x個插入的數(shù)所在小根堆的一個最小值
{
scanf("%d",&x);
x=find(x);
if(cmp(h[x].r,h[x].l)) swap(h[x].l,h[x].r);
p[x]=p[h[x].l]=h[x].l; //并查集的換根操作
merge(h[x].l,h[x].r);
}
}
return 0;
}
4.4.堆維護中位數(shù)
4.4.1.對頂堆維護中位數(shù)
依次讀入一個整數(shù)序列，每當已讀入的整數(shù)個數(shù)為奇數(shù)時輸出當前的中位數(shù)。
int m,n;
int main()
{
int m,n;
scanf("%d%d",&m,&n);
//初始化
priority_queue<int> hmax;
priority_queue<int,vector<int>,greater<int> > hmin;
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
hmax.push(t);
if(hmin.size() && hmin.top()<hmax.top())
{
auto a=hmin.top(),b=hmax.top();
hmin.pop(),hmax.pop();
hmin.push(b),hmax.push(a);
}
if(hmax.size()>hmin.size()+1)
{
hmin.push(hmax.top());
hmax.pop();
}
if(i&1)
{
printf("%d ",hmax.top());
}
}
return 0;
}
4.4.2.左偏樹維護中位數(shù)
給定一個整數(shù)序列 a1,a2,???,an。
每次可以花費1個單位使\(a_i\)\(+1\)或\(-1\)。把序列a變成嚴格單調的，至少要多少花費？
- 解題思路
-
利用\(a_i'=a_i-i\),\(b_i'=b_i-i\)將嚴格不等→非嚴格不等。
-
在一段\([a_l,a_r]\)中，若只選一個數(shù)b使|al?b|+???+|ar?b| 最小，則b是\([a_l,a_r]\)的中位數(shù)。
考慮兩段的最優(yōu)解\([b_{l1},b_{r1}]\)、\([b_{l2},b_{r2}]\)（兩段的中位數(shù)b1、b2）合并成一段的最優(yōu)解\([b_{l1},b_{r2}]\)：
- 當b1≤b2時
-
--b2--
--b1--
l1 r1 l2 r2
若$[a_{l1},a_{r1}]$的中位數(shù)是b1，$[a_{l2},a_{r2}]$的中位數(shù)是b2，
又因為此時b1、b2滿足非嚴格遞增，
則\([b_{l1},b_{r1}]\)取b1，\([b_{l2},b_{r2}]\)取b2時\(\sum\limits_{i=l1}^{r2}|a_i-b_i|\)結果最小。
2. 當b1>b2時
--b1--
--b2--
l1 r1 l2 r2
若$[a_{l1},a_{r1}]$的中位數(shù)是b1，$[a_{l2},a_{r2}]$的中位數(shù)是b2，
又因為此時b1、b2不滿足非嚴格遞增，
則\([b_{l1},b_{r2}]\)取\([a_{l1},a_{r2}]\)的中位數(shù)時\(\sum\limits_{i=l1}^{r2}|a_i-b_i|\)結果最小。
每次新加一段a（一個點$a_i$），則段a的最優(yōu)解中位數(shù)b就是$a_i$這個數(shù)本身。假定前面已經(jīng)求得$[a_1,a_{i-1}]$最優(yōu)解b，則每一段b段與段之間是單調遞增的。
-
用左偏樹維護中位數(shù)。
用左偏樹維護有序序列的一半，其中左偏樹中最大的數(shù)就是序列的中位數(shù)，即大根堆的根。
初始每個點就是一段，中位數(shù)就是自己。每輪新加一段（一個點），再用cur從后往前合并。
當b1≤b2時，此時b1、b2滿足非嚴格遞增，不用合并。
當b1>b2時，此時b1、b2不滿足非嚴格遞增，需要合并，合并之后的b是\([a_{l1},a_{r2}]\)的中位數(shù)。由前面的性質，新中位數(shù)一定是在兩個有序序列的前一半——仍在左偏樹中：
- 合并時，當兩段的大小至少有一個是偶數(shù)時，中位數(shù)是合并后左偏樹中最大的數(shù)；
- 當兩段的大小全是奇數(shù)時，中位數(shù)是合并后左偏樹中第二大的數(shù)，需要pop掉堆頂。
這就自然滿足了序列的有序并舍棄了有序序列的后一半。
struct Heap
{
int l,r,val,dis;
}h[N];
int top;
struct Segment
{
int rt;
int tot_sum,tot_siz; //整個區(qū)間的信息
int h_sum,h_siz; //左偏樹維護的前半?yún)^(qū)間的信息
int get_cost()
{
int mid=h[rt].val;
return (mid*h_siz-h_sum)+((tot_sum-h_sum)-mid*(tot_siz-h_siz));
}
}st[N];
int merge(int x,int y)
{
if(x==0 || y==0) return x|y;
if(h[x].val<h[y].val) swap(x,y);
h[x].r=merge(h[x].r,y);
if(h[h[x].l].dis<h[h[x].r].dis) swap(h[x].l,h[x].r);
h[x].dis=h[h[x].r].dis+1;
return x;
}
int pop(int x)
{
return merge(h[x].l,h[x].r);
}
int get_cost()
{
int res=0;
top=0;
for(int i=1;i<=n;i++)
{
auto cur=Segment({i,h[i].val,1,h[i].val,1});
h[i].l=h[i].r=0,h[i].dis=1; //初始化
while(top && h[cur.rt].val<h[st[top].rt].val)
{
res-=st[top].get_cost();
bool is_pop=cur.tot_siz%2==1 && st[top].tot_siz%2==1;
cur.rt=merge(cur.rt,st[top].rt);
cur.tot_siz+=st[top].tot_siz;
cur.tot_sum+=st[top].tot_sum;
cur.h_siz+=st[top].h_siz;
cur.h_sum+=st[top].h_sum;
if(is_pop)
{
cur.h_siz--;
cur.h_sum-=h[cur.rt].val;
cur.rt=pop(cur.rt);
}
top--;
}
st[++top]=cur;
res+=cur.get_cost();
}
return res;
}
5.ST表
適用條件：RMQ問題：區(qū)間最值問題。
《基礎算法5.2.倍增》
6.前綴和和差分
關于邊界問題：若邊界上的點不算作答案，則插入一個點(x,y)時令x+=0.5,y+=0.5即x+=1,y+=1處理邊界。
前綴和很適合用樹狀數(shù)組維護。
前綴和思想在很多算法都有涉獵。
多次加減修改區(qū)間，最后詢問值，可以用差分維護。\(e.g.\)《.樹上差分》
將一個數(shù)列差分后，可能會看見它的偽裝，從而解題。
排名關系（\(e.g.\)選手A與選手B排名比他們之間的選手要高，可以在差分序列上令\(d[A_i]\)減1，\(d[B_i]\)加1。最后統(tǒng)計前綴和）可以用差分維護。
6.1.前綴和
6.1.1.一維前綴和（靜態(tài)求區(qū)間和）
int a[100005];
int main(){
int n,m,l,r,x;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>x;
a[i]=a[i-1]+x;
}
while(m--){
cin>>l>>r;
cout<<a[r]-a[l-1]<<endl;
}
return 0;
}
6.1.2.二維前綴和（基于容斥原理）
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum[i][j]=a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];//容斥原理
while(q--)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]);//容斥原理
}
6.1.3.高維前綴和（逐維前綴和）
K維，每維大小為N，則時間復雜度是\(O(K*N^K)\)。
對每個維度都做該維度的前綴和。每個維度做前綴和的先后順序可以任意
二維前綴和
二維前綴和其實也可以對每個維度做該維度的前綴和來實現(xiàn)：\(sum_{i,j}←sum_{i.j-1}\)；\(sum_{i,j}←sum_{i-1,j}\)。
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum[i][j]=a[i][j];
for(int i=1;i<=n;i++)//第i個維度j
for(int j=2;j<=m;j++)//維度j
sum[i][j]+=sum[i][j-1];
for(int j=1;j<=m;j++)//第j個維度i
for(int i=2;i<=n;i++)//維度i
sum[i][j]+=sum[i-1][j];
三維前綴和
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=1;k<=l;k++) sum[i][j][k]=a[i][j][k];
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=2;k<=l;k++) sum[i][j][k]+=sum[i][j][k-1];//第(i,j)個維度k
for(int i=1;i<=n;i++) for(int k=1;k<=l;k++) for(int j=2;j<=m;j++) sum[i][j][k]+=sum[i][j-1][k];//第(i,k)個維度j
for(int j=1;j<=m;j++) for(int k=1;k<=l;k++) for(int i=2;i<=n;i++) sum[i][j][k]+=sum[i-1][j][k];//第(j,k)個維度i
高維前綴和
考慮狀壓。e.g.對于一個三維，每一維大小是n的前綴和\(s_{i,j,k},0≤i,j,k<n\)，就可以把它壓成\(s_{in^2+jn+k}\)。
對于求一個k維，每一維大小是n的前綴和，枚舉每一維i，其實就是枚舉一個\(n^i(0≤i<k)\)，接著在\(0～n^k?1\)范圍內枚舉\(s_j\)，若j在第i維上的值大于0，就可以將\(s_j\)加上\(s_{j?n^i}\)。
int pn[K];//pn[i]=pow(n,i)
for(int i=0;i<k;i++)
for(int j=0;j<pn[k];j++)
if((j/pn[i])%n>0)
sum[j]+=sum[j-pn[i]];
子集和SOS
《數(shù)學...4.1.快速莫比烏斯變換FMT\(O(bit*2^{bit})\)》中的\(FMT_{or}\)，此外子集和對應的差分是\(IFMT_{or}\)，超集和及其對應的差分分別是\(FMT_{and}\)和\(IFMT_{and}\)。
6.2.差分
6.2.1.一維差分（動態(tài)修改（+、-）區(qū)間，修改完后再詢問）
將“區(qū)間操作”轉化為“單點操作”。
原理：差分序列的前綴和是原序列。
定義
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=n;i>=1;i--) a[i]=a[i]-a[i-1];//注意是倒序
6.2.1.1.動態(tài)修改（+、-）區(qū)間，修改完后再詢問
int n,m,l,r,c,a[100005],b[100005];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
while(m--){
cin>>l>>r>>c;
b[l]+=c;
b[r+1]-=c;
}
for(int i=1;i<=n;i++){
b[i]+=b[i-1];
cout<<a[i]+b[i]<<' ';
}
return 0;
}
6.2.2.二階差分
將區(qū)間[l, r] 加上一個首項為s，末項為e，公差為d（若l==r則不存在公差！！！）的等差數(shù)列，求最終數(shù)列。
先考慮使用一次差分\(a_1\)的做法：a[l]+=s，a[l+1~r]+=d，a[r+1]-=e。
發(fā)現(xiàn)需要對一次差分\(a_1\)使用動態(tài)修改（+、-）區(qū)間，因此使用二次差分\(a_2\)維護一次差分\(a_1\)。
對二次差分做兩遍前綴和得到原序列。
n=read(),m=read();
while(m--)
{
int l=read(),r=read();
LL s=read(),e=read();
if(l==r) a[l]+=s,a[l+1]-=s; //特判l(wèi)==r不存在公差！！！
else
{
//先寫出一次差分的式子：a1[l]+=s，a1[l+1~r]+=d，a1[r+1]-=e。
LL d=(e-s)/(r-l);
a[l]+=s,a[l+1]-=s;//a1[l]+=s
a[l+1]+=d,a[r+1]-=d;//a1[l+1~r]+=d
a[r+1]+=-e,a[r+2]-=-e;//a1[r+1]-=e
}
}
//對二次差分做兩遍前綴和得到原序列
for(int i=2;i<=n;i++) a[i]+=a[i-1];
for(int i=2;i<=n;i++) a[i]+=a[i-1];
for(int i=1;i<=n;i++) printf("%lld ",a[i]);
補充
- 動態(tài)維護區(qū)間加等差數(shù)列：因為等差數(shù)列加等差數(shù)列仍然是等差數(shù)列，因此線段樹開懶標記首項a和公差d，表示即將給其兩個兒子構成的整個區(qū)間加上首項為a公差為d的等差數(shù)列。代碼鏈接。
- 區(qū)間給原序列加上一個數(shù)，單點查詢二階前綴和：本質上是維護三階前綴和，可以把原題改為區(qū)間給原序列加上一個數(shù)，區(qū)間查詢一階前綴和，進一步轉化為區(qū)間給原序列加上一個等差數(shù)列，區(qū)間查詢原序列的和。
6.2.3.二維差分
long long n,m,a[1005][1005],q,xx1,xx2,yy1,yy2,c,x;
void insert(int i1,int j1,int i2,int j2,long long xx){
a[i1][j1]+=xx;
a[i2+1][j1]-=xx;
a[i1][j2+1]-=xx;
a[i2+1][j2+1]+=xx;
return ;
}
int main(){
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>x;
insert(i,j,i,j,x);
}
while(q--){
cin>>xx1>>yy1>>xx2>>yy2>>c;
insert(xx1,yy1,xx2,yy2,c);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
cout<<a[i][j]<<' ';
}
if(i==n) continue;
cout<<endl;
}
return 0;
}
7.樹狀數(shù)組
適用條件：維護前綴（或者后綴）的滿足結合律的信息。e.g.前綴和、前綴最值。
千萬小心add(0)或者ask(0)！！！
7.1.樹狀數(shù)組
定義樹狀數(shù)組：定義一個大小為n的類型組。
樹狀數(shù)組儲存前綴信息：add：x→n、ask：x→1。（因為add一個數(shù)只會影響后面的數(shù)）
樹狀數(shù)組儲存后綴信息：add：x→1、ask：x→n。
下面以前綴信息為例。
單點修改\(O(\log n)\)
void add(int x,type val)
{
while(x<=n)
{
/*用val對tr[x]的信息進行單點修改：tr[x]+=val;*/
x+=lowbit(x);
}
return ;
}
前綴查詢\(O(\log n)\)
type ask(int x)
{
type res=0;
while(x)
{
/*把tr[x]的信息合并到res：res+=tr[x];*/
x-=lowbit(x);
}
return res;
}
建樹\(O(n)\)
for(int i=1;i<=n;i++)
{
/*把a[i]的信息合并到tr[i]：tr[i]+=a[i];*/
int j=i+lowbit(i);
if(j<=n) /*把tr[i]的信息合并到tr[j]：tr[j]+=tr[i];*/
}
7.2.樹狀數(shù)組在線求逆序對\(O(n\log n)\)
適用條件：在線統(tǒng)計\(<a_i\)的個數(shù)（樹狀數(shù)組儲存前綴和）或\(>a_i\)的個數(shù)（樹狀數(shù)組儲存后綴和）。
優(yōu)點：可以一邊插入一邊隨時求逆序對。
注意開long long！
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int val)
{
while(x<=n*n)
{
tr[x]+=val;
x+=lowbit(x);
}
return ;
}
LL ask(int x)
{
LL res=0;
while(x)
{
res+=tr[x];
x-=lowbit(x);
}
return res;
}
memset(tr,0,sizeof tr);
LL res=0;
for(int i=n;i>=1;i--)//注意是倒序，或者這里正序而樹狀數(shù)組add:→0、ask→n
{
res+=ask(a[i]-1);
add(a[i],1);
}
printf("%lld\n",res);
- 例題1：給一個序列，給每一對逆序對之間添加一條無向邊，求出這個序列有多少個連通塊。
int t,n,ans;
int a[N],tr[N];
//卡常操作1：
int tim[N], pos[N];
/*每次操作前判斷：
if(tim[i]!=t) tr[i]=0,tim[i]=t;
*/
int lowbit(int x){
return x&-x;
}
void add(int x,int y){
while(x<=n){
if(tim[x]!=t) tr[x]=0,tim[x]=t;
tr[x]+=y;
x+=lowbit(x);
}
return ;
}
int ask(int x){
int res=0;
while(x>0){
if(tim[x]!=t) tr[x]=0,tim[x]=t;
res+=tr[x];
x-=lowbit(x);
}
return res;
}
int main(){
t=read();
while(t--)
{
n=read();
ans=0;
for(int i=1;i<=n;i++)
pos[read()] = i;
for(int i=1;i<=n;i++) {
int p = pos[i];
if (ask(i - 1) == i - 1)
++ans;
add(p, 1);
}
printf("%d\n",ans);
}
return 0;
}
歸并排序求逆序對：《1.2.歸并排序求逆序對》
只能一起求逆序對。
7.3.樹狀數(shù)組維護區(qū)間加減和查詢單點數(shù)值
C l r d：表示把數(shù)列中第l～r個數(shù)都加d。
Q x：表示詢問數(shù)列中第x個數(shù)的值。
樹狀數(shù)組存儲差分，又因為樹狀數(shù)組具有前綴和的性質，二者結合就是原數(shù)。
int n,m;
int a[N],tr[N]; //tr：用樹狀數(shù)組維護前綴和
int lowbit(int x){
return x&-x;
}
void add(int x,int y){
while(x<=n){
tr[x]+=y;
x+=lowbit(x);
}
return ;
}
int ask(int x){
int res=0;
while(x>0){
res+=tr[x];
x-=lowbit(x);
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
while(m--){
char op[2];
scanf("%s",op);
if(*op=='C'){
int l,r,d;
scanf("%d%d%d",&l,&r,&d);
add(l,d);
add(r+1,-d);
}
else{
int x;
scanf("%d",&x);
printf("%d\n",a[x]+ask(x));
}
}
return 0;
}
7.4.樹狀數(shù)組上從1向右/從n向左倍增（動態(tài)查詢數(shù)列小于等于x的最大前綴和）
前提條件：樹狀數(shù)組上倍增只能從1向右倍增或從n向左倍增。
前置知識：倍增靜態(tài)查詢數(shù)列小于等于x的最大前綴和：《基礎算法5.1.序列上的倍增》
C x val：表示把數(shù)列中第x個數(shù)改為val。
Q x：表示詢問最大的res，使得數(shù)列a[1]+a[2]+...+a[res]<=x。
由于樹狀數(shù)組\(tr[]\)本身維護了區(qū)間長度為2的次冪的一些信息，故采用倍增查詢（不需要用到ask函數(shù)，直接用\(tr[]\)倍增跳，可以省下一個\(O(log)\)）。
樹狀數(shù)組存儲原數(shù)。
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
add(i,a[i]);
}
while(q--)
{
char op[2];
cin>>op;
if(op[0]=='C')
{
int x,val;
scanf("%d%d",&x,&val);
//注意是像下面這樣修改
add(x,-a[x]);
add(x,val);
a[x]=val;
}
else
{
int x;
scanf("%d",&x);
int res=0,sum=0;
//利用tr[]倍增跳，不需要用到ask函數(shù)
for(int k=20;k>=0;k--)
{
if(res+(1<<k)<=n && sum+tr[res+(1<<k)]<=x) //注意直接用tr[]，而不是ask
{
sum+=tr[res+(1<<k)]; //注意直接用tr[]，而不是ask
res+=(1<<k);
}
}
cout<<res<<endl;
}
}
7.5.值域樹狀數(shù)組
下面以維護區(qū)間種類數(shù)為例：
7.6.二維樹狀數(shù)組
功能參考于二維前綴和和一維樹狀數(shù)組。
void add(int x,int y,int val)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j))
tr[i][j]+=val;
/*不可以寫成：
while(x<=n)
{
while(y<=m)
{
tr[x][y]+=val;
y+=lowbit(y);
}
x+=lowbit(x);
}
因為對于每一輪的外層循環(huán)，y都要從一開始傳入的值開始
*/
return ;
}
int ask(int x,int y)
{
int res=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
res+=tr[i][j];
return res;
}
8.線段樹
適用條件：維護滿足結合律的信息。動態(tài)開點值域線段樹或者平衡樹能支持插入和刪除。
線段樹空間開4*N！！！
線段樹的節(jié)點數(shù)的上界是4N。
- 信息要滿足結合律才能用線段樹維護。
- 考慮線段樹維護什么信息。
- 維護的區(qū)間；
- 題目中詢問的內容，子樹信息；
- 懶標記；
- 先從query()分析信息是否完全（即當前節(jié)點的信息能否由兒子節(jié)點的信息得到），不可以的話就根據(jù)需要增加其他信息；
- 再從modify()分析信息是否完全（即如何把這個區(qū)間上的每個數(shù)修改后得到整個區(qū)間的信息），不可以的話就根據(jù)需要增加其他信息；
- 最后分析新建的信息在
query()和modify()的角度上是否完全。
- 怎么維護父節(jié)點、合并信息（即
pushup）。 - 如何區(qū)間修改的時候快速維護信息（即
pushdown）。
8.1.線段樹\(O(N\log N)\)
線段樹節(jié)點只關注它的維護的區(qū)間[l,r]內的信息。
修改需要懶標記update_tag 和往下遞歸前pushdown
懶標記：當前節(jié)點的兩個兒子節(jié)點有待更新關于懶標記的信息。
區(qū)間修改時，若修改的區(qū)間包含當前節(jié)點代表的線段樹區(qū)間，則更新當前節(jié)點的信息（給當前節(jié)點的信息執(zhí)行懶標記操作，并給當前節(jié)點加上懶標記表示當前節(jié)點的兩個兒子節(jié)點有待更新信息（不包括這個節(jié)點自身））然后直接返回而不是遞歸到葉子節(jié)點。
作用：區(qū)間修改時保證復雜度是\(O(\log N)\)。因為一個區(qū)間至多被劃分成\(O(\log N)\)個線段樹區(qū)間，如果沒有懶標記而是遞歸到葉子節(jié)點復雜度則是\(O(N)\)！！！
update_tag(u,tag)：更新節(jié)點u關于懶標記tag的信息：先給u的信息執(zhí)行tag操作，再給u的懶標記加上tag。
核心：當前節(jié)點的信息只有在其祖先節(jié)點都沒有懶標記時才是正確的。
pushdown(u)：
用于在往下遞歸前，需要先下傳懶標記更新子節(jié)點信息。
首先，當前節(jié)點信息下傳到子節(jié)點，用當前節(jié)點的懶標記更新兩個兒子結點的信息update_tag(u<<1,tag),update_tag(u<<1|1,tag)。然后，當前節(jié)點的懶標記清空。
遞歸完成返回后pushup
pushup(u)：用于當修改子節(jié)點的信息后返回當前節(jié)點，會影響當前節(jié)點的信息時，需要利用結合律上傳兩個兒子結點的信息更新當前節(jié)點的信息。
更新信息包括修改信息、pushdown、pushup。一個函數(shù)若（查詢函數(shù)）只有pushdown，沒有修改信息，則可以不執(zhí)行pushup。
懶標記操作信息沖突
當兩個操作的發(fā)生沖突相互影響時（\(e.g.\)加法與乘法：先加再乘、先乘再加；增量與覆蓋：先增量再覆蓋、先覆蓋再增量）：
- 先決定pushdown先執(zhí)行什么懶標記操作。（事實上先執(zhí)行隨便一個懶標記都可以寫出對應的代碼，只不過先執(zhí)行某一個懶標記代碼會較簡單）
- 先執(zhí)行的懶標記
update``_tag(u,tag)在給點u加上懶標記tag時，若點u已經(jīng)有后執(zhí)行的懶標記，- 考慮把已經(jīng)有的后執(zhí)行的懶標記轉化為再加上當前的tag之后才有的懶標記（也就是轉化時間順序，保證后執(zhí)行的懶標記在先執(zhí)行的懶標記添加之后才添加）。
- 或者，把當前的tag轉化為后執(zhí)行的懶標記，這樣仍能保證時間順序。
- 其他部分正常代碼。
-
加法與乘法
pushdown先執(zhí)行乘法。
void eval_mul(int u,LL mul)
{
tr[u].sum=tr[u].sum*mul%p;
if(tr[u].add==0) //若沒有后執(zhí)行的懶標記add，則正常代碼
{
tr[u].mul=tr[u].mul*mul%p;
}
else //若已經(jīng)有后執(zhí)行的懶標記add
{
tr[u].add=tr[u].add*mul%p; //把原add的時間順序轉化為在添加當前的mul之后才添加原add
tr[u].mul=tr[u].mul*mul%p; //其他部分正常代碼
}
return ;
}
void eval_add(int u,LL add) //其他部分正常代碼
{
tr[u].sum=(tr[u].sum+add*(tr[u].r-tr[u].l+1)/*別漏了區(qū)間長度*/%p)%p;
tr[u].add=(tr[u].add+add)%p;
return ;
}
void pushdown(int u)
{
if(tr[u].mul!=1) //先執(zhí)行乘法
{
eval_mul(u<<1,tr[u].mul);
eval_mul(u<<1|1,tr[u].mul);
tr[u].mul=1;
}
if(tr[u].add!=0)
{
eval_add(u<<1,tr[u].add);
eval_add(u<<1|1,tr[u].add);
tr[u].add=0;
}
return ;
}
-
增量與覆蓋
pushdown先執(zhí)行增量
void eval_add(int u,int add)
{
tr[u].maxn+=add;
if(tr[u].cov==-INF) //若沒有后執(zhí)行的懶標記cov，則正常代碼
{
tr[u].add+=add;
}
else //若已經(jīng)有后執(zhí)行的懶標記cov
{
//可把add轉化為cov，這樣仍能保證時間順序cov在add之后
tr[u].cov+=add;
}
return ;
}
void eval_cover(int u,int cov) //其他部分正常代碼
{
tr[u].maxn=cov;
tr[u].cov=cov;
return ;
}
void pushdown(int u)
{
if(tr[u].add!=0) //先執(zhí)行增量
{
eval_add(u<<1,tr[u].add);
eval_add(u<<1|1,tr[u].add);
tr[u].add=0;
}
if(tr[u].cov!=-INF)
{
eval_cover(u<<1,tr[u].cov);
eval_cover(u<<1|1,tr[u].cov);
tr[u].cov=-INF;
}
return ;
}
C++代碼
下面以單點修改數(shù)值、區(qū)間加一個數(shù)、區(qū)間乘一個數(shù)、單點查詢數(shù)值、區(qū)間查詢總和為例。
//定義線段樹
struct Segment_tree
{
int l,r;//維護的區(qū)間
ll sum;//題目中詢問的內容，子樹信息
ll add,mul;//懶標記
/*
先從query()分析屬性是否完全（即當前節(jié)點的信息能否由兒子節(jié)點的信息得到），不可以的話就根據(jù)需要增加其他屬性；
再從modify()分析屬性是否完全（即如何把這個區(qū)間上的每個數(shù)修改后得到整個區(qū)間的信息），不可以的話就根據(jù)需要增加其他屬性；
最后分析新建的屬性在query()和modify()的角度上是否完全。
*/
}tr[N*4];
//修改需要懶標記update_tag
//更新節(jié)點u關于懶標記tag的信息
void update_mul(int u,ll mul)//更新節(jié)點u關于懶標記mul的信息：給u的信息執(zhí)行mul操作+給u的懶標記加上mul
{
//先給u的信息執(zhí)行nul操作
tr[u].sum=tr[u].sum*mul%MOD;
//再給u的懶標記加上tag
if(tr[u].add==0)//若沒有后執(zhí)行的懶標記add，則正常代碼
{
tr[u].mul=tr[u].mul*mul%MOD;//注意u的懶標記代表u的兩個兒子節(jié)點有待更新信息（不包含u），所以這里是累積而不是清零！！！
}
else//若已經(jīng)有后執(zhí)行的懶標記add
{
tr[u].add=tr[u].add*mul%MOD;//把原add的時間順序轉化為在添加當前的mul之后才添加原add
tr[u].mul=tr[u].mul*mul%MOD;//其他部分正常代碼
}
return ;
}
void update_add(int u,ll add)//其他部分正常代碼
{
tr[u].sum=(tr[u].sum+add*(tr[u].r-tr[u].l+1)/*別漏了區(qū)間長度*/)%MOD;
tr[u].add=(tr[u].add+add)%MOD;
return ;
}
//往下遞歸前pushdown
void pushdown(int u)
{
if(tr[u].mul!=1)//先執(zhí)行乘法
{
update_mul(u<<1,tr[u].mul);
update_mul(u<<1|1,tr[u].mul);
tr[u].mul=1;
}
if(tr[u].add!=0)
{
update_add(u<<1,tr[u].add);
update_add(u<<1|1,tr[u].add);
tr[u].add=0;
}
return ;
}
//遞歸完成返回后pushup
//簡單的pushup
void pushup(int u)
{
tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%MOD;//由子結點->父節(jié)點
return ;
}
/*復雜的pushup
Segment_tree pushup(Segment_tree v,Segment_tree w)
{
Segment_tree u;
//合并v,w到u
return u;
}
tr[u]=pushup(tr[u<<1],tr[u<<1|1]);
if(l<=mid && r>mid) return pushup(query(u<<1,l,r),query(u<<1|1,l,r));
else if (l<=mid) return query(u<<1,l,r);
else return query(u<<1|1,l,r);
*/
//建樹
void build(int u,int l,int r)
{
tr[u]={l,r,0,0,1/*,……*/};//這里不要忘記！！！
if(l==r)
{
//ll x;cin>>x;
tr[u].sum=x;
//……
return ;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);//當子節(jié)點更新信息后返回當前節(jié)點，且子節(jié)點會影響當前節(jié)點時，需要利用結合律上傳兩個兒子結點的信息更新當前節(jié)點的信息
return ;
}
//單點修改（不需要懶標記）
void change(int u,int x,ll val)
{
if(tr[u].l==tr[u].r)
{
tr[u].sum=val;
//……
return ;
}
pushdown(u);//在往下遞歸前，需要先下傳懶標記更新子節(jié)點信息
int mid=(tr[u].l+tr[u].r)>>1;
if(x<=mid) change(u<<1,x,val);
else change(u<<1|1,x,val);
pushup(u);//當子節(jié)點更新信息后返回當前節(jié)點，且子節(jié)點會影響當前節(jié)點時，需要利用結合律上傳兩個兒子結點的信息更新當前節(jié)點的信息
return ;
}
//區(qū)間修改
void modify(int u,int l,int r,ll mul,ll add)
{
if(l<=tr[u].l && tr[u].r<=r)//若修改的區(qū)間包含當前節(jié)點代表的線段樹區(qū)間，則更新當前節(jié)點的信息，然后直接返回
{
if(add!=0) update_add(u,add);
if(mul!=1) update_mul(u,mul);
return ;
}
pushdown(u);//否則需要繼續(xù)往下遞歸，需要先下傳懶標記更新子節(jié)點信息
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) modify(u<<1,l,r,mul,add);
if(r>mid) modify(u<<1|1,l,r,mul,add);
pushup(u);//當子節(jié)點更新信息后返回當前節(jié)點，且子節(jié)點會影響當前節(jié)點時，需要利用結合律上傳兩個兒子結點的信息更新當前節(jié)點的信息
return ;
}
//單點查詢
ll ask(int u,int x)
{
if(tr[u].l==tr[u].r) return tr[u].sum;
pushdown(u);//在往下遞歸前，需要先下傳懶標記更新子節(jié)點信息
int mid=(tr[u].l+tr[u].r)>>1;
if(x<=mid) return ask(u<<1,x);
else return ask(u<<1|1,x);
//一個函數(shù)（查詢函數(shù)）若只有pushdown，沒有修改信息，則可以不執(zhí)行pushup
}
//區(qū)間查詢
ll query(int u,int l,int r)
{
if(l<=tr[u].l && tr[u].r<=r) return tr[u].sum;//若查詢的區(qū)間包含當前節(jié)點代表的線段樹區(qū)間，則直接返回當前節(jié)點的信息
pushdown(u);//否則需要繼續(xù)往下遞歸，需要先下傳懶標記更新子節(jié)點信息
int mid=(tr[u].l+tr[u].r)>>1;
ll res=0;
if(l<=mid) res=(res+query(u<<1,l,r))%MOD;
if(r>mid) res=(res+query(u<<1|1,l,r))%MOD;
//一個函數(shù)（查詢函數(shù)）若只有pushdown，沒有修改信息，則可以不執(zhí)行pushup
return res%MOD;
}
線段樹性質
- 線段樹遞歸到葉子節(jié)點當且僅當：操作區(qū)間左端點是右葉子節(jié)點，操作區(qū)間右端點是左葉子節(jié)點。
- 對于滿線段樹，兩個葉子結點的 LCA的節(jié)點編號其實就是他們編號的最長公共前綴（二進制下）。
8.2.帶剪枝的暴力修改線段樹
有的題目的區(qū)間詢問不能由當前區(qū)間的信息+懶標記得到（\(e.g.\)模數(shù)的和≠和的模數(shù)、根號的和≠和的根號），這時我們只能暴力修改線段樹（即區(qū)間修改一直修改到葉子節(jié)點），但是可以帶上下面的一個小剪枝，仍然能保證時間復雜度是\(O(log)\)。
- 維護對區(qū)間每個數(shù)取模+查詢區(qū)間和。一個數(shù)在取模過一個小一點的數(shù)后，再取模一個大一點的數(shù)結果仍然不變。因此我們線段樹再維護一個區(qū)間最大值max的信息：當遞歸的區(qū)間的最大值max都小于模數(shù)時，再取模修改就沒有意義了，直接回溯。
- 維護對區(qū)間每個數(shù)開方+查詢區(qū)間和。在int范圍內，一個數(shù)至多6次開方后就變成1了，再開方結果仍然是1。因此我們線段樹再維護一個區(qū)間最大值max的信息：當遞歸的區(qū)間的最大值max都是1時，再開方修改就沒有意義了，直接回溯。
- 維護對區(qū)間每個數(shù)對x取gcd+查詢區(qū)間和。在int范圍內，一個數(shù)至多O(log)次取gcd后就變成1了，再取gcd結果仍然是1。還可以再繼續(xù)剪枝，對x取gcd不會修改區(qū)間內任何一個數(shù)的充要條件是區(qū)間lcm是x的約數(shù)。因此我們線段樹再維護一個區(qū)間lcm的信息：當遞歸的區(qū)間的lcm是x的約數(shù)時，再對x取gcd修改就沒有意義了，直接回溯。
8.3.值域線段樹、動態(tài)開點線段樹和線段樹合并
適用條件：值域上的計數(shù)問題。
統(tǒng)計最值：min/max：最小數(shù)值和最大數(shù)值；cnt：最值的個數(shù)；id：在哪個位置。
一棵維護值域[1,n]的動態(tài)開點線段樹在經(jīng)歷m次單點操作后，空間復雜度為\(O(M\log N)\)。
線段樹合并適用條件：若干棵線段樹維護相同的值域[1,n]，有m次單點操作，每次操作在某一棵線段樹上執(zhí)行，所有操作結束后需要把所有線段樹上對應值域的信息合并。配合動態(tài)開點復雜度是\(O(M\log N)\)。
每棵線段樹：\(lson\)：左兒子的編號（注意不是區(qū)間左端點）；\(rson\)：右兒子的編號；區(qū)間左右端點由函數(shù)中\(l\)和\(r\)決定。
注意：
- 初始的單點修改操作也需要pushup，因為合并時可能這棵線段樹還沒遞歸到葉子節(jié)點，那棵線段樹就已經(jīng)到空節(jié)點了。
- 記得給空節(jié)點（0號節(jié)點）賦初值。\(e.g.\)
tr[0].mi=INF;。否則pushup時如果兒子是空節(jié)點就會出錯！
//動態(tài)開點合并線段樹的變量
int tidx;
int root[N]; //root[i]：點i所對應的線段樹的根是root[i]
struct Tree //區(qū)間左右端點由函數(shù)中l(wèi)和r決定
{
int lson,rson,sum; //lson：左兒子的編號（注意不是區(qū)間左端點）；rson：右兒子的編號；
}tr[N*2*L*2];
void pushup(int u)
{
tr[u].sum=tr[tr[u].lson].sum+tr[tr[u].rson].sum;
return ;
}
//區(qū)間左右端點由函數(shù)中l(wèi)和r決定，以給某個數(shù)加上一個權值為例
void insert(int &u,int l,int r,int x,int val)
{
if(!u) u=++tidx; //動態(tài)開點
if(l==r) //l==r==x
{
tr[u].sum+=val;
return ;
}
int mid=(l+r)>>1;
if(x<=mid) insert(tr[u].lson,l,mid,x,val);
else insert(tr[u].rson,mid+1,r,x,val);
pushup(u);
return ;
}
//保p不保q
void merge(int &p,int &q,int l,int r)
{
if(q==0) return ;
if(p==0)
{
p=q;
return ;
}
if(l==r)
{
tr[p].sum+=tr[q].sum;
return ;
}
int mid=(l+r)>>1;
merge(tr[p].lson,tr[q].lson,l,mid);
merge(tr[p].rson,tr[q].rson,mid+1,r);
pushup(p);
return ;
}
tr[0]={};//記得給空節(jié)點（0號節(jié)點）賦初值。e.g.tr[0].mi=INF。否則pushup時如果兒子是空節(jié)點就會出錯！！！
8.4.掃描線
簡單的掃描線也可以用樹狀數(shù)組維護。
掃描線的本質是維護復雜信息的二維數(shù)點。
8.4.1.面積并
掃描線的特殊性質：
\(1.\)永遠只考慮根節(jié)點信息
-->不需要query函數(shù)
\(2.\)所有操作成對出現(xiàn)，先加后減（永遠大于等于\(0\)）
\(3.\)用線段樹來維護縱坐標的覆蓋區(qū)間，不考慮縱坐標之間的差值，且縱坐標需要離散化
縱坐標建立線段樹
線段樹只是用來維護縱坐標區(qū)間覆蓋問題，只不過掃描線有一些特殊性質使得可以簡化線段樹的寫法。
節(jié)點信息： \(cnt\):覆蓋層數(shù)（計算時只要代表大于\(0\)代表需要加，是多少無所謂） \(len\):不考慮祖先節(jié)點的\(cnt>0\)部分的區(qū)間長
** 注意線段樹單點u維護的是區(qū)間\(**[y_u,y_{u+1}]**\)！！！如果把它寫成一般的值域線段樹單點維護點\(**y_i**\)寫法，就會對[mid,mid+1]的區(qū)間覆蓋長度錯誤計算。**
實現(xiàn)步驟
1.開一個四元結構體儲存每條掃描線的信息，建一個線段樹維護縱坐標區(qū)間覆蓋。
2.輸入數(shù)據(jù)，結構體儲存每條掃描線的信息p[i<<2]={x1,y1,y2,1},p[i<<2+1]={x2,y1,y2,-1};,并對縱坐標y離散化。
3.預處理，對縱坐標y的區(qū)間建線段樹，對結構體按照x的升序排序。
4.掃描線，先求每塊面積=縱坐標的區(qū)間覆蓋長度\(\times\)每2條掃描線之間的距離ans+=tr[1].len*(p[i].x-p[i-1].x);，然后再對縱坐標的區(qū)間覆蓋修改。
不需要pushdown
\(1.\)永遠只考慮根節(jié)點信息
-->query不需要pushdown
\(2.\)所有操作成對出現(xiàn)，先加后減（永遠大于等于\(0\)）
-->減的時候一定在之前加過不會分離任何一個區(qū)間
\((1)\)減完之后大于\(0\)-->不需要，因為大于\(0\)是幾都一樣
\((2)\)減完之后恰好等于\(0\)-->利用兒子來算，兒子沒有改變一定是對的
-->加法：
-->不需要用到子結點，不用pushdown
struct point{
double x,y1,y2;
int k;
}p[N*2]; //儲存每條掃描線的信息
struct tree{
int l,r;
int cnt;
double len;
}tr[N*8]; //線段樹維護區(qū)間覆蓋
int n,m,t;
double ans;
vector<double> y_hash; //y的離散化
//離散化
int Hash(double y){
return lower_bound(y_hash.begin(),y_hash.end(),y)-y_hash.begin(); //返回排名以離散化
}
bool cmp(point q,point w){
return q.x<w.x;
}
void build(int u,int l,int r){
if(l==r){
tr[u]={l,r,0,0};
return ;
}
tr[u]={l,r,0,0};
int mid=(l+r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
return ;
}
void pushup(int u){
//當區(qū)間全被覆蓋時：直接求覆蓋長度
//不能用子節(jié)點間接求覆蓋長度，因為覆蓋標記不會pushdown下傳
if(tr[u].cnt){
tr[u].len=y_hash[tr[u].r+1]-y_hash[tr[u].l]; //tr[u].r+1：因為線段樹單點u維護的是區(qū)間[y_u,y_{u+1}]
return ;
}
//當區(qū)間部分覆蓋時：用子節(jié)點間接求覆蓋長度
if(tr[u].l==tr[u].r) tr[u].len=0; //防止越界：葉子節(jié)點不能繼續(xù)往下訪問
else tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
return ;
}
void modify(int u,int l,int r,int k){
if(l<=tr[u].l && tr[u].r<=r){
tr[u].cnt+=k;
pushup(u);//別忘記這里！！！因為上面一行的代碼導致點u的信息需更新。
return ;
}
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) modify(u<<1,l,r,k);
if(r>mid) modify(u<<1|1,l,r,k);
pushup(u);
return ;
}
int main(){
while(scanf("%d",&n),n){
//初始化
y_hash.clear();
ans=0;
//輸入
for(int i=0;i<n;i++){
double x1,x2,y1,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
p[i*2]={x1,y1,y2,1},p[i*2+1]={x2,y1,y2,-1};
y_hash.push_back(y1),y_hash.push_back(y2);
}
//離散化（排序+去重）
sort(y_hash.begin(),y_hash.end());
y_hash.erase(unique(y_hash.begin(),y_hash.end()),y_hash.end());
//預處理
m=y_hash.size();
build(1,0,m-2); //m-2：0~m-1的點共有m-2個區(qū)間[y_u,y_{u+1}]
sort(p,p+n*2,cmp); //p+n*2：對0~n*2-1的n*2條掃描線排序
//掃描線
int i=0;
while(i<n*2){
if(i) ans+=tr[1].len*(p[i].x-p[i-1].x);
double backup=p[i].x;
while(i<n*2 && p[i].x==backup)
{
modify(1,Hash(p[i].y1),Hash(p[i].y2)-1,p[i].k); //Hash(p[i].y2)-1：因為線段樹單點u維護的是區(qū)間[y_u,y_{u+1}]，Hash(p[i].y2)作為一個區(qū)間的右端點，故要修改到線段樹上點Hash(p[i].y2)-1
i++;
}
}
printf("Test case #%d\n",++t);
printf("Total explored area: %.2lf\n\n",ans);
}
return 0;
}
8.4.2.格點覆蓋
struct point{
ll x,y1,y2,c;
}p[N*2];
struct tree{
int l,r;
ll max,add;
}tr[N*8];
int n;
ll w,h,ans;
vector<ll> y_hash;
int Hash(ll y){
return lower_bound(y_hash.begin(),y_hash.end(),y)-y_hash.begin();
}
bool cmp(point q,point w){
if(q.x!=w.x) return q.x<w.x;
return q.c>w.c;
}
void build(int u,int l,int r){
if(l==r){
tr[u]={l,r,0,0};
return ;
}
tr[u]={l,r,0,0};
int mid=(l+r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
return ;
}
void pushup(int u){
tr[u].max=max(tr[u<<1].max,tr[u<<1|1].max);
return ;
}
void pushdown(int u){
tr[u<<1].max+=tr[u].add;
tr[u<<1|1].max+=tr[u].add;
tr[u<<1].add+=tr[u].add;
tr[u<<1|1].add+=tr[u].add;
tr[u].add=0;
return ;
}
void modify(int u,int l,int r,ll c){
if(l<=tr[u].l && tr[u].r<=r){
tr[u].max+=c;
tr[u].add+=c;
return ;
}
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) modify(u<<1,l,r,c);
if(r>mid) modify(u<<1|1,l,r,c);
pushup(u);
return ;
}
int main(){
while(cin>>n>>w>>h){ //scanf是lj好吧
y_hash.clear();
ans=0;
for(int i=0;i<n;i++){
ll x,y,c;
scanf("%lld%lld%lld",&x,&y,&c);
p[i*2]={x,y,y+h-1,c},p[i*2+1]={x+w-1,y,y+h-1,-c};
y_hash.push_back(y),y_hash.push_back(y+h-1);
}
sort(y_hash.begin(),y_hash.end());
y_hash.erase(unique(y_hash.begin(),y_hash.end()),y_hash.end());
build(1,0,y_hash.size()-2);
sort(p,p+n*2,cmp);
for(int i=0;i<n*2;i++){
modify(1,Hash(p[i].y1),Hash(p[i].y2),p[i].c);
ans=max(ans,tr[1].max);
}
printf("%lld\n",ans);
}
return 0;
}
8.4.3.區(qū)間子區(qū)間問題
適用條件：給定L,R，求L≤l≤r≤R的合法區(qū)間[l,r]數(shù)量。
把原問題轉化為二維問題：l一維，r一維。區(qū)間[l,r]相當于平面上的一個點，L≤l≤r≤R的區(qū)間[l,r]相當于平面上的圖形。
一般還需要結合前驅后繼、拆貢獻等技巧。
8.5.區(qū)間最值修改操作和區(qū)間歷史最值查詢操作（Segment Tree Beats，吉司機線段樹）
8.5.1.區(qū)間最值修改操作
區(qū)間最值修改操作：給定l,r,x，對于i∈[l,r]，令A_i←min/max(A_i,x)。
核心是數(shù)域的劃分。
下面以min為例。
8.5.1.1.修改操作只有區(qū)間最值修改操作\(O(Q\log N)\)
線段樹節(jié)點u維護區(qū)間最大值tr[u].ma、區(qū)間最大值的個數(shù)tr[u].mac、區(qū)間嚴格次大值tr[u].sma、區(qū)間針對最大值的加操作的懶標記tr[u].madd和查詢操作所需的信息。
對于一次區(qū)間最小值修改操作l,r,x：
- 若x≥tr[u].ma，則直接返回。
- 若tr[u].sma<x<tr[u].ma，則
update_madd(u,-tr[u].ma+x);，返回。 - 若x≤tr[u].sma，往下遞歸到左右子樹，返回時合并信息。
使用勢能分析可以證明時間復雜度為\(O(Q\log N)\)。
8.5.1.2.區(qū)間最值修改操作和其他修改操作\(O(Q\log^2N)\)
區(qū)間加操作
線段樹節(jié)點再額外維護區(qū)間針對非最大值的加操作的懶標記tr[u].oadd。
對于一次區(qū)間最值修改操作，代碼不變。對于一次區(qū)間加操作l,r,x，像普通線段樹一樣，只不過同時執(zhí)行update_oadd(u,x)和update_madd(u,x);。注意處理懶標記操作信息沖突。
基于對標記的分析可以證明時間復雜度是\(O(Q\log^2N)\)。
其他修改操作
嘗試能不能轉化為區(qū)間最值修改操作和區(qū)間加操作。e.g.區(qū)間覆蓋操作l,r,x等于先區(qū)間加操作l,r,+∞再區(qū)間最小值修改操作l,r,x。
8.5.2.區(qū)間歷史最值查詢操作
形式化地，定義一個輔助數(shù)組B，一開始與A完全相同。在A的每次操作后，我們對整個數(shù)組取max：\(\forall i\in [1,n] , B_i=\max(B_i,A_i)\)。此時，\(B_i\)稱作這個位置i的歷史最大值。
如果只維護一個歷史最大值的信息，那么對于操作序列“先[1,n]區(qū)間+1，再[1,n]區(qū)間-1，最后詢問[6,6]的歷史最大值”就會得到錯誤的答案0。因為區(qū)間修改的信息為保證復雜度沒有下傳。
歷史最值版本的信息包含當前版本的信息。
歷史最值的前提是保證該歷史時間點前所有的操作都執(zhí)行。
難點在于pushdown中梳理歷史最值版本的信息和當前版本的信息。
- 對于每個信息（包括懶標記），都新開一個歷史最值的信息（\(e.g.\)hmaxn是當前區(qū)間的最大值maxn的歷史最值版本：當前區(qū)間的歷史最大值）。
- 給當前節(jié)點增加懶標記時：
- 如果當前懶標記是覆蓋操作：
void cover(int u,int cov,int hcov)
{
tr[u].hmaxn=max(tr[u].hmaxn,hcov);
tr[u].maxn=cov;
tr[u].hcov=max(tr[u].hcov,hcov);
tr[u].cov=cov;
return ;
}
- 如果當前懶標記是增量操作：
void added(int u,int add,int hadd)
{
tr[u].hmaxn=max(tr[u].hmaxn,tr[u].maxn+hadd); //此時的tr[u].maxn是加入懶標記更新之前的最大值，時間上是連續(xù)合法的。因為歷史最值的前提是保證該歷史時間點前所有的操作都執(zhí)行，所以不是tr[u].hmaxn+hadd，否則某些操作缺失，時間不連續(xù)合法
tr[u].maxn+=add; //然后再更新當前版本的信息
tr[u].hadd=max(tr[u].hadd,tr[u].add+hadd);
tr[u].add+=add;
return ;
}
- 其他部分正常線段樹代碼
void pushdown(int u)
{
if(tr[u].add!=0 || tr[u].hadd!=0)
{
added(u<<1,tr[u].add,tr[u].hadd);
added(u<<1|1,tr[u].add,tr[u].hadd);
tr[u].add=tr[u].hadd=0;
}
if(tr[u].cov!=-INF || tr[u].hcov!=-INF)
{
cover(u<<1,tr[u].cov,tr[u].hcov);
cover(u<<1|1,tr[u].cov,tr[u].hcov);
tr[u].cov=tr[u].hcov=-INF;
}
return ;
}
void pushup(int u)
{
tr[u].maxn=max(tr[u<<1].maxn,tr[u<<1|1].maxn);
tr[u].hmaxn=max(tr[u<<1].hmaxn,tr[u<<1|1].hmaxn); //！！！
return ;
}
int query_hmax(int u,int l,int r)
{
if(l<=tr[u].l && tr[u].r<=r) return tr[u].hmaxn;
}
void modify(int u,int l,int r,int add,int cov)
{
if(l<=tr[u].l && tr[u].r<=r)
{
if(add!=0) added(u,add,add);
if(cov!=-INF) cover(u,cov,cov);
return ;
}
}
8.5.3.區(qū)間最值修改操作、區(qū)間歷史最值查詢操作和其他操作\(O(Q\log^2 N)\)
結合所學知識即可。
以下面這道題目為例：
給出一個長度為 \(n\) 的數(shù)列 \(A\)，同時定義一個輔助數(shù)組 \(B\)，\(B\) 開始與 \(A\) 完全相同。接下來進行了 \(q\) 次操作，操作有五種類型，按以下格式給出：
1 l r add：對于所有的 \(i\in[l,r]\)，將 \(A_i\) 加上 \(add\)（\(add\) 可以為負數(shù)）。2 l r mi：對于所有的 \(i\in[l,r]\)，將 \(A_i\) 變成 \(\min(A_i,mi)\)。3 l r：求 \(\sum_{i=l}^{r}A_i\)。4 l r：對于所有的 \(i\in[l,r]\)，求 \(A_i\) 的最大值。5 l r：對于所有的 \(i\in[l,r]\)，求 \(B_i\) 的最大值。
在每一次操作后，我們都進行一次更新，讓 \(B_i\gets\max(B_i,A_i)\)。
int n,q;
ll a[N];
struct Segment_tree
{
int l,r;
ll sum;
ll ma,mac,hma,sma;
ll madd,hmadd,oadd,hoadd;
}tr[N*4];
void update(int u,ll madd,ll hmadd,ll oadd,ll hoadd)
{
tr[u].sum+=madd*tr[u].mac+oadd*(tr[u].r-tr[u].l+1-tr[u].mac);
tr[u].hma=max(tr[u].hma,tr[u].ma+hmadd);
tr[u].hmadd=max(tr[u].hmadd,tr[u].madd+hmadd);
tr[u].ma+=madd;
tr[u].madd+=madd;
tr[u].hoadd=max(tr[u].hoadd,tr[u].oadd+hoadd);
if(tr[u].sma!=-INF) tr[u].sma+=oadd;
tr[u].oadd+=oadd;
return ;
}
void pushdown(int u)
{
ll ma=max(tr[u<<1].ma,tr[u<<1|1].ma);
if(tr[u<<1].ma==ma) update(u<<1,tr[u].madd,tr[u].hmadd,tr[u].oadd,tr[u].hoadd);
else update(u<<1,tr[u].oadd,tr[u].hoadd,tr[u].oadd,tr[u].hoadd);
if(tr[u<<1|1].ma==ma) update(u<<1|1,tr[u].madd,tr[u].hmadd,tr[u].oadd,tr[u].hoadd);
else update(u<<1|1,tr[u].oadd,tr[u].hoadd,tr[u].oadd,tr[u].hoadd);
tr[u].madd=tr[u].hmadd=tr[u].oadd=tr[u].hoadd=0;
return ;
}
void pushup(int u)
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
tr[u].ma=max(tr[u<<1].ma,tr[u<<1|1].ma);
tr[u].hma=max(tr[u<<1].hma,tr[u<<1|1].hma);
tr[u].sma=-INF,tr[u].mac=0;
if(tr[u<<1].ma==tr[u].ma)
{
tr[u].sma=max(tr[u].sma,tr[u<<1].sma);
tr[u].mac+=tr[u<<1].mac;
}
else tr[u].sma=max(tr[u].sma,tr[u<<1].ma);
if(tr[u<<1|1].ma==tr[u].ma)
{
tr[u].sma=max(tr[u].sma,tr[u<<1|1].sma);
tr[u].mac+=tr[u<<1|1].mac;
}
else tr[u].sma=max(tr[u].sma,tr[u<<1|1].ma);
return ;
}
void build(int u,int l,int r)
{
tr[u].l=l,tr[u].r=r;
tr[u].madd=tr[u].hmadd=tr[u].oadd=tr[u].hoadd=0;
if(l==r)
{
tr[u].sum=tr[u].ma=tr[u].hma=a[l];
tr[u].mac=1;
tr[u].sma=-INF;
return ;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
return ;
}
void modify_add(int u,int l,int r,ll add)
{
if(l<=tr[u].l && tr[u].r<=r)
{
update(u,add,add,add,add);
return ;
}
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) modify_add(u<<1,l,r,add);
if(r>mid) modify_add(u<<1|1,l,r,add);
pushup(u);
return ;
}
void modify_mi(int u,int l,int r,ll mi)
{
if(mi>=tr[u].ma) return ;
if(l<=tr[u].l && tr[u].r<=r && mi>tr[u].sma)
{
update(u,-tr[u].ma+mi,-tr[u].ma+mi,0,0);
return ;
}
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) modify_mi(u<<1,l,r,mi);
if(r>mid) modify_mi(u<<1|1,l,r,mi);
pushup(u);
return ;
}
ll query_sum(int u,int l,int r)
{
if(l<=tr[u].l && tr[u].r<=r) return tr[u].sum;
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
ll res=0;
if(l<=mid) res+=query_sum(u<<1,l,r);
if(r>mid) res+=query_sum(u<<1|1,l,r);
return res;
}
ll query_ma(int u,int l,int r)
{
if(l<=tr[u].l && tr[u].r<=r) return tr[u].ma;
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
ll res=-INF;
if(l<=mid) res=max(res,query_ma(u<<1,l,r));
if(r>mid) res=max(res,query_ma(u<<1|1,l,r));
return res;
}
ll query_hma(int u,int l,int r)
{
if(l<=tr[u].l && tr[u].r<=r) return tr[u].hma;
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
ll res=-INF;
if(l<=mid) res=max(res,query_hma(u<<1,l,r));
if(r>mid) res=max(res,query_hma(u<<1|1,l,r));
return res;
}
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while(q--)
{
int o,l,r;
cin>>o>>l>>r;
if(o==1)
{
ll add;
cin>>add;
modify_add(1,l,r,add);
}
else if(o==2)
{
ll mi;
cin>>mi;
modify_mi(1,l,r,mi);
}
else if(o==3) cout<<query_sum(1,l,r)<<'\n';
else if(o==4) cout<<query_ma(1,l,r)<<'\n';
else cout<<query_hma(1,l,r)<<'\n';
}
8.6.貓樹
適用條件：滿足結合律且支持快速合并且大小與區(qū)間長度無關的信息，快速查詢不修改。
下面以區(qū)間最大子段和為例。
\(O(N\log N)\)預處理
-
首先將 1~n 整個區(qū)間分成兩份 1~mid ，mid+1~n。
-
然后對于這兩個區(qū)間，我們先從中間點 mid 和 mid+1 出發(fā)，O(n) 地向兩邊遍歷區(qū)間中的每個元素，同時維護要處理的信息。
對于左邊的區(qū)間，i 倒序遍歷， f[i]=f[i+1]+a[i]
對于右邊的區(qū)間，i 正序遍歷， f[i]=f[i?1]+a[i] -
等兩個區(qū)間都處理完之后，我們再將兩個區(qū)間繼續(xù)分下去。重復迭代以上步驟直到區(qū)間左右邊界重合（即 l == r ）時，記錄位置l對應的葉子結點編號，直接返回。
\(O(1)\)查詢
某個預處理過的區(qū)間 可以將任意一個左右端點都在該區(qū)間內，且經(jīng)過該區(qū)間中點（\(O(\log N)\)尋找分割點）的區(qū)間分成兩份，而這兩份區(qū)間已經(jīng)處理過了，那么就可以 O(1)合并求解。
O(1)尋找分割點：如果讓兩個點從葉子結點不斷向上走直到相遇，那么該區(qū)間的中間點就是它們的分割點——LCA，\(O(\log \log n)\)。
還可以繼續(xù)優(yōu)化：我們觀察一下就可以發(fā)現(xiàn)，對于滿線段樹（因此數(shù)組大小應為\(2^k+10\)****！！！），兩個葉子結點的 LCA的節(jié)點編號其實就是他們編號的最長公共前綴（二進制下）。我們將兩個數(shù)異或之后可以發(fā)現(xiàn)他們的公共前綴不見了，即最高位的位置后移了\(\log LCA.len\)（LCA 節(jié)點在二進制下的長度），即LCA 所在的層。 我們將長度相同的區(qū)間放在一維數(shù)組里了啊，那么我們又知道這兩個區(qū)間的左右邊界，中間點又是確定的，當然可以在該層中得到我們想要的信息并快速合并起來了。
特殊處理區(qū)間左右邊界重合的詢問。
注意數(shù)組大小應為\(2^k+10\)！！！
const int N=(1<<17)+10;//**注意數(shù)組大小應為2^k+10！！！**
int n,m,len=2;
int a[N];
int lg[N*4],id[N],s1[17][N],s2[17][N];//lg[i]：log2(i)；id[i]：位置i對應的葉子結點編號s1[depth][i]：第depth層區(qū)間i和mid的最大子段和（包含端點mid）；s2[depth][i]：（不包含端點mid）
void build(int u,int depth,int l,int r)
{
//到達葉子節(jié)點
if(l==r)
{
id[l]=u;//記錄位置l對應的葉子結點編號
return ;
}
//處理左半部分
int mid=(l+r)>>1,sum1,sum2;
s1[depth][mid]=a[mid];
s2[depth][mid]=a[mid];
sum1=a[mid],sum2=max(a[mid],0);
for(int i=mid-1;i>=l;i--)
{
sum1+=a[i],sum2+=a[i];
s1[depth][i]=max(s1[depth][i+1],sum1);
s2[depth][i]=max(s2[depth][i+1],sum2);
sum2=max(sum2,0);
}
//處理右半部分
s1[depth][mid+1]=a[mid+1];
s2[depth][mid+1]=a[mid+1];
sum1=a[mid+1],sum2=max(a[mid+1],0);
for(int i=mid+2;i<=r;i++)
{
sum1+=a[i],sum2+=a[i];
s1[depth][i]=max(s1[depth][i-1],sum1);
s2[depth][i]=max(s2[depth][i-1],sum2);
sum2=max(sum2,0);
}
//向下遞歸
build(u<<1,depth+1,l,mid);
build(u<<1|1,depth+1,mid+1,r);
return ;
}
int query(int l,int r)
{
if(l==r) return a[l];
int depth=lg[id[l]]-lg[id[l]^id[r]];//得到lca所在的層
return max(s1[depth][l]+s1[depth][r],max(s2[depth][l],s2[depth][r]));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
while(len<n) len<<=1;
for(int i=2;i<=len<<2;i++) lg[i]=lg[i>>1]+1;
build(1,1,1,len);
scanf("%d",&m);
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",query(l,r));
}
return 0;
}
應用
-
區(qū)間詢問dp
多個詢問[l,r]，需從l出發(fā)dp求得f[(l~)r]回答詢問。
設從f[i+1(mid)]轉移到f[i(mid)]的復雜度為a，由f[l(mid)]和f[(mid+1)r]回答詢問的復雜度為b，則總的復雜度為\(O((N\log N)a+Qb)\)，并且可以做到在線回答。
若卡空間，則采用離線貓樹分治寫法，空間復雜度為單獨dp的空間復雜度\(O(Na)\)。
8.7.李超線段樹
適用條件：動態(tài)維護整個平面上的斜率確定的直線或線段，或形如\(\min \{ kx+b \},(k是定值)\)。
8.7.1.李超線段樹
值域線段樹維護每個區(qū)間的最優(yōu)線段，使縮小答案候選集合。
稱一條線段在\(x=x_0\)處最優(yōu)，當且僅當該線段在\(x_0\)處是所有線段中取值最小的線段。
稱一條線段能成為區(qū)間\([l,r]\)中的 最優(yōu)線段，當且僅當：
- 該線段的定義域完整覆蓋了區(qū)間\([l,r]\)；
- 該線段在區(qū)間中點處最優(yōu)。
-
平面內插入一條全局直線
change()\(O(\log N)\)這里的“全局”廣義上定義為完全覆蓋當前區(qū)間的線。
- 若當前區(qū)間內沒有任何線段，則直接將新線段放入當前區(qū)間，返回。
若新線段完全覆蓋當前區(qū)間的線段，則直接將新線段替換當前區(qū)間的線段，返回。
若當前區(qū)間的線段完全覆蓋新線段，則直接返回。
上面三種情況還同時額外處理了新舊線段斜率相同、到達葉子結點的情況。 - 設該區(qū)間的中點為 mid，我們拿新線段 f 在中點處的值與原最優(yōu)線段 g 在中點處的值作比較。
- 首先，如果新線段 f 斜率大于原線段 g，
-
如果 f 在 mid 處更優(yōu)，則 f 在右半?yún)^(qū)間 一定 最優(yōu)，g 在左半?yún)^(qū)間 可能 最優(yōu)；
![]()
-
反之，g 在左半?yún)^(qū)間 一定 最優(yōu)，f 在右半?yún)^(qū)間 可能 最優(yōu)。
![]()
-
- 接下來考慮 f 斜率小于 g 的情況，
-
如果 f 在 mid 處更優(yōu)，則 f 在左半?yún)^(qū)間 一定 最優(yōu)，g 在右半?yún)^(qū)間 可能 最優(yōu)；
![]()
-
反之，g 在右半?yún)^(qū)間 一定 最優(yōu)，f 在左半?yún)^(qū)間 可能 最優(yōu)。
![]()
-
- 首先，如果新線段 f 斜率大于原線段 g，
- 最后考慮新線段和舊線段斜率相同的情況，這種情況已經(jīng)被情況1處理了。
- 確定完當前區(qū)間的最優(yōu)線段后，我們需要遞歸進入子區(qū)間，更新最優(yōu)線段可能改變的區(qū)間。
這樣的過程與一般線段樹的遞歸過程類似，因此我們可以使用線段樹來維護。
- 若當前區(qū)間內沒有任何線段，則直接將新線段放入當前區(qū)間，返回。
-
平面內插入一條區(qū)間線段
modify()\(O(\log^2 N)\)相當于把一條線段分成\(O(\log N)\)的區(qū)間，使線段能完全覆蓋這些區(qū)間，然后讓這些區(qū)間按照《全局插入一條直線》的方法往下遞歸\(O(\log N)\)層。
-
單點\(x=x_0\)查詢最值
ask()\(O(\log N)\)利用了標記永久化的思想，簡單地說，我們將所有包含 \(x_0\) 區(qū)間（易知這樣的區(qū)間只有 \(O(\log n)\) 個）的最優(yōu)線段拿出來，在這些線段中比較，從而得出最優(yōu)線段。
-
區(qū)間\([x_l,x_r]\)查詢最值
query()\(O(\log N)\)李超線段樹多維護一個最值變量max/min：平面上直線在當前區(qū)間的最值，在
change()函數(shù)中更新信息tr[u].min=min(tr[u].min,min(calc(id,tr[u].l),calc(id,tr[u].r))/*最值一定是線段的兩端點*/);，在change()和modify()函數(shù)中執(zhí)行pushup()函數(shù)。然后像普通線段樹那樣查詢區(qū)間最值。
const int N=1e5+10,T=5e4+10,INF=1e9;
int n;
int idx;
double k[N],b[N];
struct Lc
{
int l,r;
int tag; //儲存當前區(qū)間的最優(yōu)線段
double min; //平面上直線在當前區(qū)間的最值
}tr[N*4];
double calc(int tag,int x)
{
if(!tag) return INF;//注意初始化
return k[tag]*x+b[tag];
}
void build(int u,int l,int r)
{
tr[u]={l,r};
tr[u].min=INF; //注意初始化
if(l>=r) return ;
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
return ;
}
void pushup(int u)
{
tr[u].min=min(tr[u].min,min(tr[u<<1].min,tr[u<<1|1].min));
return ;
}
void change(int u,int tag)
{
if(!tr[u].tag)//注意初始化
{
tr[u].tag=tag;
tr[u].min=min(tr[u].min,min(calc(tag,tr[u].l),calc(tag,tr[u].r))/*最值一定是線段的兩端點*/); //別忘記更新！！！
return ;
}
if(calc(tag,tr[u].l)<calc(tr[u].tag,tr[u].l) && calc(tag,tr[u].r)<calc(tr[u].tag,tr[u].r))
{
tr[u].tag=tag;
tr[u].min=min(tr[u].min,min(calc(tag,tr[u].l),calc(tag,tr[u].r))); //別忘記更新！！！
return ;
}
if(calc(tag,tr[u].l)>=calc(tr[u].tag,tr[u].l) && calc(tag,tr[u].r)>=calc(tr[u].tag,tr[u].r)) return ; //注意要取等號（或在上面取也可以）！！！
int mid=(tr[u].l+tr[u].r)>>1;
if(k[tag]>k[tr[u].tag])
{
if(calc(tag,mid)<calc(tr[u].tag,mid))
{
//注意先下放遞歸再替換
change(u<<1|1,tr[u].tag);
tr[u].tag=tag;
}
else change(u<<1,tag);
}
else
{
if(calc(tag,mid)<calc(tr[u].tag,mid))
{
change(u<<1,tr[u].tag);
tr[u].tag=tag;
}
else change(u<<1|1,tag);
}
tr[u].min=min(tr[u].min,min(calc(tag,tr[u].l),calc(tag,tr[u].r))); //別忘記更新！！！
pushup(u);
return ;
}
void modify(int u,int l,int r,int tag)
{
if(l<=tr[u].l && tr[u].r<=r)
{
change(u,tag); //完全覆蓋當前區(qū)間時，按照change()函數(shù)的方法往下遞歸O(log N)層
return ;
}
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) modify(u<<1,l,r,tag);
if(r>mid) modify(u<<1|1,l,r,tag);
pushup(u);
return ;
}
int ask(int u,int x)
{
//注意當tr[u].l!=tr[u].r且tr[u].tag==0時，不要直接返回INF，因為可能平面上是線段
if(tr[u].l==tr[u].r)
{
if(!tr[u].tag) return INF; //注意初始化
return calc(tr[u].tag,x);
}
int mid=(tr[u].l+tr[u].r)>>1;
int res=calc(tr[u].tag,x); //別忘了當前區(qū)間的最值
if(x<=mid) res=min(res,ask(u<<1,x));
else res=min(res,ask(u<<1|1,x));
return res;
}
int query(int u,int l,int r)
{
if(l<=tr[u].l && tr[u].r<=r) return tr[u].min;
int mid=(tr[u].l+tr[u].r)>>1;
int res=INF;
if(tr[u].tag!=0/*注意特判*/) res=min(calc(tr[u].tag,max(tr[u].l,l)/*注意這里取的是max，別越界了！！！*/),calc(tr[u].tag,min(tr[u].r,r)/*注意這里取的是min，別越界了！！！*/)); //別忘了當前區(qū)間的最值
if(l<=mid) res=min(res,query(u<<1,l,r));
if(r>mid) res=min(res,query(u<<1|1,l,r));
return res;
}
//建立值域（可以為負）上的線段樹
build(1,LINF,RINF);
//插入
++num;
scanf("%d%d",&k[num],&b[num]);
change(1,num); //平面內插入一條全局直線
modify(1,LINF,RINF,num); //平面內插入一條區(qū)間線段
//查詢
printf("%d\n",ask(1,x)); //單點x=x0查詢最值
printf("%d\n",query(1,l,r)); //區(qū)間[xl,xr]查詢最值
8.7.2.拓展
李超線段樹就是線段樹+維護特殊的信息，線段樹的拓展李超線段樹也可以直接應用（模板也一樣）。
8.7.2.1.樹上序列——樹鏈剖分
樹剖剖一剖，將樹上問題轉化為序列問題，就可以用李超線段樹來做了。
但需要注意，例如：從s到t的樹上路徑，在點x上添加\(k*dis(s,x)+b\)的權值。由于李超線段樹只能維護k值確定的線段，所以我們要將式子適當變形：令\(p=lca(s,t)\)，那么\(s\)到\(p\)就可以表示為這么一條直線：\(y=?a×dis[i]+(a×dis[s]+b) i∈\{s,?x\}\)；\(t\)到\(p\)同理為：\(y=a×dis[i]+a×(dis[s]?2×dis[x]) i∈\{s,?x\}\)。然后直接在李超線段樹上維護區(qū)間最值就可以了。
8.7.2.2.李超線段樹合并\(O(N\log N)\)
適用條件：形如\(f[u]=\min\limits_{v \in subtree(u)} \{ u*v+b \}\)
復雜度證明：勢能分析：一條直線在插入及合并的過程中最多被下放\(O(depth_{max})=O(\log N)\)次，所以總的時間復雜度是\(O(N\log N)\)。
和線段樹合并一樣。
動態(tài)開點。
- 下面以求樹上每個點的最優(yōu)線段為例：
LL f[N];
int num;
LL k[N],b[N];
int rt[N],ridx;
struct Lc
{
int lson,rson; //線段樹合并，記錄左右兒子編號
int tag;
}tr[N*20*4];
void change(int &u/*動態(tài)開點*/,int l,int r,int tag)
{
if(!tr[u].tag)
{
u=++ridx; //動態(tài)開點
tr[u].tag=tag;
return ;
}
return ;
}
int merge(int p,int q,int l,int r)
{
if(!p || !q) return p|q;
if(l==r)
{
if(calc(tr[p].tag,l)<calc(tr[q].tag,l)) return p;
else return q;
}
int mid=(l+r)>>1;
tr[p].lson=merge(tr[p].lson,tr[q].lson,l,mid);
tr[p].rson=merge(tr[p].rson,tr[q].rson,mid+1,r);
change(p,l,r,tr[q].tag); //把q的直線插入p的平面
return p;
}
//求樹上每個點的最優(yōu)線段
void dfs(int u,int fa)
{
bool son=false;
for(int i=h[u];i!=0;i=ne[i])
{
int v=e[i];
if(v==fa) continue;
son=true;
dfs(v,u);
rt[u]=merge(rt[u],rt[v],-N,N);
}
if(son) f[u]=ask(rt[u],-N,N,x);
else f[u]=0;//注意特判
change(rt[u],-N,N,num);
return ;
}
dfs(1,-1);
8.7.3.應用
注意，李超線段樹只能維護斜率k值確定的直線。
8.7.3.1.李超線段樹優(yōu)化斜率優(yōu)化dp\(O(N \log N)\)
適用條件：斜率、橫坐標任意的斜率優(yōu)化dp。
由于李超線段樹可以動態(tài)維護整個平面上的斜率確定的直線或線段，或形如\(\min \{ kx+b \},(k是定值)\)，因此李超線段樹可以對于每一個i很輕松地找到凸包及其最值。
李超線段樹
用一條x=i的豎線去截所有直線并直接求出最值
一般斜率優(yōu)化dp
用一條斜率為i的直線去截凸包并求出截距
下面以\(f[i]=c+\min\limits_{j<i} \{ f[j]+d+e[i]*g[j] \}\)為例。
因為李超線段樹只能維護斜率k值確定的直線，所以不同于一般的斜率優(yōu)化dp的方程變形，我們只關心min括號內f[j]+d+e[i]*g[j]，用一條x=i的豎線去截所有直線并直接求出最值，我們把g[j]看做斜率k，f[j]+d看做截距b。
對于每個i，我們查詢整個平面的單點\(x=e[i]\)的最值以計算f[i]，然后在平面內插入斜率k為g[i]、截距b為f[i]+d的直線。
for(int i=1;i<=n;i++)
{
if(i!=1/*注意符合實際情況f[1]=0，否則會錯誤地使f[1]=c*/) f[i]=ask(1,e[i])+c;
k[i]=g[i],b[i]=f[i]+d;
change(1,i);
}
printf("%d\n",f[n]);
8.8.線段樹分治
《數(shù)據(jù)結構?13.3.1.2.有刪除操作——線段樹分治》
8.9.線段樹維護區(qū)間前綴最大值信息（單側遞歸問題，《樓房重建》）
下面以“單點修改+區(qū)間查詢單調遞增最長序列長度”為例。
單調遞增最長序列：從序列首個元素開始，序列最大值等于序列首個元素的權值，單調遞增最長序列長度等于1。從前往后掃描，只要一個節(jié)點的權值比序列最大值大，單調遞增最長序列長度+1，序列最大值等于該節(jié)點的權值。（故≠最長上升子序列）
單側遞歸問題。calc()和pushup()的復雜度是\(O(\log N)\)。
int n,m;
struct Tree
{
int l,r;
int ma,ans;//ans：只考慮當前區(qū)間的單調遞增最長序列長度
}tr[N*4];
//計算只考慮區(qū)間[l,r]且第一個數(shù)大于ma的單調遞增最長序列長度
int calc(int u,int ma)
{
if(tr[u].ma<=ma) return 0;
if(tr[u].l==tr[u].r) return 1;//別忘記遞歸邊界！！！
if(tr[u<<1].ma<=ma) return calc(u<<1|1,ma);
return calc(u<<1,ma)+(tr[u].ans-tr[u<<1].ans); //左兒子（遞歸處理）的答案+右兒子（直接計算，注意不是tr[u<<1|1].ans！）的答案
}
void pushup(int u)
{
tr[u].ma=max(tr[u<<1].ma,tr[u<<1|1].ma);
tr[u].ans=tr[u<<1].ans+calc(u<<1|1,tr[u<<1].ma); //左兒子（直接取值，因為左兒子不受任何限制）的答案+右兒子（遞歸處理，因為受到左兒子最大值的限制）的答案
return ;
}
void build(int u,int l,int r)
{
tr[u]={l,r};
if(l==r)
{
int x=read();
tr[u].ma=x,tr[u].ans=1;
return ;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
return ;
}
void change(int u,int x,int y)
{
if(tr[u].l==tr[u].r)
{
tr[u].ma=y;
tr[u].ans=1;
return ;
}
int mid=(tr[u].l+tr[u].r)>>1;
if(x<=mid) change(u<<1,x,y);
else change(u<<1|1,x,y);
pushup(u);
return ;
}
//ma要加上&：由于遞歸一定是左兒子優(yōu)先，所以最大值的限制可以從左到右更新傳遞
int query(int u,int l,int r,int &ma)
{
if(l<=tr[u].l && tr[u].r<=r)
{
int backup=ma;
ma=max(ma,tr[u].ma);
return calc(u,backup);
}
int mid=(tr[u].l+tr[u].r)>>1,res=0;
if(l<=mid) res+=query(u<<1,l,r,ma);
if(r>mid) res+=query(u<<1|1,l,r,ma);
return res;
}
int main()
{
n=read(),m=read();
build(1,1,n);
while(m--)
{
int op=read();
if(op==1)
{
int x=read(),y=read();
change(1,1,n,x,y);
}
else
{
int l=read(),r=read(),ma=0;
printf("%d\n",query(1,l,r,ma));
}
}
return 0;
}
8.10.線段樹維護單點+、min、max操作序列
-
線段樹維護什么信息？
把3種操作看作3個函數(shù)圖像。\(e.g.\)+：f(x)=x+val。
單看3種操作的函數(shù)圖像是一致的，他們都可以看作是左邊一段水平直線+中間一段斜率為1的直線+右邊一段水平直線，交接處無縫銜接有交點：\(f(x)=\begin{cases}mi&x< l,\\ x+delta&l\leqslant x\leqslant r,\\ ma&r<x.\end{cases}\)。
- +：\(mi=-\infty,delta=val,ma=\infty\)。
- min：\(mi=-\infty,delta=0,ma=val\)。
- max：\(mi=val,delta=0,ma=\infty\)。
- 空操作\(\varnothing\)：\(mi=-\infty,delta=0,ma=\infty\)。
只需要知道一個函數(shù)的3個信息mi、delta、ma即可，不需要知道l、r。因為\(f(x)=\min(\max(x+delta,mi),ma)\)。
-
怎么
pushup合并信息維護父節(jié)點？原操作序列f(x)→g(x)可視作求\(g(f(x))\)。也就是把f(x)的值域作為g(x)的定義域。
可以感性證明這種函數(shù)圖像的復合具有封閉性、結合律。那么就可以用線段樹維護信息了。
合并f(x)、g(x)的信息：
- mi：\(mi=g(mi_f)\)。
- delta：\(delta=delta_f+delta_g\)。
- ma：\(ma=g(ma_f)\)。
int n,q;
struct Segment
{
int l,r;
int mi,de,ma;
}tr[N*4];
inline int calc(int u,int x)//x經(jīng)過操作序列[tr[u].l,tr[u].r]得到的值
{
return min(max(x+tr[u].de,tr[u].mi),tr[u].ma);
}
void pushup(int u)
{
tr[u].mi=calc(u<<1|1,tr[u<<1].mi);
tr[u].de=tr[u<<1].de+tr[u<<1|1].de;
tr[u].ma=calc(u<<1|1,tr[u<<1].ma);
return ;
}
void build(int u,int l,int r)
{
tr[u]={l,r,-INF,0,INF};
if(l==r)
{
int opt=read(),val=read();
if(opt==1) tr[u].mi=-INF,tr[u].de=val,tr[u].ma=INF;
else if(opt==2) tr[u].mi=-INF,tr[u].de=0,tr[u].ma=val;
else tr[u].mi=val,tr[u].de=0,tr[u].ma=INF;
return ;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
return ;
}
void change(int u,int x,int mi,int de,int ma)
{
if(tr[u].l==tr[u].r)
{
tr[u].mi=mi,tr[u].de=de,tr[u].ma=ma;
return ;
}
int mid=(tr[u].l+tr[u].r)>>1;
if(x<=mid) change(u<<1,x,mi,de,ma);
else change(u<<1|1,x,mi,de,ma);
pushup(u);
return ;
}
n=read();
build(1,1,n);
q=read();
while(q--)
{
int c=read();
if(c==1)
{
int pos=read(),val=read();
change(1,pos,-INF,val,INF);
}
else if(c==2)
{
int pos=read(),val=read();
change(1,pos,-INF,0,val);
}
else if(c==3)
{
int pos=read(),val=read();
change(1,pos,val,0,INF);
}
else
{
int x=read();
printf("%d\n",calc(1,x));
}
}
8.11.線段樹維護重排等差數(shù)列
給定長度為n的序列a，支持修改：給定x,y，把a_x修改為y；+查詢：給定l,r,k，查詢將區(qū)間[l,r]的數(shù)從小到大排序后是否能構成公差為k的等差數(shù)列）。
以下3個條件同時滿足是對于一個查詢回答Yes的充要條件：
-
[l,r]最大值-[l,r]最小值=(r-l)*k。
線段樹維護區(qū)間最大值和最小值。
-
[l,r]內相鄰兩數(shù)差的絕對值的gcd是k。
線段樹維護區(qū)間左端點和右端點+差的gcd。
sp.當線段樹區(qū)間lr時，令差的gcd=0。當詢問區(qū)間lr時，無論k是多少，均回答Yes（只有一個數(shù)的數(shù)列也是等差數(shù)列）。
-
[l,r]內無重復數(shù)字，即[l,r]前驅（指在它之前和它的權值相同的元素的位置）最大值<l。
新建全局set
s[N]。s[x]儲存數(shù)值為x出現(xiàn)的位置。因此還需要map對數(shù)值離散化，當且僅當訪問set時，使用離散化后的值。 線段樹維護前驅最大值（葉子節(jié)點儲存它的前驅）。
修改時要一起修改“x、原來a[x]的后繼以及現(xiàn)在y的后繼”的前驅。
sp.詢問k==0時，此條件不要求滿足。
8.12.線段樹維護遞推數(shù)列之和
適用條件：給定一個序列\(\{a_n\}\)，1 l r x：給\(a_l\sim a_r\)加上x；2 l r：求\(\sum\limits_{i=l}^r f_{a_i}\)。其中\(f_i\)是遞推數(shù)列，只求1個\(f_i\)可以用初始矩陣S和轉移矩陣T：\(S*T^i\)求解。
序列上的元素i表示\(S*T^i\)。
矩陣乘法對加法的的分配律：\(S*T^i+S*T^j=S*(T^i+T^j)\)。這使得可以用線段樹維護當前區(qū)間的轉移矩陣T之和。
區(qū)間下標加：\(S*T^{i+x}+S*T^{j+x}=S*(T^i*T^x+T^j*T^x)=S*(T^i+T^j)*T^x\)。
線段樹維護當前區(qū)間的轉移矩陣T之和。詢問2=S*區(qū)間[l,r]的轉移矩陣T之和。
int n,m;
struct Matrix
{
LL mat[K][K];
Matrix()
{
memset(mat,0,sizeof mat);
return ;
}
Matrix(int a)
{
if(a==0) //單位元矩陣
{
for(int i=0;i<K;i++)
for(int j=0;j<K;j++)
if(i==j) mat[i][j]=1;
else mat[i][j]=0;
}
else if(a==1) //初始矩陣S
else //轉移矩陣T
return ;
}
bool operator == (const Matrix &qw) const
{
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
if(mat[i][j]!=qw.mat[i][j]) return false;
return true;
}
Matrix operator + (const Matrix &qw) const
{
Matrix res;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
res.mat[i][j]=(mat[i][j]+qw.mat[i][j])%MOD;
return res;
}
Matrix operator * (const Matrix &qw) const
{
Matrix res;
for(int k=0;k<2;k++)
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
res.mat[i][j]=(res.mat[i][j]+mat[i][k]*qw.mat[k][j]%MOD)%MOD;
return res;
}
};
struct Segmenttree
{
int l,r;
Matrix sum; //區(qū)間[l,r]的轉移矩陣T之和
Matrix mul=Matrix(0); //區(qū)間下標加懶標記
}tr[N*4];
Matrix qpow(Matrix a,LL b)
{
Matrix res;
res=Matrix(0);
while(b)
{
if(b&1) res=res*a;
a=a*a;
b>>=1;
}
return res;
}
void update(int u,Matrix mul)
{
tr[u].sum=tr[u].sum*mul;
tr[u].mul=tr[u].mul*mul;
return ;
}
void pushdown(int u)
{
if(tr[u].mul==Matrix(0)) return ;
update(u<<1,tr[u].mul);
update(u<<1|1,tr[u].mul);
tr[u].mul=Matrix(0);
return ;
}
void pushup(int u)
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
return ;
}
void build(int u,int l,int r)
{
tr[u]={l,r};
if(l==r)
{
int a;
scanf("%d",&a);
tr[u].sum=qpow(Matrix(2),a);
return ;
}
int mid=(tr[u].l+tr[u].r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
return ;
}
void modify(int u,int l,int r,Matrix mul)
{
if(l<=tr[u].l && tr[u].r<=r)
{
update(u,mul);
return ;
}
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) modify(u<<1,l,r,mul);
if(r>mid) modify(u<<1|1,l,r,mul);
pushup(u);
return ;
}
Matrix query(int u,int l,int r)
{
if(l<=tr[u].l && tr[u].r<=r) return tr[u].sum;
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid && r>mid) return query(u<<1,l,r)+query(u<<1|1,l,r);
else if(l<=mid) return query(u<<1,l,r);
else return query(u<<1|1,l,r);
}
scanf("%d%d",&n,&m);
build(1,1,n);
while(m--)
{
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==1)
{
LL x;
scanf("%lld",&x);
modify(1,l,r,qpow(Matrix(2),x));
}
else printf("%lld\n",(Matrix(1)*query(1,l,r)).mat[0][0]);
}
8.13.線段樹維護時間軸
線段樹維護序列
一般的線段樹寫法。
整棵線段樹維護整個序列。
按時間順序依次插入操作。
查詢時查詢線段樹上某個區(qū)間。
線段樹維護時間軸
需要維護版本，區(qū)間修改（故主席樹不可做）+單點查詢。離線數(shù)據(jù)結構。
整棵線段樹維護序列某一個位置的所有時間信息。
朝序列方向推進插入操作。\(e.g.\)第3個操作是對區(qū)間[6,8]加1→在推進到6時，在線段樹上第3個位置+1；在推進到8時，在線段樹上第3個位置-1。
查詢時查詢線段樹前綴。\(e.g.\)第9個操作是對單點12進行詢問→在推進到12時，查詢線段樹[1,9]的區(qū)間和。
8.14.線段樹上二分\(O(\log N)\)
在區(qū)間[l,r]上二分→線段樹把[l,r]分成\(O(\log N)\)個區(qū)間，線段樹節(jié)點維護區(qū)間的單調性信息。先依次掃描\(O(\log N)\)個區(qū)間，根據(jù)線段樹節(jié)點維護的區(qū)間單調性信息判斷最終分界點在哪個區(qū)間，再在該區(qū)間上通過往線段樹下遞歸的方式直接二分找到最終分界點。
下面以“在[l,r]內查找從左到右開始滿足條件的下標，不存在返回-1”為例。“在[l,r]內查找從左到右結束滿足的下標（從右到左開始）”把下面的先序遍歷改為后序遍歷即可。
int binary(int u,int l,int r)
{
if(l<=tr[u].l && tr[u].r<=r)
{
if(!check(u)) return -1;
if(tr[u].l==tr[u].r) return tr[u].l;
pushdown(u);
if(check(u<<1)) return binary(u<<1,l,r);
else return binary(u<<1|1,l,r);
}
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1,res=-1;
if(l<=mid) res=binary(u<<1,l,r);
if(r>mid && res==-1) res=binary(u<<1|1,l,r);
return res;
}
9.分塊
9.1.分塊
9.1.1.分塊
以動態(tài)維護區(qū)間+-，動態(tài)查詢區(qū)間和為例
注意這里的sum是包含add的。
//注意這里的sum是包含add的
int n,m,len;
int w[N];
LL add[M],sum[M];
int get(int i)
{
return (i-1)/len;
}
void change(int l,int r,int d)
{
if(get(l)==get(r)) //l和r在同一段內直接暴力
{
for(int i=l;i<=r;i++)
{
w[i]+=d;
sum[get(i)]+=d; //注意這里不要忘記！！！
}
return ;
}
int i=l,j=r;
while(get(i)==get(l))
{
w[i]+=d;
sum[get(i)]+=d;
i++;
}
while(get(j)==get(r))
{
w[j]+=d;
sum[get(j)]+=d;
j--;
}
for(int k=get(i);k<=get(j);k++)
{
add[k]+=d;
sum[k]+=len*d;
}
return ;
}
LL query(int l,int r)
{
LL res=0;
if(get(l)==get(r))
{
for(int i=l;i<=r;i++) res+=w[i]+add[get(i)];
return res;
}
int i=l,j=r;
while(get(i)==get(l))
{
res+=w[i]+add[get(i)];
i++;
}
while(get(j)==get(r))
{
res+=w[j]+add[get(j)];
j--;
}
for(int k=get(i);k<=get(j);k++) res+=sum[k];
return res;
}
int main()
{
scanf("%d%d",&n,&m);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
sum[get(i)]+=w[i];
}
while(m--)
{
int l,r,d;
char op[2];
scanf("%s",op);
if(op[0]=='C')
{
scanf("%d%d%d",&l,&r,&d);
change(l,r,d);
}
else
{
scanf("%d%d",&l,&r);
printf("%lld\n",query(l,r));
}
}
return 0;
}
9.1.2.詢問分塊
適用條件：當沒有修改或少數(shù)修改時的詢問容易回答。
9.1.3.序列分塊
適用條件：需要平衡預處理和詢問的復雜度。
對序列進行分塊，降低預處理或詢問一方的復雜度，但是會提高另一方的復雜度。
9.1.3.1.\(O(\sqrt N)\)修改\(O(1)\)查詢前綴和
LL s1[N/B+10],s2[N]; //s1[b]：第b塊的前綴和；s2[i]：位置i在其塊內的前綴和
void add(int x,LL val)
{
int id=x/B;
for(int i=x;i/B==id && i<M/*注意這里！！！*/;i++) s2[i]+=val;
for(int i=id;i<=N/B;i++) s1[i]+=val;
return ;
}
LL ask(int x)
{
int id=x/B;
if(id==0) return s2[x];
else return s1[id-1]+s2[x];
}
9.2.塊狀鏈表（分塊+鏈表）
9.3.根號分治算法
適用條件：2種“糟糕”的算法，兩個約束，相互制約，制約關系是乘積關系。
9.3.1.步長與項數(shù)
- 預處理的復雜度大。
- 不預處理，但是詢問暴力求解的復雜度大。
分界：步長。當詢問的步長\(\leqslant \sqrt N\)時，采用算法1；否則，此時詢問的項數(shù)\(\leqslant \sqrt N\)，采用算法2。
9.3.2.種類與數(shù)量
特征：總共有N個元素，每個元素屬于一個種類spe。
數(shù)量*種類=總數(shù)N，種類=總數(shù)N/數(shù)量。
9.3.2.1.元素
- 對于一個種類，O(數(shù)量數(shù)量)求解。時間復雜度為O(種類數(shù)量數(shù)量)=O(N數(shù)量)。
- 對于一個種類，O(總數(shù)N)求解。時間復雜度為O(種類*N)。
分界：屬于該種類的元素的數(shù)量。當屬于該種類的元素的數(shù)量\(\leqslant \sqrt N\)時，采用算法1；否則，此時這樣的種類的個數(shù)\(\leqslant \sqrt N\)，采用算法2。
9.3.2.2.元素對
題目：n個元素，每個元素屬于一個種類spe，還有一些限制條件。對于第i個詢問a、b，找到滿足spe[u]=a、spe[v]=b的元素對(u,v)數(shù)量。
首先記憶化排除重復的詢問。
- 用u找合法的v。詢問(a,b)離線儲存在vector A[a]中。掃描每一個u，取出A[spe[u]]進行求解。O(滿足spe[u]=a、spe[v]=b的總數(shù)量*所有v的種類個數(shù))，因為每一個a_i至多放b_1、b_2、...b_q（記憶化已排除重復的詢問(a,b)）。
- 用v找合法的u。詢問(a,b)離線儲存在vector B[v]。掃描每一個v，取出B[spe[v]]進行求解。O(詢問個數(shù)*屬于種類spe[v]的元素的數(shù)量)，因為每一個詢問會使屬于種類spe[v]的元素的vector B[spe[v]]的大小+1。
分界：屬于種類spe[i]的元素的數(shù)量。當屬于種類spe[i]的元素的數(shù)量\(\ge \sqrt N\)時，采用算法1，因為這樣每個vector A[spe[u]]至多儲存\(\sqrt N\)個v（種類=總數(shù)/數(shù)量\(≤\sqrt N\)）；當屬于種類spe[i]的元素的數(shù)量\(\le \sqrt N\)時，采用算法2。
void solve_u(int u)
{
for(auto it : A[spe[u]])
}
void solve_v(int v)
{
for(auto it : B[spe[v]])
}
len=sqrt(n)+1;
calc_cnt();
for(int i=1;i<=q;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(Hash.count({a,b})) ans[i]=Hash[{a,b}]; //記憶化排除重復的詢問
else
{
if(cnt[b]>len) A[a].push_back({i,b});
else B[b].push_back({i,a});
Hash[{a,b}]=-i; //負數(shù)方便下面判斷
}
}
solve_u(1);
solve_v(1);
for(int i=1;i<=q;i++)
{
if(ans[i]<0) printf("%lld\n",ans[-ans[i]]);
else printf("%lld\n",ans[i]);
}
9.3.3.質數(shù)
n至多只有1個\(>\sqrt n\)的質數(shù)。
- 把所有的元素按照其所含的最大質因子排序。
for(int i=2;i<=n;i++)
{
int x=i;
for(int j=0;j<prime.size();j++)
if(x%prime[j]==0)
{
num[i].y|=1<<j;
while(x%prime[j]==0) x/=prime[j];
}
if(x>1) num[i].x=x;
}
- 把每一段所含的最大質因子相同的元素（若最大質因子\(≤\sqrt n\)，算作同一段）一起處理，將處理≤n的質數(shù)的原問題轉化為處理\(≤\sqrt n\)的質數(shù)的問題。
for(int l=1,r;l<=n;l=r+1)
{
r=l;
while(r+1<=n && num[r+1].x==num[l].x) r++;
if(l==1) work1();
else work2();
}
- 最后合并每一段的信息。
9.3.4.類整除分塊
適用條件：1.對于\(i\in[1,n]\)，求\(f_i\) ;2.有\(O(F(N))\)求\(f_i\) 的做法；3.\(\forall i\in[\sqrt N,N]\)，\(f_i\)的取值不超過\(O(\sqrt N)\)種，且 \(f_i\)具有單調性。
- 設塊長\(B=\sqrt{N\log N}\)。
- 對于\(i\in[1,B]\)，\(O(F(N))\)求\(f_i\)。
- 對于\(i\in(B,N]\)，類似于整除分塊，定l求\(f_l\)，二分求出r，使得\(\forall i\in[l,r],f_i=f_l\)。
總的時間復雜度是\(O(\sqrt N\log NF(N))\)。
int solve(int i) //求出f_i
int get_r(int L)
{
int l=L,r=n;
while(l<r)
{
int mid=(l+r+1)>>1;
if(solve(mid)==ans[L]) l=mid;
else r=mid-1;
}
return l;
}
b=sqrt(n*log2(n));
for(int i=1;i<=b;i++) ans[i]=solve(i);
for(int l=b+1,r;l<=n;l=r+1)
{
ans[l]=solve(l);
r=get_r(l);
for(int i=l+1;i<=r;i++) ans[i]=ans[l];
}
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
9.3.5.度數(shù)與點數(shù)
前提條件：邊數(shù)（度數(shù)*點數(shù)=邊數(shù)）不太多。
對于每個點的狀態(tài)的求解，采用下面兩種算法之一：
-
在自己的階段，拿別人轉移到自己（from）。自己的度數(shù)不能太多。
-
在別人的階段，預先讓別人轉移到自己（to）。這樣的“自己”的數(shù)量不能太多。
相當于特殊對待自己。可能需要額外開一個新數(shù)組。
分界：度數(shù)。當該點的度數(shù)\(\leqslant \sqrt M\)時，采用算法1；否則，此時這樣的點的數(shù)量\(\leqslant \sqrt M\)，采用算法2。
9.4.平衡思想
10.離線算法
10.1.莫隊
離線算法。
適用條件：從區(qū)間[l,r]的答案擴展到區(qū)間[l?1,r],[l+1,r],[l,r?1],[l,r+1]的答案的時間復雜度均為 O(1)。
莫隊排序
而莫隊算法則是通過改變掃描的順序來優(yōu)化上述暴力做法的。先按照值域 \(\left[0,n\right]\) 分塊，分成 \(\sqrt{n}\) 塊，則第 \(i\) 塊應表示為 \(\left[\left(i-1\right)\times\sqrt{n},i\times\sqrt{n}\right]\)。對于一個區(qū)間 \(\left[l,r\right]\)，設 \(p\) 表示左端點 \(l\) 所在的塊的編號（即 \(p=\left\lceil\dfrac{l}{\sqrt{n}}\right\rceil\)），那么我們將所有區(qū)間按照 \(p\) 為第一關鍵字，按照 \(r\) 為第二關鍵字排序。可以證明，按照這樣排序的順序依次執(zhí)行上述暴力算法可以使得時間復雜度為 \(O\left(n\sqrt{n}\right)\)
玄學優(yōu)化
- 奇數(shù)塊中按照 \(r\) 升序排列，偶數(shù)塊中按照 \(r\) 降序排列（倒過來也可以），實踐證明會縮短大約一半的時間。其實很好理解：第一次 \(r\) 從小到大滾，第二次 \(r\) 從大到小滾，肯定比第二次從小到大重新滾要更快。
- 塊的長度不一定要是 \(\sqrt{n}\)。在 \(n\not=m\) 的時候，一般來說長度 \(a\) 取 \(\sqrt{\dfrac{n^2}{m}}\) 會好一些，此時的時間復雜度為 \(O\left(\sqrt{n^2m}\right)\)。
原因：此時 \(r\) 的移動次數(shù)為 \(\dfrac{n^2}{a}\)，\(l\) 的移動次數(shù)為 \(am\)，當二者相等時二者的和最小。（積一定，差小和小）
10.1.1.莫隊
以靜態(tài)查詢區(qū)間數(shù)字種類個數(shù)為例。
int n,m,len,res;
int w[N],ans[M];
struct node
{
int id,l,r;
}q[M];
int cnt[S];
int get(int x)
{
return x/len;
}
bool cmp(const node &a,const node &b)
{
if(get(a.l)!=get(b.l)) return get(a.l)<get(b.l);
if(get(a.l)%2==0) return a.r<b.r;
return a.r>b.r;
}
void add(int x)
{
if(cnt[x]==0) res++;
cnt[x]++;
return ;
}
void del(int x)
{
if(cnt[x]==1) res--;
cnt[x]--;
return ;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
scanf("%d",&m);
len=max(1,(int)sqrt((double)n*n/m));
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
q[i]={i,l,r};
}
sort(q+1,q+m+1,cmp);
for(int i=1,tt=0,hh=1;i<=m;i++)
{
int id=q[i].id,l=q[i].l,r=q[i].r;
while(tt<r) tt++,add(w[tt]);
while(hh>l) hh--,add(w[hh]);
while(tt>r) del(w[tt]),tt--;
while(hh<l) del(w[hh]),hh++;
ans[id]=res;
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
10.1.2.帶修改的莫隊
增加一個新的維度\(time\)，表示數(shù)組在第time次修改后是什么樣的。與此同理，我們的詢問操作也從一個二元組變成了一個三元組——\(\left(l,r,time\right)\)，表示在第 \(time\) 次修改后詢問區(qū)間 \(\left[l,r\right]\) 的值。
最簡單的想法就是對 \(l\)、\(r\) 分別分塊，\(time\) 單調遞增，然后以 \(l\) 的塊編號為第一關鍵字，以 \(r\) 的塊編號為第二關鍵字，以 \(time\) 為第三關鍵字進行排序。
以動態(tài)修改單點，動態(tài)查詢區(qū)間查詢區(qū)間數(shù)字種類個數(shù)為例。
int n,mm,len;
int w[N],cnt[S],ans[N];
int qidx;
struct Query
{
int id,l,r,t;
}q[N];
int midx;
struct Modify
{
int p,col;
}m[N];
int get(int x)
{
return x/len;
}
bool cmp(const Query& a, const Query& b)
{
int al = get(a.l), ar = get(a.r);
int bl = get(b.l), br = get(b.r);
if (al != bl) return al < bl;
if (ar != br) return ar < br;
return a.t < b.t;
}
void add(int x,int &res)
{
if(cnt[x]==0) res++;
cnt[x]++;
return ;
}
void del(int x,int &res)
{
cnt[x]--;
if(cnt[x]==0) res--;
return ;
}
int main()
{
scanf("%d%d",&n,&mm);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=mm;i++)
{
char op[2];
scanf("%s",op);
if(op[0]=='Q')
{
int l,r;
scanf("%d%d",&l,&r);
++qidx;
q[qidx]={qidx,l,r,midx};
}
else
{
int p,col;
scanf("%d%d",&p,&col);
++midx;
m[midx]={p,col};
}
}
len=pow(n*max(1,midx),1.0/3)+1; //注意midx=0（即全是查詢的情況）的情況
sort(q+1,q+qidx+1,cmp);
for(int i=1,tt=0,hh=1,tim=0,res=0;i<=qidx;i++)
{
int id=q[i].id,l=q[i].l,r=q[i].r,t=q[i].t;
while(tt<r) tt++,add(w[tt],res);
while(hh>l) hh--,add(w[hh],res);
while(tt>r) del(w[tt],res),tt--;
while(hh<l) del(w[hh],res),hh++;
while(tim<t)
{
tim++;
if(l<=m[tim].p && m[tim].p<=r)
{
del(w[m[tim].p],res);
add(m[tim].col,res);
}
swap(w[m[tim].p],m[tim].col);
}
while(tim>t)
{
if(l<=m[tim].p && m[tim].p<=r)
{
del(w[m[tim].p],res);
add(m[tim].col,res);
}
swap(w[m[tim].p],m[tim].col);
tim--;
}
ans[id]=res;
}
for(int i=1;i<=qidx;i++) printf("%d\n",ans[i]);
return 0;
}
10.1.3.回滾莫隊
適用條件：add的復雜度較小，而del的復雜度較大。
每一次循環(huán)都處理完左端點所在同一個塊內的所有情況：
- 右端點在塊內：暴力求解。之后暴力還原現(xiàn)場 \(cnt\)和
res=0;。 - 右端點在塊外：以塊內外邊界為初始區(qū)間往左右擴展，由于右端點單調遞增可直接add，左端點則要備份暴力擴展暴力還原現(xiàn)場。
- 關于處理
del：暴力還原\(cnt\)，有利用價值的\(res\)先備份，沒有利用價值的\(res\)res=0;。 - 一輪循環(huán)結束后
memset(cnt,0,sizeof cnt);//范圍不確定，沒有利用價值。
int n,m,len;
int type[N];
LL ans[N];
int hidx;
int h[N];
int cnt[N];
struct Query
{
int id,l,r;
}q[N];
int Hash(int x)
{
return lower_bound(h+1,h+hidx+1,x)-h;
}
int get(int x)
{
return x/len;
}
bool cmp(const Query& a, const Query& b)
{
int i = get(a.l), j = get(b.l);
if (i != j) return i < j;
return a.r < b.r;
}
void add(int x,LL &res)
{
cnt[x]++;
res=max(res,(LL)cnt[x]*h[x]);
return ;
}
int main()
{
scanf("%d%d",&n,&m);
len=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&type[i]);
h[i]=type[i];
}
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d%d",&l,&r);
q[i]={i,l,r};
}
sort(h+1,h+n+1);
hidx=unique(h+1,h+n+1)-(h+1);
for(int i=1;i<=n;i++) type[i]=Hash(type[i]);
sort(q+1,q+m+1,cmp);
int i=1;
while(i<=m)//每一次循環(huán)都處理完左端點所在同一個塊內的所有情況
{
LL res;//注意下面res初始化成0的不同位置
int ne=i;//左端點在下一個塊的問題編號，也就是當前循環(huán)的邊界
while(ne<=m && get(q[ne].l)==get(q[i].l)) ne++;
int right=min(n/*小心越界*/,get(q[i].l)*len+(len-1));//當前塊的右端點
//右端點在塊內：暴力求解
while(i<ne && q[i].r<=right)
{
res=0;//每次暴力求解時，范圍都不確定，故上一次的res沒有利用價值
int id=q[i].id,l=q[i].l,r=q[i].r;
for(int k=l;k<=r;k++) add(type[k],res);
ans[id]=res;
for(int k=l;k<=r;k++) cnt[type[k]]--; //暴力還原現(xiàn)場
i++;
}
//右端點在塊外：由于右端點單調遞增可直接add，左端點則要備份
res=0;//區(qū)間所包含的塊外的部分單調遞增，故上一次的res有利用價值，因此采用備份
int tt=right,hh=right+1; //以塊內外邊界為初始區(qū)間往左右擴展
while(i<ne)
{
int id=q[i].id,l=q[i].l,r=q[i].r;
while(tt<r) tt++,add(type[tt],res);
LL backup=res; //左端點范圍不確定，備份
while(hh>l) hh--,add(type[hh],res);
ans[id]=res;
while(hh<=right) cnt[type[hh]]--,hh++;
res=backup; //還原現(xiàn)場
i++;
}
memset(cnt,0,sizeof cnt);//范圍不確定，沒有利用價值
}
for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
return 0;
}
10.1.4.樹上莫隊
- 離散化；
- 求括號序列；
- 求lca；
- 將樹上詢問變?yōu)閰^(qū)間詢問；
- 莫隊。
求歐拉序列2.2.1.《樹的歐拉序列》：
C++代碼
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,len;
int w[N];
int h[N],e[N],ne[N],idx;
//歐拉序列的變量
int seq[N],sidx;
int fir[N],las[N]; //fir[x]：x在歐拉序列中第一次出現(xiàn)的地方；las[x]：x在歐拉序列中最后一次出現(xiàn)的地方。
int depth[N],fa[N][16];
//莫隊的變量
int cnt[N],st[N],ans[N];
struct Query
{
int id,l,r,p; //p：歐拉序列是否要加上lca(l,r)這個點
}q[N];
//離散化
vector<int> nums;
int Hash(int x)
{
return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
void add_edge(int u,int v)
{
e[++idx]=v;
ne[idx]=h[u];
h[u]=idx;
return ;
}
void dfs(int u,int father)
{
seq[++sidx]=u;
fir[u]=sidx;
for(int i=h[u];i!=0;i=ne[i])
{
int v=e[i];
if(v==father) continue;
dfs(v,u);
}
seq[++sidx]=u;
las[u]=sidx;
return ;
}
void init_lca(int u,int father)
{
for(int i=h[u];i!=0;i=ne[i])
{
int v=e[i];
if(v==father) continue;
depth[v]=depth[u]+1;
fa[v][0]=u;
for(int k=1;k<=15;k++) fa[v][k]=fa[fa[v][k-1]][k-1];
init_lca(v,u);
}
return ;
}
int lca(int x,int y)
{
if(depth[x]<depth[y]) swap(x,y);
for(int k=15;k>=0;k--) if(depth[fa[x][k]]>=depth[y]) x=fa[x][k];
if(x==y) return x;
for(int k=15;k>=0;k--)
if(fa[x][k]!=fa[y][k])
{
x=fa[x][k];
y=fa[y][k];
}
return fa[x][0];
}
int get(int x)
{
return (x-1)/len;
}
bool cmp(const Query a,const Query b)
{
if(get(a.l)!=get(b.l)) return a.l<b.l;
return a.r<b.r;
}
//add和del是同一個函數(shù)
void add(int x,int &res)
{
st[x]^=1;
if(st[x]==0)
{
cnt[w[x]]--; //注意這里不要忘記w[]
if(!cnt[w[x]]) res--;
}
else
{
if(!cnt[w[x]]) res++;
cnt[w[x]]++;
}
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
nums.push_back(w[i]);
}
//離散化
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
for(int i=1;i<=n;i++) w[i]=Hash(w[i]);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v),add_edge(v,u);
}
//求歐拉序列
dfs(1,-1);
//求lca
depth[1]=1;
init_lca(1,-1);
//將樹上詢問變?yōu)閰^(qū)間詢問
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(fir[x]>fir[y]) swap(x,y);
int p=lca(x,y);
if(x==p) q[i]={i,fir[x],fir[y],0};
else q[i]={i,las[x],fir[y],p};
}
//莫隊
len=sqrt(sidx);
sort(q+1,q+m+1,cmp);
for(int i=1,tt=0,hh=1,res=0;i<=m;i++)
{
int id=q[i].id,l=q[i].l,r=q[i].r,p=q[i].p;
while(tt<r) tt++,add(seq[tt],res); //注意轉化為區(qū)間要加上seq[]
while(hh>l) hh--,add(seq[hh],res);
while(tt>r) add(seq[tt],res),tt--; //add和del是同一個函數(shù)
while(hh<l) add(seq[hh],res),hh++; //add和del是同一個函數(shù)
if(p) add(p,res); //特判
ans[id]=res;
if(p) add(p,res); //add和del是同一個函數(shù)
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
10.1.5.二次離線莫隊
適用條件：數(shù)據(jù)只能一邊加入一邊掃描計算（也就是只能求1~i-1對i的貢獻）。
對于一個詢問，采用記錄它與上一個詢問答案的偏移量（差分）的方法。最后統(tǒng)計答案時用前綴和。
因為數(shù)據(jù)只能一邊加入一邊掃描計算，所以設g：一邊加入數(shù)據(jù)，輔助變量；f[x]：一邊掃描計算并記錄，1~(x-1)對x的貢獻。
更進一步地，設s[x]：1~x對當前i的貢獻。
下面以右端點指針tt向右移動一個單位從tt-1到tt為例：
此處的偏移量delta=s[tt-1]-s[hh-1]，顯然s[tt-1]=f[tt]，而s[hh-1]卻不好求。
但是注意到右端點指針tt向右移動從i-1到詢問區(qū)間右端點r時，i~r的偏移量都只剩對于每一個\(j\in [i,r]\)求解相應的s[hh-1]，因此第一次離線可以先不加偏移量-s[hh-1]，再來一次離線對于每一個\(j\in [i,r]\)求解相應的s[hh-1]。
- 預處理f[x]，一邊加入數(shù)據(jù)：g；一邊掃描計算并記錄：f[x]。
- 第一次離線。對于每一個詢問先記錄待求解問題：對于每一個\(j\in [i,r]\)求解相應的s[hh-1]，儲存到節(jié)點hh-1，再一邊加入數(shù)據(jù)一邊掃描計算s[tt-1]=f[tt]，把s[tt-1]先加入偏移量。
- 第二次離線。
g=0;，從零開始一邊加入數(shù)據(jù)一邊掃描計算。當掃描到hh-1時。把hh-1儲存的待求解問題拿出來：對于每一個\(j\in [i,r]\)求解相應的s[hh-1]。然后對于每一個\(j\in [i,r]\)求解相應的s[hh-1]，加入對應詢問的偏移量。
int ans[N];
int g,f[N]; //g：一邊加入，輔助變量；f[i]：一邊掃描計算并記錄，1~(i-1)對i的貢獻
struct Query
{
int id,l,r;
LL delta; //與上一個詢問答案的偏移量（差分）。最后統(tǒng)計答案時用前綴和
}q[N];
struct Range
{
int id,l,r,sign; //sign：正負號
};
vector<Range> range[N]; //range[i]={id,l,r,sign}：q[id].delta+=sign*（對于每一個j\in [l,r]求解相應的s[i]）
len=sqrt(n);
sort(q+1,q+m+1,cmp); //正常的莫隊排序
//預處理f[x]
for(int i=1;i<=n;i++)
{
f[i]=g; //一邊掃描計算
calc(g,i); //一邊加入數(shù)據(jù)
}
//第一次離線：把s[tt-1]=f[tt]先加入偏移量
for(int i=1,tt=0,hh=1;i<=m;i++)
{
int l=q[i].l,r=q[i].r;
if(tt<r) range[hh-1].push_back({i,tt+1,r,-1}); //記錄待求解問題：每一個j\in [tt+1,r]求解相應的s[hh-1]
while(tt<r) tt++,q[i].delta+=f[tt];
if(hh>l) range[tt].push_back({i,l,hh-1,1}); //對于左端點hh向左移動，仔細思考會發(fā)現(xiàn)s[hh-1]=f[hh]，s[tt]才是待求解問題
while(hh>l) hh--,q[i].delta-=f[hh];
if(tt>r) range[hh-1].push_back({i,r+1,tt,1});
while(tt>r) q[i].delta-=f[tt],tt--;
if(hh<l) range[tt].push_back({i,hh,l-1,-1});
while(hh<l) q[i].delta+=f[hh],hh++;
}
//第二次離線：求解待求解問題s[hh-1]
g=0;
for(int i=1;i<=n;i++)
{
calc(g,i);
for(auto it : range[i])
{
int id=it.id,l=it.l,r=it.r,sign=it.sign;
for(int j=l;j<=r;j++) q[id].delta+=another_calc(g,j)*sign;
}
}
for(int i=2;i<=m;i++) q[i].delta+=q[i-1].delta; //差分后的前綴和=答案
for(int i=1;i<=m;i++) ans[q[i].id]=q[i].delta;
for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
10.2.基于時間的分治算法
見《數(shù)據(jù)結構·數(shù)13.3.1.基于時間的分治算法》
10.3.基于值域的分治算法——整體二分
見《數(shù)據(jù)結構·數(shù)13.3.2.基于值域的分治算法——整體二分》
11.二叉搜索樹
二叉搜索樹是一棵滿足在中序遍歷中關鍵字key單調遞增/遞減的二叉樹。
11.1.笛卡爾樹\(O(N)\)
每個節(jié)點有兩個信息\((x_i,y_i)\)。x滿足二叉搜索樹的性質（在中序遍歷中x單調遞增/遞減）， y滿足小/大根堆的性質（當前節(jié)點的y小/大于其子節(jié)點的y）。
- 子樹下標是一段連續(xù)x的區(qū)間。
- 根節(jié)點是st[1]。
- treap本質上也是一種笛卡爾樹。
每次插入一個新節(jié)點時，為了確保二叉搜索樹的性質得到滿足（別忘了之前按照 x 遞增的順序插入），需要將新節(jié)點插入到盡可能靠右端的位置。
- 構建笛卡爾樹一定要保證x遞增的順序插入！！！
- 插入點u時用單調棧維護一個從根節(jié)點一直走到右兒子的鏈。
- 在單調棧中找到第一個y權值比\(y_u\)大的點st[cur]，令st[cur]的右兒子是u（如果不存在這樣的點，那 u 就是根節(jié)點）。
- 如果 st[cur] 已經(jīng)有右子樹了，就令st[cur] 的右子樹是 u 的左子樹。（因為之前插入的點的 x 權值都比\(u_x\)小， 因此這樣不會破壞二叉搜索樹的性質）
int n;
struct Descartes //(x,y)
{
int kid[2]; //左右兒子
int val; //y
}tr[N]; //tr[x]
int st[N],top,cur; //單調棧
void insert(int i)
{
cur=top;
while(cur && tr[st[cur]].val>tr[i].val) cur--;
if(cur) tr[st[cur]].kid[1]=i; //當前點不是根
if(cur<top) tr[i].kid[0]=st[cur+1]; //當前點有彈出別的節(jié)點，st[cur]有右子樹
top=cur;
st[++top]=i;
return ;
}
void dfs(int u) //遍歷笛卡爾樹
{
for(int i=0;i<2;i++)
{
int v=tr[u].kid[i];
if(!v) continue;//沒有該兒子
dfs(v);
}
return ;
}
for(int i=1;i<=n;i++) //建樹。注意保證x遞增的順序插入！！！
{
tr[i].val=read();
insert(i);
}
dfs(st[1]); //根節(jié)點是st[1]
11.1.1.直方圖子矩形問題
把下標i作為x，高度\(h_i\)作為y，建立一棵\((i,h_i)\)的笛卡爾樹。
因此u的子樹內的節(jié)點的高度都大于等于\(h_u\)，且子樹u下標是一段i的連續(xù)區(qū)間。所以點u代表的當前區(qū)間的子矩陣面積\(=h_u*siz_u\)（\(siz_u\)：u的子樹大小）。
dfs遞歸笛卡爾樹時傳入已減去的高度。
11.1.2.“闖關”問題
“通過第u關后解鎖第e_{u,i}關。關卡被解鎖一次后方可闖關。每關u有各自固定的通關難度d_u”
-
將關卡按照自身通關難度d_u從小到大排序。
-
隱式建立笛卡爾樹：依次遍歷排序后的關卡u：遍歷e_{u,i}：若d_{e_{u,i}}≤d_u并且點e_{u,i}和點u不聯(lián)通，則令點e_{u,i}的父親是點u。（雖然點u可能有多個兒子，但是不影響正確性。）
性質：
- 只考慮通關難度d_u，該樹是一個大根堆。
- 若能通過第u關，則點u的子樹內的關卡都能通過。若不能通過第fa_u關，則點u的子樹外的關卡都不能通過。
-
建樹后，在笛卡爾樹上使用樹上倍增或者樹鏈剖分預處理信息。
-
對于詢問“初始處于第s關”，在笛卡爾樹上，找到點s的最遠的能通關的祖先a，則最后總共能通過的關卡是點a的子樹內的關卡。
11.2.平衡二叉搜索樹
簡稱平衡樹。
適用條件：類似于線段樹，維護滿足結合律的信息，支持插入和刪除。
調試代碼利器——輸出中序遍歷（關鍵字序列）
void dfs(int u)//輸出子樹u的中序遍歷
{
if(!u) return ;
pushdown(u);
dfs(tr[u].kid[0]);
printf("%d\n",tr[u].key);
dfs(tr[u].kid[1]);
return ;
}
puts("Root:");dfs(root);
int x,y;
split(root,key,x,y);
puts("X:");dfs(x);
puts("Y:");dfs(y);
11.2.1.STL紅黑樹
《C++語言.2.3.有序集合set和有序多重集合multiset》《C++語言.2.4.有序映射map》
11.2.2.FHQ-Treap
類似于笛卡爾樹，每個節(jié)點有關鍵字key和校準值cor，key滿足二叉搜索樹的性質（在中序遍歷中key單調遞增/遞減）， y滿足小/大根堆的性質（當前節(jié)點的y小/大于其子節(jié)點的y）。校準值cor的隨機性保證樹高的期望是\(O(\log n)\)，從而保證期望復雜度。
懶標記操作信息沖突參考《數(shù)據(jù)結構·序列8.1.線段樹\(O(N\log N)\) 懶標記操作信息沖突》。
- 若要維護元素排序，則一般令關鍵字key為自身元素值。
- 若要維護序列順序，則一般不設置關鍵字key，節(jié)點的自身個數(shù)cnt是1，函數(shù)
split按子樹大小siz分裂，中序遍歷就是序列順序。
基礎代碼
split和merge的時間復雜度是\(O(\log n)\)，其他部分的時間復雜度一般是\(O(1)\)。
空間復雜度是\(O(n)\)。
mt19937_64 gen((random_device()())^chrono::system_clock::now().time_since_epoch().count());
//定義FHQ-Treap
int root,idx;
struct Fhq_Treap
{
int son[2];
ktype key;//關鍵字
unsigned long long cor;//校準值
int cnt,siz;//自身個數(shù)、子樹大小（包括自身的cnt）
vtype val,sum;//題目中詢問的內容，val是單點信息，sum是子樹信息
ttype tag;//懶標記
/*
先從query()分析屬性是否完全（即當前節(jié)點的信息能否由兒子節(jié)點的信息得到），不可以的話就根據(jù)需要增加其他屬性；
再從modify()分析屬性是否完全（即如何把這個區(qū)間上的每個數(shù)修改后得到整個區(qū)間的信息），不可以的話就根據(jù)需要增加其他屬性；
最后分析新建的屬性在query()和modify()的角度上是否完全。
*/
}tr[N];
//新建一個節(jié)點
int new_node(vtype val)
{
tr[++idx]={0,0,/*關鍵字key*/,gen(),1,1,val,val,0/*,……*/};
return idx;
}
//修改需要懶標記update_tag
//更新節(jié)點u關于懶標記tag的信息
void update_tag(int u,ttype tag)
{
if(!u) return ;//不要忘記！！！
//先給u的信息執(zhí)行tag操作
/*更新tr[u].key*/
tr[u].val+=tag;
tr[u].sum+=tag*tr[u].siz;
//再給u的懶標記加上tag
tr[u].tag+=tag;
return ;
}
//往下遞歸前pushdown
void pushdown(int u)
{
if(!u) return ;//不要忘記！！！
if(tr[u].tag)
{
update_tag(tr[u].son[0],tr[u].tag);
update_tag(tr[u].son[1],tr[u].tag);
tr[u].tag=0;
}
return ;
}
void pushup(int u)
{
if(!u) return ;//不要忘記！！！
/*更新tr[u].key*/
tr[u].siz=tr[tr[u].son[0]].siz+tr[u].cnt/*不要忘記*/+tr[tr[u].son[1]].siz;//不要忘記！！！
tr[u].sum=tr[tr[u].son[0]].sum+tr[u].val/*不要忘記*/+tr[tr[u].son[1]].sum;
return ;
}
//建樹，插入哨兵
void build()
{
int mi=new_node(-INF),ma=new_node(INF);
if(tr[mi].cor<=tr[ma].cor)
{
root=mi;
tr[mi].son[1]=ma;
pushup(mi);
}
else
{
root=ma;
tr[ma].son[0]=mi;
pushup(ma);
}
return ;
}
//函數(shù)split按關鍵字key分裂
//當key是單點信息（e.g.val）時
void split(int u,ktype key,int &x,int &y)
{
if(!u)
{
x=y=0;
return ;
}
pushdown(u);
if(tr[u].key<=key)
{
x=u;
split(tr[u].son[1],key,tr[u].son[1],y);
}
else
{
y=u;
split(tr[u].son[0],key,x,tr[u].son[0]);
}
pushup(u);
return ;
}
/*當key是子樹信息（e.g.sum）時
void split(int u,ktype key,int &x,int &y)
{
if(!u)
{
x=y=0;
return ;
}
pushdown(u);
if(tr[tr[u].son[0]].key+tr[u].val<=key)
{
x=u;
split(tr[u].son[1],key-(tr[tr[u].son[0]].key+tr[u].val),tr[u].son[1],y);
}
else
{
y=u;
split(tr[u].son[0],key,x,tr[u].son[0]);
}
pushup(u);
return ;
}
*/
/*函數(shù)split按子樹大小siz分裂，節(jié)點的自身個數(shù)cnt是1
void split(int u,int siz,int &x,int &y)
{
if(!u)
{
x=y=0;
return ;
}
pushdown(u);
if(tr[tr[u].son[0]].siz+1<=siz)
{
x=u;
split(tr[u].son[1],siz-(tr[tr[u].son[0]].siz+1),tr[u].son[1],y);
}
else
{
y=u;
split(tr[u].son[0],siz,x,tr[u].son[0]);
}
pushup(u);
return ;
}
*/
//每次merge都對應上一次的split，上一次的split保證了此次merge子樹p的中序遍歷是接在子樹q的中序遍歷的前面的
int merge(int u,int v)
{
//if(tr[u].key>tr[v].key) swap(u,v);//要保證tr[u].key<=tr[v].key。若在調用merge函數(shù)時已經(jīng)保證了，則無需此行代碼
if(!u || !v) return u|v;
if(tr[u].cor<=tr[v].cor)
{
pushdown(u);
tr[u].son[1]=merge(tr[u].son[1],v);
pushup(u);
return u;
}
else
{
pushdown(v);
tr[v].son[0]=merge(u,tr[v].son[0]);
pushup(v);
return v;
}
}
有序建樹\(O(n)\)
- 方法一
//O(n)建立要插入的區(qū)間的樹
//必須保證序列a是有序的！
//此處不需要保證校準值cor的小根堆性質，因為按照下面方式建樹的樹高本來就是O(log n)
int build(int l,int r)
{
if(l>r) return 0; //因為mid單獨新建，build(l,mid-1)，故要特判防止越界
if(l==r) return new_node(a[l]);
int mid=(l+r)>>1,u=new_node(a[mid]);
tr[u].son[0]=build(l,mid-1);
tr[u].son[1]=build(mid+1,r);
pushup(u);
return u;
}
int x,y;
split(root,key,x,y);
root=merge(x,merge(build(l,r),y));
- 方法二：笛卡爾樹建樹
遍歷子樹u\(O(n)\)
void dfs(int u)
{
if(!u) return ;
pushdown(u);//記得pushdown！！！
dfs(tr[u].son[0]);
print(u);//中序遍歷
dfs(tr[u].son[1]);
return ;
}
維護元素排序
令關鍵字key為自身元素值val。
- 插入一個元素val\(O(\log n)\)
void insert(vtype val)
{
int x,y,z;
//抽絲剝繭：把key對應的節(jié)點單獨分裂成z
//x,y,z的值傳入時無所謂，傳出時得到被分裂的子樹（該序列順序給出）x,z,y
split(root,val,x,y);
split(x,val-1,x,z);
if(!z) root=merge(merge(x,new_node(val)),y);//每次split之后都要root=merge()
else
{
tr[z].cnt++;
pushup(z);//更改了子樹z的cnt信息，記得pushup更新子樹z的siz信息！！！
root=merge(merge(x,z),y);
}
return ;
}
- 刪除一個元素val\(O(\log n)\)
void erase(vtype val)
{
int x,y,z;
split(root,val,x,y);
split(x,val-1,x,z);
if(--tr[z].cnt>0)
{
pushup(z);
root=merge(merge(x,z),y);
}
else root=merge(x,y);
return ;
}
-
查詢元素v的排名\(O(\log n)\)
注意哨兵。
int get_rank(vtype val)
{
int x,y;
split(root,val-1,x,y);
int rank=tr[x].siz+1;//注意要加上自己本身
root=merge(x,y);
return rank;
}
int rank=get_rank(val)-1;//-1：減去哨兵
-
查詢排名rank的元素\(O(\log n)\)
本質是平衡樹上二分。
注意哨兵。
vtype get_val(int rank)
{
int u=root;
while(true)
{
if(!u) return INF;
pushdown(u);//記得pushdown！！！
if(rank<=tr[tr[u].son[0]].siz) u=tr[u].son[0];
else if(rank<=tr[tr[u].son[0]].siz+tr[u].cnt) return tr[u].val;
else
{
rank-=tr[tr[u].son[0]].siz+tr[u].cnt;
u=tr[u].son[1];
}
}
}
vtype val=get_val(rank+1);//+1：排除哨兵
- 查詢元素val的前驅或者后繼\(O(\log n)\)
vtype get_prev(vtype val)
{
int x,y;
split(root,val-1,x,y);
int u=x;
while(tr[u].son[1])
{
pushdown(u);//記得pushdown！！！
u=tr[u].son[1];//子樹x的最大值一定是一直往右子樹走
}
root=merge(x,y);
return tr[u].val;
}
vtype get_next(vtype val)
{
int x,y;
split(root,val,x,y);
int u=y;
while(tr[u].son[0])
{
pushdown(u);//記得pushdown！！！
u=tr[u].son[0];//子樹y的最小值一定是一直往左子樹走
}
root=merge(x,y);
return tr[u].val;
}
（中序遍歷的）區(qū)間[l,r]操作\(O(\log n)\)
需要滿足節(jié)點的自身個數(shù)cnt是1。
int x,y,z;
split(root,l-1,x,y);//函數(shù)split按子樹大小siz分裂
split(y,r-l+1,y,z);
//刪除
root=merge(x,z);
//修改
update_tag(y,tag);
root=merge(x,merge(y,z));
//查詢
cout<<tr[y].sum<<'\n';
root=merge(x,merge(y,z));
平衡樹上二分\(O(\log n)\)
下面以“在[l,r]內查找從左到右開始滿足條件的下標，不存在返回r+1”為例。“在[l,r]內查找從左到右結束滿足條件的下標（從右到左開始）”把下面的先序遍歷改為后序遍歷即可。
int binary(int u)
{
int siz=0;
while(true)
{
if(!u) return siz;
pushdown(u);//記得pushdown！！！
if(check(/*節(jié)點u的左子樹*/)) u=tr[u].son[0];
else
{
siz+=tr[tr[u].son[0]].siz;
/*消除節(jié)點u的左子樹的影響*/
if(check(/*節(jié)點u*/)) return siz;
else
{
siz++;
/*消除節(jié)點u的影響*/
u=tr[u].son[1];
}
}
}
}
int x,y,z;
split(root,l-1,x,y);//函數(shù)split按子樹大小siz分裂
split(y,r-l+1,y,z);
int ans=l+binary(y);
root=merge(x,merge(y,z));
內存回收
int space[N],sidx;//內存回收站
//新建一個節(jié)點
int new_node(vtype val)
{
int i=(sidx==0 ? ++idx : space[sidx--]);
tr[i]={0,0,/*關鍵字key*/,gen(),1,1,val,val,0/*,……*/};
return i;
}
//回收被刪除的節(jié)點u
space[++sidx]=u;
//回收被刪除的子樹u
void delete_tree(int u)
{
space[++sidx]=u;
if(tr[u].son[0]) delete_tree(tr[u].son[0]);
if(tr[u].son[1]) delete_tree(tr[u].son[1]);
return ;
}
在第p個（要算上本身的個數(shù)cnt）元素后插入\(O(\log n)\)
split(root,p,p1,p2);
int k1=p-tr[p1].siz;
if(k1==0)
{
root=merge(p1,merge(new_fhq(a,b,c,x),p2));
}
else
{
split(p2,tr[p2].lsiz,p2,p3);
p2=new_fhq(tr[p2].a,tr[p2].b,tr[p2].c,tr[p2].siz-k1);
p4=new_fhq(tr[p2].a,tr[p2].b,tr[p2].c,k1),p5=new_fhq(a,b,c,x);
root=merge(p1,merge(p4,merge(p5,merge(p2,p3))));
}
-
例題一：替代Treap
![]()
//中序遍歷是按key排序，父節(jié)點的cor（correction校準值）必須小于等于子結點（也可以自己定義為大于等于）
int n;
int root,idx;
struct Fhq
{
int kid[2];//左右兒子的下標
int key,cor,cnt,size;//關鍵字、校準值、本身個數(shù)、子樹大小（包含本身的cnt）
}tr[N];
int new_node(int key)
{
tr[++idx]={0,0,key,rand(),1,1};
return idx;
}
void pushup(int p)
{
tr[p].size=tr[tr[p].kid[0]].size+tr[tr[p].kid[1]].size+tr[p].cnt;
return ;
}
void build()
{
int mi=new_node(-INF),ma=new_node(INF);
if(tr[mi].cor<tr[ma].cor)
{
root=mi;
tr[mi].kid[1]=ma;
pushup(mi);
}
else
{
root=ma;
tr[ma].kid[0]=mi;
pushup(ma);
}
return ;
}
//按key分裂
//把當前的子樹分裂成子樹xx和yy，且分裂后子樹xx代表的序列是[-INF,key]，子樹yy代表的序列是[key+,INF]，相當于把原序列以key為依據(jù)分裂成兩部分
//傳引用使得后面可以merge(xx,yy)
void split(int p,int key,int &xx,int &yy)
{
if(p==0)//不要忘記！！！
{
xx=yy=0;
return ;
}
if(tr[p].key<=key)
{
//此時把p丟到左邊的xx，去右子樹tr[p].kid[1]繼續(xù)分裂
xx=p;
split(tr[p].kid[1],key,tr[p].kid[1],yy);//注意這里的順序：遞歸時仍要用到當前的yy
}
else
{
yy=p;
split(tr[p].kid[0],key,xx,tr[p].kid[0]);
}
pushup(p);//記得pushup！！！
return ;
}
//每次merge都對應上一次的split，上一次的split保證了此次merge子樹p的中序遍歷是接在子樹q的中序遍歷的前面的
int merge(int p,int q)
{
//if(tr[p].key>tr[q].key) swap(p,q);//要保證tr[p].key<tr[q].key。若在調用merge函數(shù)時已經(jīng)保證了，則無需此行代碼
if(p==0 || q==0) return p|q;
if(tr[p].cor<=tr[q].cor)//保證父節(jié)點的cor必須小于等于子結點
{
tr[p].kid[1]=merge(tr[p].kid[1],q);
pushup(p);//記得pushup！！！
return p;
}
tr[q].kid[0]=merge(p,tr[q].kid[0]);
pushup(q);
return q;
}
void insert(int key)
{
int x,y,z;
//抽絲剝繭：把key對應的節(jié)點單獨分裂成z
//x,y,z的值傳入時無所謂，傳出時得到被分裂的子樹（該序列順序給出）x,z,y
split(root,key,x,y);
split(x,key-1,x,z);
if(z==0) root=merge(merge(x,new_node(key)),y);//每次split之后都要root=merge()
else
{
tr[z].cnt++;
pushup(z);//更改了子樹z的cnt信息，記得pushup更新子樹z的siz信息！！！
root=merge(merge(x,z),y);
}
return ;
}
void deletee(int key)
{
int x,y,z;
split(root,key,x,y);
split(x,key-1,x,z);
if(--tr[z].cnt>0)
{
pushup(z);
root=merge(merge(x,z),y);
}
else root=merge(x,y);
return ;
}
int get_rank(int key)
{
int x,y;
split(root,key-1,x,y);
int res=tr[x].siz+1;//注意要加上自己本身
root=merge(x,y);
return res;
}
int get_key(int p,int rank)
{
while(true)
{
if(p==0) return INF;
if(rank<=tr[tr[p].kid[0]].siz) p=tr[p].kid[0];
else if(rank<=tr[tr[p].kid[0]].siz+tr[p].cnt) return tr[p].key;
else
{
rank-=tr[tr[p].kid[0]].siz+tr[p].cnt;
p=tr[p].kid[1];
}
}
}
int get_prev(int key)
{
int x,y;
split(root,key-1,x,y);
int u=x;
while(tr[u].kid[1]) u=tr[u].kid[1];//子樹x的最大值一定是一直往右子樹走
root=merge(x,y);
return tr[u].key;
}
int get_next(int key)
{
int x,y;
split(root,key,x,y);
int u=y;
while(tr[u].kid[0]) u=tr[u].kid[0];//子樹y的最小值一定是一直往左子樹走
root=merge(x,y);
return tr[u].key;
}
int main()
{
scanf("%d",&n);
build();
int op,xx;
while(n--)
{
scanf("%d%d",&op,&xx);
if(op==1) insert(xx);
else if(op==2) deletee(xx);
else if(op==3) printf("%d\n",get_rank(xx)-1);//-1：減去哨兵
else if(op==4) printf("%d\n",get_key(root,xx+1));//+1：排除哨兵
else if(op==5) printf("%d\n",get_prev(xx));
else printf("%d\n",get_next(xx));
}
return 0;
}
-
例題二：替代Splay
![]()
#define ls tr[p].kid[0]
#define rs tr[p].kid[1]
const int N=5e5+5;
int n,m,root;
int a[N];
int idx;
struct Fhq
{
int kid[2];
int key,cor,siz;
int sum,fro,bac,seg; //sum：子樹總和；fro：以子樹區(qū)間左端點作為左端點的子段最大和；bac：以子樹區(qū)間右端點作為右端點的子段最大和；seg：子樹子段最大和
int sam,rev; //改值、翻轉懶標記
}tr[N];
int spa[N],sidx; //內存回收站
int new_fhq(int key)
{
int i= sidx==0 ? ++idx : spa[sidx--];
tr[i]=(Fhq){0,0,key,rand(),1,key,max(key,0),max(key,0),key/*子樹只有一個點，則key必選不可*/,0,0};
return i;
}
void cover(int p,int c)
{
if(p==0) return ;//不要忘記！！！
tr[p].sam=1,tr[p].key=c,tr[p].sum=c*tr[p].siz;
if(c>=0) tr[p].seg=tr[p].sum,tr[p].fro=tr[p].bac=tr[p].sum;
else tr[p].seg=c/*不得不選1個*/,tr[p].fro=tr[p].bac=0;
return ;
}
void reverse(int p)
{
if(p==0) return ;//不要忘記！！！
tr[p].rev^=1;
swap(tr[p].fro,tr[p].bac); //不要忘記！！！
swap(ls,rs);
return ;
}
void pushup(int p)
{
tr[p].siz=tr[ls].siz+tr[rs].siz+1;
tr[p].sum=tr[ls].sum+tr[rs].sum+tr[p].key;
tr[p].fro=max(tr[ls].fro,max(tr[ls].sum+tr[p].key,tr[ls].sum+tr[p].key+tr[rs].fro));
tr[p].bac=max(tr[rs].bac,max(tr[p].key+tr[rs].sum,tr[ls].bac+tr[p].key+tr[rs].sum));
tr[p].seg=max(tr[ls].bac+tr[p].key+tr[rs].fro,max(tr[ls].seg,tr[rs].seg));
return ;
}
void pushdown(int p)
{
if(p==0) return ;//不要忘記！！！
if(tr[p].sam!=0)
{
cover(ls,tr[p].key);
cover(rs,tr[p].key);
tr[p].sam=0;
}
if(tr[p].rev!=0)
{
reverse(ls);
reverse(rs);
tr[p].rev=0;
}
return ;
}
//O(N)建立要插入的區(qū)間的樹
//必須保證序列a是有序的！
//此處不需要保證cor的小根堆性質，因為按照這樣建樹樹高本來就是log的
int build(int l,int r)
{
if(l>r) return 0; //因為mid單獨新建，build(l,mid-1)，故要特判防止越界
if(l==r) return new_fhq(a[l]);
int mid=(l+r)>>1,p=new_fhq(a[mid]);
ls=build(l,mid-1);
rs=build(mid+1,r);
pushup(p);
return p;
}
//按siz分裂
void split(int p,int siz,int &x,int &y)
{
if(p==0)
{
x=y=0;
return ;
}
pushdown(p);
if(tr[ls].siz+1/*注意是左子樹+本身節(jié)點的大小，而不是整棵子樹tr[p].siz的大小*/<=/*注意要取等*/siz)
{
x=p;
split(rs,siz-tr[ls].siz-1/*去右子樹找記得減去左子樹+本身節(jié)點的大小*/,rs,y);
}
else
{
y=p;
split(ls,siz,x,ls);
}
pushup(p);
return ;
}
int merge(int p,int q)
{
if(p==0 || q==0) return p|q;
if(tr[p].cor<=tr[q].cor)
{
pushdown(q);
tr[q].kid[0]=merge(p,tr[q].kid[0]);
pushup(q);
return q;
}
pushdown(p);
tr[p].kid[1]=merge(tr[p].kid[1],q);
pushup(p);
return p;
}
void deletee(int p)
{
spa[++sidx]=p;
if(ls!=0) deletee(ls);
if(rs!=0) deletee(rs);
return ;
}
//遍歷子樹u的區(qū)間
void dfs(int u)
{
if(!u) return ;
pushdown(u);//記得pushdown！！！
dfs(tr[u].kid[0]);
printf("%d ",tr[u].key);
dfs(tr[u].kid[1]);
return ;
}
int main()
{
int x,y,z;
tr[0].seg=-2e9;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
root=build(1,n);
while(m--)
{
int p,t,c;
char op[10];
scanf("%s",op);
//在第p個數(shù)字后插入t個數(shù)字
if(op[0]=='I')
{
scanf("%d%d",&p,&t);
split(root,p,x,y);
for(int i=1;i<=t;i++) scanf("%d",&a[i]);
root=merge(x,merge(build(1,t),y));
}
//從第p個數(shù)字開始刪除t個數(shù)字
else if(op[0]=='D')
{
scanf("%d%d",&p,&t);
split(root,p-1,x,y);
split(y,t,z,y);
deletee(z);
root=merge(x,y);
}
//從第p個數(shù)字開始連續(xù)t個數(shù)字修改為c
else if(op[0]=='M' && op[2]=='K')
{
scanf("%d%d%d",&p,&t,&c);
split(root,p-1,x,y);
split(y,t,z,y);
cover(z,c);
root=merge(x,merge(z,y));
}
//從第p個數(shù)字開始連續(xù)t個數(shù)字翻轉
else if(op[0]=='R')
{
scanf("%d%d",&p,&t);
split(root,p-1,x,y);
split(y,t,z,y);
reverse(z);
root=merge(x,merge(z,y));
}
//輸出從第p個數(shù)字開始連續(xù)t個數(shù)字的總和
else if(op[0]=='G')
{
scanf("%d%d",&p,&t);
split(root,p-1,x,y);
split(y,t,z,y);
printf("%d\n",tr[z].sum);
root=merge(x,merge(z,y));
}
//輸出數(shù)列最大子段和
else printf("%d\n",tr[root].seg);
}
return 0;
}
11.2.3.Splay
3要素:
\(1.\)每操作一個節(jié)點，均將該節(jié)點旋轉至樹根。
z 右旋 z
/ ---> /
y <--- x
/\ 左旋 /\
x c a y
/\ /\
a b b c
\(2.\)核心操作splay(x,k)：將點x旋轉至點k的下面。（將點x旋轉至根：splay(x,0)）
先轉y再轉x： 先轉x再轉x：
z z
/ /
y y
/ \
x x
splay(x,k)維護信息：I.插入x：先往下搜索找到空節(jié)點插入x，再splay(x,0)；II.將一個序列插到y(tǒng)的后面：先找到y(tǒng)的后繼z，再splay(y,0)，再splay(z,y)，此時z的左兒子一定是空節(jié)點，再將x成為z的左兒子；III.刪除[l,r]：先splay(l-1,0)，再splay(r+1,l-1)，再刪除左子樹。
\(3.\)splay如何維護信息？
I.查詢第k大：size
void pushup(int u)//旋轉之后調用，用于維護信息
{
u.size=u.l.size+u.r.size+1;
return ;
}
II.翻轉區(qū)間：懶標記
void pushdown(int u)//往下遞歸之前調用，用于下傳懶標記
{
swap(u.l,u.r);
//將懶標記下傳
return ;
}
splay保證中序遍歷是當前序列的順序。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
struct Node
{
int s[2]; //左兒子和右兒子：用0和1表示方便真值表達式判斷
int p,v; //p：父節(jié)點；v：當前節(jié)點的值
int size,flag; //size：；flag：懶標記：是否要翻轉，用int取反方便排除偶數(shù)次翻轉仍為原序列的情況
void init(int _v,int _p)
{
v=_v,p=_p;
size=1;
}
}tr[N];
int root,idx; //root：當前splay的根節(jié)點；idx：splay的指針
//更新后需要pushup
void pushup(int u) //更新信息
{
tr[u].size=tr[tr[u].s[0]].size+tr[tr[u].s[1]].size+1; //注意還要加上u本身的節(jié)點
return ;
}
//查詢前需要pushdown
void pushdown(int u) //維護信息，翻轉操作
{
if(tr[u].flag)
{
swap(tr[u].s[0],tr[u].s[1]);
tr[tr[u].s[0]].flag^=1;
tr[tr[u].s[1]].flag^=1;
tr[u].flag=0;
}
return ;
}
int dir(int u) //direction：輔助判斷方向一致性
{
return tr[tr[u].p].s[1]==u;
}
void rotate(int x) //左旋+右旋
{
int y=tr[x].p,z=tr[y].p;
int tx = dir(x), ty = dir(y);//注意這里一定要用一個變量存儲，否則當下面改變父子關系時再調用dir會得到錯誤的信息
tr[y].s[tx]=tr[x].s[tx^1],tr[tr[x].s[tx^1]].p=y;
tr[x].s[tx^1]=y,tr[y].p=x;
tr[x].p=z;if(z) tr[z].s[ty]=x;
pushup(y),pushup(x);
return ;
}
//遞歸子樹時保證復雜度需要splay(u,0)
void splay(int u,int k) //核心，將節(jié)點u旋轉至節(jié)點k的兒子
{
while(tr[u].p!=k)
{
int v=tr[u].p,w=tr[v].p;
if (w!=k)
if (dir(v)^dir(u)) rotate(u);
else rotate(v);
rotate(u);
}
if(!k) root=u;
return ;
}
void insert(int val) //插入
{
int u=root,p=0;
while(u)
{
p=u;
u=tr[u].s[val>tr[u].v];
}
u=++idx; //一定能找到空節(jié)點
if(p) tr[p].s[val>tr[p].v]=u;
tr[u].init(val,p);
splay(u,0);
return ;
}
int get_k(int rank) //獲得排名為rank的節(jié)點的下標
{
int u=root;
while(true)
{
pushdown(u);
if(tr[tr[u].s[0]].size>=rank) u=tr[u].s[0];
else if(tr[tr[u].s[0]].size+1==rank) return u;
else rank-=tr[tr[u].s[0]].size+1,u=tr[u].s[1];
}
return -1;
}
void reverse(int l,int r) //翻轉懶標記
{
l=get_k(l); //獲得排名為l-1的節(jié)點的下標
r=get_k(r+2); //獲得排名為r+1的節(jié)點的下標
splay(l,0); //此處splay作用不是保證復雜度
splay(r,l); //此處splay作用不是保證復雜度
tr[tr[r].s[0]].flag^=1;
return ;
}
void print(int u) //輸出
{
pushdown(u);
if(tr[u].s[0]) print(tr[u].s[0]);
if(1<=tr[u].v && tr[u].v<=n) printf("%d ",tr[u].v); //防止輸出哨兵
if(tr[u].s[1]) print(tr[u].s[1]);
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n+1;i++) {
insert(i); //加入0和n+1哨兵
}
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
reverse(l,r);
}
print(root);
return 0;
}
11.2.4.樹套樹
樹套樹可以被分成外層樹和內層樹。外層樹常見的有線段樹和樹狀樹組（平衡樹少見），內層樹常見的有平衡樹和（線段樹少見）。當然了，有些時候內層的樹可以用 STL? 來代替。
\(e.g.\)下標線段樹，值域平衡樹。
判斷平衡樹能不能用 STL? 水過的方式很簡單：我們只需要判斷一下，假設這棵平衡樹手寫的話，需不需要給每個點都維護一個 size? 的信息。如果不需要，就可以用 STL? 水過；如果需要（比如查詢排名），就只能手寫。
12.可持久化數(shù)據(jù)結構
可持久化的原則：用新建代替修改，盡量復用空間，節(jié)點指向保持正確。
12.1.可持久化Tire
p：前一個tire，q：當前新建的tire。
q節(jié)點復制節(jié)點p的信息，在節(jié)點q新建新的信息，然后p和q各自往同一個方向走。
以下面為例：
A x：添加操作，表示在序列末尾添加一個數(shù) \(x\)，序列的長度 \(N\) 增大 \(1\)。Q l r x：詢問操作，你需要找到一個位置 \(p\)，滿足 \(l≤p≤r\)，使得：\(a[p] \operatorname{xor} a[p+1] \operatorname{xor} … \operatorname{xor} a[N] \operatorname{xor} x\) 最大，輸出這個最大值。
方法一：可持久化01Tire\(O(N\log N)\)
優(yōu)點：復雜度更低。
int n,m;
int s[N];
int tr[M][2],max_id[M];
int root[N],idx;
void insert(int id,int k,int p,int q)
{
if(k<0)
{
max_id[q]=id;
return ;
}
int v=s[id]>>k&1;
if(p) tr[q][v^1]=tr[p][v^1];
tr[q][v]=++idx;
insert(id,k-1,tr[p][v],tr[q][v]);
max_id[q]=max(max_id[tr[q][0]],max_id[tr[q][1]]);
return ;
}
int query(int root,int num,int l)
{
int p=root;
for(int k=23;k>=0;k--)
{
int v=num>>k&1;
if(max_id[tr[p][v^1]]>=l) p=tr[p][v^1];
else p=tr[p][v];
}
return num^s[max_id[p]];//最終的答案就是第max_id[p]個數(shù)
}
int main()
{
scanf("%d%d",&n,&m);
max_id[0]=-1;
root[0]=++idx;
insert(0,23,0,root[0]);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
s[i]=s[i-1]^x;
root[i]=++idx;
insert(i,23,root[i-1],root[i]);
}
while(m--)
{
int l,r,x;
char op[2];
scanf("%s",op);
if(op[0]=='A')
{
scanf("%d",&x);
n++;
s[n]=s[n-1]^x;
root[n]=++idx;
insert(n,23,root[n-1],root[n]);
}
else
{
scanf("%d%d%d",&l,&r,&x);
printf("%d\n",query(root[r-1],s[n]^x,l-1));
}
}
return 0;
}
方法二：01Tire思想+可持久化線段樹\(O(N\log^2 N)\)
優(yōu)點：適用范圍廣，可以解決更多的約束條件。
值域線段樹也可以實現(xiàn)01Trie樹的作用：《數(shù)據(jù)結構·字符串和圖1.2.2.1.求a xor b_i的最值 方法二：01Tire思想+值域線段樹O(N\log^2 N)》。
加上區(qū)間的限制，使用可持久化線段樹。
12.2.可持久化線段樹（主席樹）
適用條件：二維問題。
可持久化線段樹用葉子節(jié)點維護一維a，用版本維護滿足可逆性（可加減性）的一維b的前綴和：可以理解為b個維護a的線段樹，第b個線段樹是前b個維護a的原線段樹的信息前綴和線段樹。但是空間復雜度是\(O(A\log B)\)
解題思路：思考如何用“對于每個維度b的前綴建立維護維度a的線段樹”來解決原問題。
p：在版本p上建立當前版本，q：當前版本。
類似于動態(tài)開點新建一個節(jié)點q，節(jié)點q復制節(jié)點p的信息，隨著p往下走在節(jié)點q新建新的信息。
空間開大一些（\(e.g.\)50倍），但注意空間限制。
如果插入的值離散化了，則主席樹的值域也是離散化后的值域。
主席樹不能支持對舊版本的修改。
復雜度：\(O(N\log N)\)。
12.2.1.一維值域一維下標/一維信息的前綴和
適用條件：求區(qū)間內與數(shù)值有關的問題（\(e.g.\)第k小）。
做一維信息的前綴和，使用二維樹狀數(shù)組，空間復雜度是\(O(N^2)\)；而使用可持久化線段樹，空間復雜度是\(O(N\log N)\)。
可持久化線段樹做好了一維信息的前綴和，區(qū)間問題就很好解決了。
下面以靜態(tài)在線求區(qū)間第k小數(shù)為例：
給定長度為n的整數(shù)序列a，求a的區(qū)間[l,r]第k小數(shù)。
先考慮全局第k小數(shù)：建立值域線段樹，線段樹維護當前區(qū)間所包含數(shù)的個數(shù)siz。對于一個詢問k，如果k≤siz，往左兒子找；否則令k-=siz，往右兒子找。直至l==r。
再考慮區(qū)間第k小數(shù)：想象對于每個下標前綴建立值域線段樹。使用可持久化，因為區(qū)間具有前綴和的性質，所以tr[q].siz-tr[p-1].siz表示區(qū)間[p,q]的數(shù)。實現(xiàn)區(qū)間查詢。
int n,m,tot;
int a[N];
vector<int> num;
int root[N],idx;
struct Chairman //區(qū)間左右端點由函數(shù)中l(wèi)和r決定
{
int lson,rson; //lson：左兒子的編號（注意不是區(qū)間左端點）；rson：右兒子的編號；
int siz; //當前區(qū)間所包含數(shù)的個數(shù)
}tr[N*50];
int Hash(int x)
{
return lower_bound(num.begin(),num.end(),x)-num.begin();
}
void pushup(int u)
{
tr[u].siz=tr[tr[u].lson].siz+tr[tr[u].rson].siz;
return ;
}
int change(int p,int l,int r,int x,int sign)//sign：1：插入；-1：刪除
{
int q=++idx; //類似于動態(tài)開點
tr[q]=tr[p]; //復制上一個節(jié)點的信息，注意葉子節(jié)點也要繼承p的siz
if(l==r)
{
tr[q].siz+=sign;
return q;
}
//新建
int mid=(l+r)>>1;
if(x<=mid) tr[q].lson=change(tr[p].lson,l,mid,x,sign);
else tr[q].rson=change(tr[p].rson,mid+1,r,x,sign);
pushup(q);
return q;
}
//tr[q].siz-tr[p].siz：因為區(qū)間具有前綴和的性質，所以表示區(qū)間[p+1,q]的數(shù)
int query(int p,int q,int l,int r,int k)
{
if(tr[q].siz-tr[p].siz<k) return -1;
if(l==r) return num[l];
int mid=(l+r)>>1,lsiz=tr[tr[q].lson].siz-tr[tr[p].lson].siz;
if(k<=lsiz) return query(tr[p].lson,tr[q].lson,l,mid,k);
else return query(tr[p].rson,tr[q].rson,mid+1,r,k-lsiz);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
num.push_back(a[i]);
}
sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());
tot=num.size();
root[0]=0;
for(int i=1;i<=n;i++) root[i]=change(root[i-1],0,tot-1,Hash(a[i]),1);
while(m--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",query(root[l-1],root[r],0,tot-1,k));
}
return 0;
}
12.2.2.一維值域一維時間
適用條件：求解2個所含元素不連續(xù)的集合的交。
核心：root[i]和root[j]對應著連續(xù)的可持久化/時間順序[i,j]，將原問題（\(e.g.\)區(qū)間）的一維排序另一維轉化為可持久化的時間順序。
因此注意插入要按順序插入！
下面以求兩個子樹交集為例：
-
給兩個集合內的元素分別內部定序，使得其在各自的集合內部連續(xù)。
先用dfs序把一個子樹集合的不連續(xù)的點編號轉化為連續(xù)的點編號。
-
建立兩個集合之間的映射關系。
建立一個映射f，使得對于任何一個點u，它的第一個dfs序為\(dfs_{1,u}\)，第二個dfs序為\(dfs_{2,u}\)，映射f:\(dfs_2→dfs_1\)。
如此，通過映射f，將連續(xù)的\(dfs_2\)映射為不連續(xù)的\(dfs_1'\)。接下來只需要求不連續(xù)的\(dfs_1'\)和連續(xù)的\(dfs_1\)即可。
-
線段樹葉子節(jié)點按照定的序維護映射過來的一維（形成連續(xù)），按照定的序依次插入映射出去的一維（利用時間形成連續(xù)）。
利用時間順序將不連續(xù)的\(dfs_1'\)轉化為連續(xù)的。建立起一棵主席樹，然后按\(dfs_2\)的順序插入\(f(dfs_2)=dfs_1'\)，這樣通過可持久化/時間上的連續(xù)，查詢前面連續(xù)的\(dfs_1\)和其的交集就是很簡單的事了，因為兩部分都是連續(xù)的，非常好處理。
//數(shù)組1（2）：第1（2）個子樹的數(shù)組
//id[u]:原圖的點u->dfs序i；nid[i]：dfs序i->原圖的點u；siz[u]：子樹u的大小
for(int i=1;i<=n;i++) f[nid1[i]]=i;
for(int i=1;i<=n;i++) root[i]=insert(root[i-1],root[i],1,n,f[nid2[i]]);
int u1,u2;
scanf("%d%d",&u1,&u2);
query(root[id2[u2]-1],root[id2[u2]+siz2[u2]-1],1,n,id1[u1],id1[u1]+siz1[u1]-1)
12.2.3.可持久化并查集
本質上是 維護的信息是按秩合并查集 的 可持久化線段樹。
12.3.可持久化FHQ-Treap
核心操作copy()的內容
可持久化\(Fhq\)就比普通平衡樹多在當“修改”某個節(jié)點之前，先copy()該節(jié)點，再在這個新節(jié)點上修改。
copy()很簡單，就是建立新節(jié)點，并且讓它的信息和原節(jié)點一樣
int copy(int p)//很簡單，就是建立新節(jié)點，并且讓它的信息和原節(jié)點一樣
{
tr[++idx]=tr[p];
return idx;
}
//現(xiàn)在要對點p進行修改change()
int q=copy(p);
change(q);
copy()的使用
為什么copy()之后不需要管原節(jié)點呢？
類似于可持久化線段樹，可持久化的原則就是：用新建代替修改，盡量復用空間，節(jié)點指向保持正確。
怎么樣的“修改”需要copy()呢？
在舊版本上，中序遍歷的修改+值的修改，得到新版本。
-
split()中的修改必須
copy()。現(xiàn)在就很像可持久化線段樹，一路新建到待修改的葉子節(jié)點。
-
merge()有時必須有時不需要copy()。
不需要copy()的時候copy()其實也不會出錯，只不過常數(shù)會大。
-
對節(jié)點的值的直接修改必須copy()。
-
pushup()不必copy()。
因為split()中一定會執(zhí)行pushup()，而split()又已經(jīng)copy()過了，直接在新版本上修改就可以了。
-
pushdown()中的eval()必須copy()。
首先中序遍歷或值會被修改，懶標記實際含義是本來在下放時就應該copy()，但是拖到現(xiàn)在才來copy()；其次split()中不一定會執(zhí)行pushdown()（不一定有懶標記）；再者split()新建的是當前節(jié)點，而eval()新建的是當前節(jié)點的子節(jié)點。
重構
前提條件：舊版本的信息是無用的，每時每刻只會用到最新版本。
適用條件：需要卡空間。
設置閾值。當節(jié)點數(shù)超過閾值時，dfs求出中序遍歷（注意pushdown），把節(jié)點數(shù)和根節(jié)點歸零，利用求出的中序遍歷建立新樹。重構一次的復雜度\(O(N)\)。
閾值越大，時間越小，空間越大。注意設置閾值時要預留\(>O(2*N\log N)\)的空間，因為1.前后判斷閾值之間的操作會復制節(jié)點；2.dfs要pushdown會復制節(jié)點。
應用
-
實現(xiàn)區(qū)間復制操作。
copy l1 r1 l2 r2：把區(qū)間[l1,r1]復制到[l2,r2]。
int x1,x2,x3,x4,x5;
split(root,l1-1,x1,x2);
split(x2,r1-l1+1,x2,x3);
if(r1<l2)
{
split(x3,l2-r1-1,x3,x4);
split(x4,r2-l2+1,x4,x5);
x4=copy(x2);
x3=merge(x3,merge(x4,x5));
}
else
{
split(x1,l2-1,x1,x4);
split(x4,r2-l2+1,x4,x5);
x4=copy(x2);
x1=merge(x1,merge(x4,x5));
}
root=merge(x1,merge(x2,x3));
注意，此時split等函數(shù)仍然需要copy，否則后續(xù)本來只修改[l1,r1]卻會連帶地把[l2,r2]一起修改。
區(qū)間復制的應用：把原序列[l1,r1]與[l2,r2]（**2個區(qū)間可能有重疊**）拼接在一起得到新序列。
時間復雜度：\(O(N\log N)\)。空間復雜度：\(O(c\times N\log N)\)，c是大常數(shù)。
以例題為例：
int n,m,ans;
int a[N],aidx;
int root,idx;
struct Fhq
{
int kid[2];
int key,sum,siz;
int cov,add;
bool rev;
int cor;
}tr[3000000];
int new_fhq(int key)
{
tr[++idx]={0,0,key,key,1,-1,0,false,rand()};
return idx;
}
int copy(int p)
{
if(!p) return 0;
tr[++idx]=tr[p];
return idx;
}
void cover(int p,int cov)
{
if(!p || cov==-1) return ;
tr[p].key=cov;
tr[p].sum=1ll*tr[p].siz*cov%MOD;
tr[p].add=0;
tr[p].cov=cov;
return ;
}
void add(int p,int add)
{
if(!p || add==0) return ;
tr[p].key=(1ll*tr[p].key+add)%MOD;
tr[p].sum=(tr[p].sum+1ll*tr[p].siz*add%MOD)%MOD;
tr[p].add=(1ll*tr[p].add+add)%MOD;
return ;
}
void reverse(int p,bool rev)
{
if(!p || !rev) return ;
swap(tr[p].kid[0],tr[p].kid[1]);
tr[p].rev^=1;
return ;
}
int eval(int p,int fa)
{
if(!p) return 0;
int q=copy(p);
if(tr[fa].cov!=-1) cover(q,tr[fa].cov);
if(tr[fa].add!=0) add(q,tr[fa].add);
if(tr[fa].rev) reverse(q,tr[fa].rev);
return q;
}
void pushdown(int p)
{
if(!p) return ;
if(tr[p].kid[0]) tr[p].kid[0]=eval(tr[p].kid[0],p);
if(tr[p].kid[1]) tr[p].kid[1]=eval(tr[p].kid[1],p);
tr[p].cov=-1,tr[p].add=0,tr[p].rev=false;
return ;
}
void pushup(int p)
{
tr[p].sum=(1ll*tr[tr[p].kid[0]].sum+tr[p].key+tr[tr[p].kid[1]].sum)%MOD;
tr[p].siz=tr[tr[p].kid[0]].siz+1+tr[tr[p].kid[1]].siz;
return ;
}
int build(int l,int r)
{
if(l>r) return 0;
if(l==r) return new_fhq(a[l]);
int mid=(l+r)>>1;
int p=new_fhq(a[mid]);
tr[p].kid[0]=build(l,mid-1);
tr[p].kid[1]=build(mid+1,r);
pushup(p);
return p;
}
void dfs(int p)
{
if(!p) return ;
pushdown(p);
dfs(tr[p].kid[0]);
a[++aidx]=tr[p].key;
dfs(tr[p].kid[1]);
return ;
}
void split(int p,int siz,int &x,int &y)
{
if(!p)
{
x=y=0;
return ;
}
pushdown(p);
if(tr[tr[p].kid[0]].siz+1<=siz)
{
x=copy(p);
split(tr[x].kid[1],siz-(tr[tr[x].kid[0]].siz+1),tr[x].kid[1],y);
pushup(x);
}
else
{
y=copy(p);
split(tr[y].kid[0],siz,x,tr[y].kid[0]);
pushup(y);
}
return ;
}
int merge(int p,int q)
{
if(!p || !q) return p|q;
int u;
if(tr[p].cor<=tr[q].cor)
{
pushdown(q);
u=copy(q);
tr[u].kid[0]=merge(p,tr[u].kid[0]);
}
else
{
pushdown(p);
u=copy(p);
tr[u].kid[1]=merge(tr[u].kid[1],q);
}
pushup(u);
return u;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
root=build(1,n);
while(m--)
{
int op=read(),l1=read(),r1=read();
int x1,x2,x3,x4,x5;
split(root,l1-1,x1,x2);
split(x2,r1-l1+1,x2,x3);
if(op==1)
{
ans=tr[x2].sum;
printf("%d\n",ans);
}
else if(op==2)
{
int k=read();
x2=copy(x2);
cover(x2,k);
}
else if(op==3)
{
int k=read();
x2=copy(x2);
add(x2,k);
}
else if(op==4)
{
int l2=read(),r2=read();
if(r1<l2)
{
split(x3,l2-r1-1,x3,x4);
split(x4,r2-l2+1,x4,x5);
x4=copy(x2);
x3=merge(x3,merge(x4,x5));
}
else
{
split(x1,l2-1,x1,x4);
split(x4,r2-l2+1,x4,x5);
x4=copy(x2);
x1=merge(x1,merge(x4,x5));
}
}
else if(op==5)
{
int l2=read(),r2=read();
if(r1<l2)
{
split(x3,l2-r1-1,x3,x4);
split(x4,r2-l2+1,x4,x5);
swap(x2,x4);
x3=merge(x3,merge(x4,x5));
}
else
{
split(x1,l2-1,x1,x4);
split(x4,r2-l2+1,x4,x5);
swap(x2,x4);
x1=merge(x1,merge(x4,x5));
}
}
else
{
x2=copy(x2);
reverse(x2,true);
}
root=merge(x1,merge(x2,x3));
if(idx>1700000)
{
aidx=0;
dfs(root);
idx=0;
root=build(1,n);
}
}
aidx=0;
dfs(root);
for(int i=1;i<=n;i++) printf("%d ",a[i]);
puts("");
return 0;
}
13.分治
前置知識：《2.5.遞歸實現(xiàn)分治》
13.1.離線分治算法
13.1.1.基于時間的分治算法
13.1.1.1.\(CDQ\)分治\(O(N\log^2 N)\)
13.1.1.1.1.三維偏序（靜態(tài)離線問題）
所有的\(CDQ\)問題都可以抽象為三維偏序。
給定 n 個元素（編號 1～n），其中第 i 個元素具有 ai,bi,ci 三種屬性。
設 f(i) 表示滿足以下 4 個條件：aj≤ai、bj≤bi、cj≤ci、j≠i的 j 的數(shù)量。
對于 d∈[0,n)，求滿足 f(i)=d 的 i 的數(shù)量。
第一維：直接按第一維排序；
第二維：在按第二維重新歸并排序時雙指針算法；
第三維：樹狀數(shù)組維護單點修改，區(qū)間查詢。
第三維的操作：在歸并排序時只計算左區(qū)間對右區(qū)間的貢獻。雙指針維護第二維滿足要求時，加入前綴和對后面的偏序都有貢獻；不滿足要求時，統(tǒng)計第三維的樹狀數(shù)組前綴和。
int n,k;
int ans[N];
struct Data
{
int a,b,c,cnt,res; //cnt：相等的個數(shù)；res：嚴格小于c的個數(shù)
bool operator < (const Data &t) const
{
if(a!=t.a) return a<t.a;
if(b!=t.b) return b<t.b;
return c<t.c;
}
bool operator == (const Data &t) const
{
return a==t.a && b==t.b && c==t.c;
}
}q[N],w[N];
int tr[M];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int val)
{
while(x<=k)
{
tr[x]+=val;
x+=lowbit(x);
}
return ;
}
int ask(int x)
{
int res=0;
while(x)
{
res+=tr[x];
x-=lowbit(x);
}
return res;
}
void cdq(int l,int r)
{
if(l>=r) return ;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
int i=l,j=mid+1,kk=l;
while(i<=mid && j<=r)
{
if(q[i].b<=q[j].b)
{
add(q[i].c,q[i].cnt);
w[kk]=q[i];
i++,kk++;
}
else
{
q[j].res+=ask(q[j].c);
w[kk]=q[j];
j++,kk++;
}
}
while(i<=mid)
{
add(q[i].c,q[i].cnt); //此處仍然add是為了下面刪除方便
w[kk]=q[i];
i++,kk++;
}
while(j<=r)
{
q[j].res+=ask(q[j].c);
w[kk]=q[j];
j++,kk++;
}
for(i=l;i<=mid;i++) add(q[i].c,-q[i].cnt); //清空樹狀數(shù)組
for(i=l;i<=r;i++) q[i]=w[i];
return ;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
q[i]={a,b,c,1};
}
sort(q+1,q+n+1);
int kk=1; //去重
for(int i=2;i<=n;i++)
if(q[i]==q[kk]) q[kk].cnt++;
else q[++kk]=q[i];
cdq(1,kk);
for(int i=1;i<=kk;i++) ans[q[i].res+q[i].cnt-1]+=q[i].cnt;
for(int i=0;i<n;i++) printf("%d\n",ans[i]);
return 0;
}
13.1.1.1.2.應用
13.1.1.1.2.1.靜態(tài)數(shù)點問題
適用條件：“給定若干個點后，多次詢問，每次詢問滿足x維條件的點的個數(shù)”
先修改再查詢：增加一個第x+1維\(\in 0,1\)表示該點是修改的點還是查詢的點。修改的點只貢獻查詢的點，查詢的點只尋找修改的點，因此第x+1維只需要排序時作為第x+1關鍵字，算法過程中判斷該點是修改的點還是查詢的點即可，不需要額外的數(shù)據(jù)結構維護第x+1維。
-
一維數(shù)點\(O(N\log N)\)
第一維：排序。
-
二維數(shù)點/二維平面矩形區(qū)域數(shù)點\(O(N\log N)\)
第一維：排序。
第二維：樹狀數(shù)組維護單點修改，區(qū)間查詢。
-
三維數(shù)點/二維平面特殊區(qū)域數(shù)點\(O(N\log^2 N)\)
CDQ分治。
-
二維平面特殊區(qū)域數(shù)點\(O(N\log N)\)
簡單容斥+二維數(shù)點。
-
多維數(shù)點
CDQ套CDQ/KD-tree。
int n,m;
LL ans[N];
struct Data
{
int x,y,z,p,id,sign;
LL sum;
bool operator < (const Data &t) const
{
if(x!=t.x) return x<t.x;
if(y!=t.y) return y<t.y;
return z<t.z;
}
}q[N],w[N];
void cdq(int l,int r)
{
if(l>=r) return ;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
int i=l,j=mid+1,k=l;
LL sum=0;
while(i<=mid && j<=r)
{
if(q[i].y<=q[j].y)
{
if(q[i].z==0) sum+=q[i].p;
w[k]=q[i];
i++,k++;
}
else
{
q[j].sum+=sum;
w[k]=q[j];
j++,k++;
}
}
while(i<=mid)
{
w[k]=q[i];
i++,k++;
}
while(j<=r)
{
q[j].sum+=sum;
w[k]=q[j];
j++,k++;
}
for(i=l;i<=r;i++) q[i]=w[i];
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
int x,y,p;
scanf("%d%d%d",&x,&y,&p);
q[i]={x,y,0,p};
}
int k=n;
for(int i=1;i<=m;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
q[++k]={x2,y2,1,0,i,1};
q[++k]={x1-1,y2,1,0,i,-1};
q[++k]={x2,y1-1,1,0,i,-1};
q[++k]={x1-1,y1-1,1,0,i,1};
}
sort(q+1,q+k+1);
cdq(1,k);
for(int i=1;i<=k;i++) if(q[i].z==1) ans[q[i].id]+=q[i].sign*q[i].sum;
for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
return 0;
}
\(2.\)動態(tài)二維問題
增加一個第三維\(t\)表示時間戳。倒序時間戳以方便前綴和。
以動態(tài)求逆序對為例：第一維度position可以省去，因為輸入數(shù)據(jù)已經(jīng)按position排序。設ans[t]為t時刻將該數(shù)刪除前，其他現(xiàn)存的數(shù)與該數(shù)構成的逆序對數(shù)量。將問題轉化為：ans[t]=\(p_i<p,a_i>a,t_i<t\)的三維偏序數(shù)+\(p_i>p,a_i<a,t_i<t\)的三維偏序數(shù)。(注意是嚴格小于)
int n,m;
int pos[N];
LL ans[N];
struct Data
{
int a,t,res;
}q[N],w[N];
int tr[N];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int val)
{
while(x<=n)
{
tr[x]+=val;
x+=lowbit(x);
}
return ;
}
int ask(int x)
{
int res=0;
while(x)
{
res+=tr[x];
x-=lowbit(x);
}
return res;
}
void cdq(int l,int r)
{
if(l>=r) return ;
int mid=(l+r)>>1;
cdq(l,mid);
cdq(mid+1,r);
//計算pi<pj,ai>aj的貢獻
int i=mid,j=r;
while(i>=l && j>=mid+1)
{
if(q[i].a>q[j].a) //注意題面要求的是嚴格小于
{
add(q[i].t,1);
i--;
}
else
{
q[j].res+=ask(q[j].t-1);
j--;
}
}
while(j>=mid+1)
{
q[j].res+=ask(q[j].t-1);
j--;
}
for(int k=i+1;k<=mid;k++) add(q[k].t,-1);
//計算pi>pj,ai<aj的貢獻
i=mid+1,j=l;
while(i<=r && j<=mid)
{
if(q[i].a<q[j].a)
{
add(q[i].t,1);
i++;
}
else
{
q[j].res+=ask(q[j].t-1);
j++;
}
}
while(j<=mid)
{
q[j].res+=ask(q[j].t-1);
j++;
}
for(int k=mid+1;k<i;k++) add(q[k].t,-1);
//歸并排序
i=l,j=mid+1;
int k=l;
while(i<=mid && j<=r)
{
if(q[i].a<=q[j].a)
{
w[k]=q[i];
i++,k++;
}
else
{
w[k]=q[j];
j++,k++;
}
}
while(i<=mid)
{
w[k]=q[i];
i++,k++;
}
while(j<=r)
{
w[k]=q[j];
j++,k++;
}
for(k=l;k<=r;k++) q[k]=w[k];
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&q[i].a);
pos[q[i].a]=i;
}
int tim=n;
for(int i=1;i<=m;i++)
{
int x;
scanf("%d",&x);
q[pos[x]].t=tim;
pos[x]=-1;
tim--;
}
for(int i=1;i<=n;i++)
{
if(pos[i]!=-1)
{
q[pos[i]].t=tim;
tim--;
}
}
cdq(1,n);
for(int i=1;i<=n;i++) ans[q[i].t]=q[i].res;
for(int i=2;i<=n;i++) ans[i]+=ans[i-1]; //若t1>t2，則ans[t2]的逆序對也是ans[t1]的逆序對
for(int i=n;i>=n-m+1;i--) printf("%lld\n",ans[i]);
return 0;
}
13.1.1.2.有刪除操作——線段樹分治
適用條件：有刪除操作，刪除（刪除之前任意一個操作，對未刪除的操作有后效性）難維護但是撤銷（刪除最后一次操作，對未刪除的操作沒有后效性）易維護。或是給定一些僅在給定時間范圍內有效的操作，詢問某個時間點所有操作的貢獻。
在l時刻之前加入、r時刻之后刪除的一對操作\(\Rightarrow\)一個時間范圍[l,r]內有效的操作。
離線數(shù)據(jù)結構。
一般還需要有可以支持撤銷操作的數(shù)據(jù)結構配合：
- 狀態(tài)很小（\(e.g.\)背包、線性基）：直接memcpy；
LL backup[M];
memcpy(backup,f,sizeof backup);
memcpy(f,backup,sizeof f);//撤銷
- 連通性：按秩合并并查集；
stack<PIII> st; //已執(zhí)行的操作序列（待撤銷），{{x,y},被改變的秩的原先大小}
void merge(int x,int y)
{
st.push({{x,y},dep[x]==dep[y]/*被改變的秩的原先大小*/});
return ;
}
void solve(int u)
{
while(st.size()>backup)
{
auto t=st.top();
st.pop();
int x=t.first.first,y=t.first.second,depy=t.second;
dep[y]=depy;
p[x]=x;
}
}
- 異或：可持久化trie、idx=0重構trie樹；
- 線段樹
- 沒有懶標記：可持久化線段樹；
- 有懶標記：暴力備份被修改的節(jié)點的原信息（一定要在pushdown前）。
vector<pair<int,Tree1> > backup[Q*4]; //backup[時間點]:{被修改的線段樹上節(jié)點編號,被修改的線段樹上節(jié)點的原信息}
void modify(int rt,int u,int l,int r,int val)
{
if(u==1 && rt!=1) backup[rt].push_back({u,tr1[u]}); //額外備份根節(jié)點的信息，因為下面?zhèn)浞莶坏?
/*
1.rt!=1：卡空間操作。時間軸在[0,q]不需要撤銷操作，不必備份；
2.不可直接在遞歸到每個節(jié)點時備份，否則其父節(jié)點懶標記的信息是未下傳的，其的信息是其父節(jié)點懶標記已下傳的
*/
if(rt!=1)
{
backup[rt].push_back({u<<1,tr1[u<<1]});
backup[rt].push_back({u<<1|1,tr1[u<<1|1]});
}
}
void solve(int u)
{
for(auto i : tr2[u].op) modify(u,1,l,r,val);
if(u!=1) for(int i=backup[u].size()-1;i>=0;i--) tr1[backup[u][i].first]=backup[u][i].second;
clear(backup[u]);
return ;
}
有一個全局狀態(tài)state，也就是所有操作依次執(zhí)行影響的狀態(tài)。修改、撤銷、查詢都是在這一個狀態(tài)上執(zhí)行。
在詢問時間軸（代碼稍難實現(xiàn)，還可以采用稍易實現(xiàn)的操作（包含修改、撤銷和詢問）時間軸）上建立線段樹。每一個節(jié)點開一個vector儲存操作，這樣對于在l時刻之前加入、r時刻之后刪除的一個操作，相當于一個時間范圍[l,r]內有效的操作，也就是在線段樹上區(qū)間[l,r]操作。把所有操作插入到線段樹離線。每執(zhí)行一次操作，把當前操作儲存到棧stack中，方便后面撤銷。
遍歷整棵線段樹，到達每個節(jié)點執(zhí)行該節(jié)點儲存的操作work()，然后繼續(xù)向下遞歸，到達葉子節(jié)點時統(tǒng)計貢獻回答詢問（可能是ANS（類似莫隊++--）或者是并查集）calc()，回溯時撤銷之前到達該節(jié)點執(zhí)行的操作（別忘記撤銷了！！！）undo(id)即可。
設執(zhí)行一次操作work(id)的復雜度是\(O(f(1))\)、撤銷undo(id)\(O(g(1))\)、查詢\(O(h(1))\)，則總的復雜度是\(O(f(N \log N)+g(N \log N)+h(N))\)。
采用詢問時間軸時，在兩個詢問操作之間的操作的時間屬于后面的詢問操作，在第一個詢問操作之前的操作的時間屬于第一個詢問操作。
now_state;//全局狀態(tài)，也就是所有操作依次執(zhí)行影響的狀態(tài)。修改、撤銷、查詢都是在這一個狀態(tài)上執(zhí)行
int aba[N]; //操作
stack<int> st; //已執(zhí)行的操作序列（待撤銷）
struct Tree
{
int l,r;
vector<int> op; //操作序列
}tr[N*4];
void work(int id)
{
st.push(id); //在執(zhí)行一次操作前，把當前操作儲存到棧stack中，方便后面撤銷
aba[id];
return ;
}
void build(int u,int l,int r)
{
tr[u]={l,r};
if(l==r) return ;
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
return ;
}
void insert(int u,int l,int r,int i)//線段樹上區(qū)間[l,r]操作
{
if(l<=tr[u].l && tr[u].r<=r)
{
tr[u].op.push_back(i);//每一個節(jié)點開一個vector儲存操作
return ;
}
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) insert(u<<1,l,r,i);
if(r>mid) insert(u<<1|1,l,r,i);
return ;
}
void solve(int u)
{
int backup=st.size();
//先執(zhí)行當前節(jié)點儲存的操作
for(int i=0;i<tr[u].op.size();i++)
{
int id=tr[u].op[i];
work(id);
}
if(tr[u].l==tr[u].r) calc(); //到達葉子節(jié)點時統(tǒng)計貢獻回答詢問，注意這里不可以直接return，因為下面還有撤銷操作
else
{
solve(u<<1);
solve(u<<1|1);
}
//回溯時撤銷操作
while(st.size()>backup)
{
auto t=st.top();
st.pop();
undo(id);
}
return ;
}
//1.采用自制的詢問時間軸
//有刪除操作，下面以加邊刪邊為例：
int eidx,qidx=1;//eidx：邊的編號；qidx：詢問的編號（同時也作為時間點），注意從1開始
PII edge[N+N];//邊的存在時間[l,r]
map<PII,int> h;//找到刪除操作對應的邊
PII que[N];//詢問操作
for(int i=1;i<=m;i++)
{
eidx++;
scanf("%d%d%d",&xx[eidx],&yy[eidx],&w[eidx]);
edge[eidx]={qidx,N};
h[{xx[eidx],yy[eidx]}]=eidx;
//h[{yy[eidx],xx[eidx]}]=eidx;//若是無向圖還有反向邊
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
int oo;
scanf("%d",&oo);
if(oo==1)
{
eidx++;
scanf("%d%d%d",&xx[eidx],&yy[eidx],&w[eidx]);
edge[eidx]={qidx,N};
h[{xx[eidx],yy[eidx]}]=eidx;
h[{yy[eidx],xx[eidx]}]=eidx;
}
else if(oo==2)
{
int uu,vv,id;
scanf("%d%d",&uu,&vv);
id=h[{uu,vv}];
edge[id].second=qidx-1;//注意刪除后此時的詢問將不能查詢到這條邊，因此edge的持續(xù)時間是qidx-1
}
else
{
int uu,vv;
scanf("%d%d",&uu,&vv);
que[qidx]={uu,vv};
qidx++;
}
}
qidx--;//注意在最后一次詢問操作之后的其他操作都沒有意義
build(1,1,qidx);//在詢問時間軸上建立線段樹，注意在qidx確定后、插入前建樹
for(int i=1;i<=eidx;i++)
{
if(edge[i].second==N) edge[i].second=qidx;//注意一直沒有刪除操作的邊持續(xù)時間是到qidx
if(edge[i].first<=edge[i].second/*在同一詢問時刻添加又刪除同一條邊（持續(xù)時間[qidx,qidx-1]，區(qū)間不存在！！！）是沒有意義的*/) insert(1,edge[i].first,edge[i].second,i/*插入邊的編號*/);
}
/*2.題目給定的時間軸
build(1,1,q); //在詢問時間軸上建立線段樹
for(int i=1;i<=m;i++)
{
int l,r; //l時刻之前加入、r時刻之后刪除
scanf("%d%d%d",&aba[i],&l,&r);
if(l!=r) insert(1,l,r,i);
}
*/
solve(1);//遍歷整棵線段樹
補充：當詢問操作有時間范圍限定，而修改操作沒有時：
在操作時間軸上建立線段樹，改為每一個節(jié)點（對應一段時間）開一個vector儲存詢問操作，開一個ans[]數(shù)組記錄答案。而把其他操作按時間排序。
遍歷整棵線段樹，傳入時間參數(shù)l,r（當前節(jié)點代表的時間段），到達每個節(jié)點執(zhí)行遞歸到當前節(jié)點的操作序列，統(tǒng)計貢獻回答當前節(jié)點儲存的詢問，ans[]數(shù)組記錄答案，然后像單點修改線段樹一樣以時間為標準把操作序列劃分到時間對應的子結點。，回溯時撤銷操作。用ans[]數(shù)組回答答案。
struct Operation
{
int t;
}op[N],opl[N],opr[N];
struct Query
{
int l,r;
}q[N];
int ans[N];
struct Tree
{
int l,r;
vector<int> que;//儲存詢問操作
}tree[N*4];
void q_insert(int u,int l,int r,int i)
{
if(l<=tr[u].l && tr[u].r<=r)
{
tr[u].que.push_back(i);
return ;
}
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) q_insert(u<<1,l,r,i);
if(r>mid) q_insert(u<<1|1,l,r,i);
return ;
}
void solve(int u,int st,int ed)//st,ed：當前節(jié)點代表的時間段[st,ed]
{
if(st>ed) return ;
int lidx=0,ridx=0;
for(int i=st;i<=ed;i++) work(op[i]);//執(zhí)行遞歸到當前節(jié)點的操作序列
for(int i=0;i<tr[u].que.size();i++)//統(tǒng)計貢獻回答當前節(jié)點儲存的詢問
{
int id=tr[u].que[i];
ans[id]=calc(id);//ans[]數(shù)組記錄答案
}
//像單點修改線段樹一樣以時間為標準把操作序列劃分到時間對應的子結點
if(tr[u].l==tr[u].r) return ;
int mid=(tr[u].l+tr[u].r)>>1;
for(int i=st;i<=ed;i++)
{
if(op[i].t<=mid) opl[++lidx]=op[i];
else opr[++ridx]=op[i];
}
for(int i=1;i<=lidx;i++) op[i+st-1]=opl[i];
for(int i=1;i<=ridx;i++) op[i+st+lidx-1]=opr[i];
solve(u<<1,st,st+lidx-1);
solve(u<<1|1,st+lidx,ed);
for(int i=st;i<=ed;i++) undo(op[i]);//回溯時撤銷操作
return ;
}
build(1,1,tim);//在操作時間軸上建立線段樹
for(int i=1;i<=qidx;i++) q_insert(1,q[i].l,q[i].r,i);//每一個節(jié)點（對應一段時間）開一個vector儲存詢問操作
sort(op+1,op+oidx+1,cmp);//把其他操作按時間排序
solve(1,1,tim);
for(int i=1;i<=qidx;i++) printf("%d\n",ans[i]);
13.1.2.基于值域的分治算法——整體二分
適用條件：多組詢問、修改，詢問具有可二分性。因不能快速計算一處點值而導致每組都單獨直接二分的總復雜度大。
13.1.2.1.整數(shù)集合上的二分
-
思考一組詢問如何二分求解。
-
把詢問放在一起二分
solve(lval,rval,st,ed)：詢問[st,ed]的答案都在[lval,rval]內。每一層都把在[lval,mid]內的元素加入集合，根據(jù)集合check在[st,ed]內的詢問，根據(jù)check的返回值+一組詢問如何二分判斷該詢問放到左/右子區(qū)間。注意像一組詢問如何二分那樣也要保左保右，也可以像一組詢問如何二分那樣判斷無解情況。整體二分復雜度的保證：“每一層都把屬于[lval,mid]的元素加入集合”：只需要維護一個全局集合+變量MID：已把在[1,MID]內的元素加入全局集合。每一層通過移動指針MID使得MID=mid。如果按照處理當前層、遞歸左區(qū)間、遞歸右區(qū)間的順序，指針的移動距離是\(O(N\log N)\)。
下面以單組詢問采用保左+n+1無解的二分為例：
int n,q,MID;//MID：已把在[1,MID]內的元素加入全局集合
struct Query
{
LL need,ans;
}que[N],lq[N],rq[N];
struct Node //全局集合
void change(int id,int sign)//1/-1：把元素id加入/刪除全局集合
bool check(Query id)//二分檢查詢問id
void solve(int lval,int rval,int st,int ed)
{
//邊界
if(st>ed) return ;
if(lval==rval)
{
for(int i=st;i<=ed;i++) que[i].ans=lval;
return ;
}
//處理當前層，移動指針MID使得MID=mid，進而使得每一層都把在[lval,mid]內的元素加入集合
int mid=(lval+rval)>>1;
while(mid<MID) change(MID,-1),MID--;
while(MID<mid) MID++,change(MID,1);
//根據(jù)全局集合check在[st,ed]內詢問，根據(jù)check的返回值+一組詢問如何二分判斷該詢問放到左/右子區(qū)間
int lqidx=0,rqidx=0;
for(int i=st;i<=ed;i++)
{
if(check(que[i])) lq[++lqidx]=que[i];
else rq[++rqidx]=que[i];
}
for(int i=1;i<=lqidx;i++) que[st+i-1]=lq[i];
for(int i=1;i<=rqidx;i++) que[st+lqidx+i-1]=rq[i];
//遞歸左/右區(qū)間
solve(lval,mid,st,st+lqidx-1);
solve(mid+1,rval,st+lqidx,ed);
return ;
}
solve(1,n+1,1,q);
for(int i=1;i<=q;i++)
{
if(que[i].ans==n+1) puts("-1");
else printf("%lld\n",que[i].ans);
}
13.1.2.1.值域上的二分
把所有的操作（包括將數(shù)組的原值看作一開始就賦值的操作）先按時間排好序（本來就自然地排好序），然后只要進行1次值域上的二分：
merge(lval,rval,st,ed)：值域為[L,R]的整數(shù)序列a，對操作序列q（含刪除、賦值、詢問）進行處理。- 令整數(shù)序列a中≤mid的數(shù)構成整數(shù)序列l(wèi)a，>mid的數(shù)構成整數(shù)序列ra，操作序列q中涉及≤mid的數(shù)的操作構成操作序列l(wèi)q，涉及≤mid的數(shù)的操作構成操作序列rq。注意保持操作的時間順序。
- 還原現(xiàn)場，分治求解
merge(lval,mid):la,lq和merge(mid+1,rval):ra,rq。邊界：當操作序列為空時直接返回；當整數(shù)序列只剩1個數(shù)時得到答案。
- 例題：區(qū)間第k小數(shù)（動態(tài)修改）
//由于修改操作會分成兩個操作，因此數(shù)組開3倍！！！
int n,m;
int a[N]; //原數(shù)組
int ans[N];
int tr[N]; //樹狀數(shù)組維護單個區(qū)間靜態(tài)第k小數(shù)
//操作序列（按時間排好序）
//當op=-1：刪除某個位置上的數(shù)的貢獻；0：在某個位置增添一個數(shù)的貢獻；1：詢問
//修改操作分為刪除-1和賦值0
int idx;
struct Data
{
int op,x,y,z;
}q[N],lq[N],rq[N]; //q：當前操作序列；lq（rq）：分配到左（右）兒子的操作序列
void merge(int lval,int rval,int st,int ed) //lval、rval：值域；st、ed：操作序列。
{
if(st>ed) return ; //空操作序列，返回
if(lval==rval) //找到答案
{
for(int i=st;i<=ed;i++) if(q[i].op>0) ans[q[i].op]=lval;
return ;
}
//分配到左兒子或右兒子
int mid=(lval+rval)>>1;
int lqidx=0,rqidx=0;
for(int i=st;i<=ed;i++)
{
if(q[i].op==-1)
{
if(q[i].y<=mid) //按值域劃分：對答案有貢獻的數(shù)的值小于mid分到左兒子
{
add(q[i].x,-1); //樹狀數(shù)組維護：刪除某個位置上的數(shù)的貢獻，而不是減這個數(shù)的值，因此修改操作分成的兩個操作就算分道揚鑣也不會影響正確性
lq[++lqidx]=q[i];
}
else rq[++rqidx]=q[i];
}
else if(q[i].op==0) //類似上面
{
if(q[i].y<=mid)
{
add(q[i].x,1);
lq[++lqidx]=q[i];
}
else rq[++rqidx]=q[i];
}
else
{
int cnt=ask(q[i].y)-ask(q[i].x-1);
if(cnt>=q[i].z) lq[++lqidx]=q[i]; //這個區(qū)間小于mid的數(shù)的個數(shù)大于k，因此答案應該在左兒子
else
{
q[i].z-=cnt; //注意分到右兒子前應減去左兒子的影響
rq[++rqidx]=q[i];
}
}
}
for(int i=ed;i>=st;i--) //清空樹狀數(shù)組
{
if(q[i].op==-1 && q[i].y<=mid) add(q[i].x,1);
else if(q[i].op==0 && q[i].y<=mid) add(q[i].x,-1);
}
for(int i=1;i<=lqidx;i++) q[st+i-1]=lq[i]; //節(jié)省空間
for(int i=1;i<=rqidx;i++) q[st+lqidx+i-1]=rq[i]; //節(jié)省空間
merge(lval,mid,st,st+lqidx-1); //往下分治
merge(mid+1,rval,st+lqidx,ed); //往下分治
return ;
}
int main()
{
memset(ans,-1,sizeof ans); //輸出時方便判斷是否為查詢操作
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
q[++idx]={0,i,a[i]};//將數(shù)組的原值看作一開始就賦值的操作
}
for(int i=1;i<=m;i++)
{
char op[2];
scanf("%s",op);
if(op[0]=='Q')
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
q[++idx]={i,l,r,k};
}
else
{
int x,y;
scanf("%d%d",&x,&y);
//修改操作會分成兩個操作。并且因此數(shù)組要開3倍！
q[++idx]={-1,x,a[x]};//刪除
q[++idx]={0,x,y};//賦值
a[x]=y; //別忘記修改原數(shù)組
}
}
merge(0,INF,1,idx);
for(int i=1;i<=m;i++) if(ans[i]!=-1) printf("%d\n",ans[i]);
return 0;
}
13.2.樹上分治算法
《數(shù)據(jù)結構?字符串和圖8.2. 樹上分治算法》
14.線性基
很適合維護異或。
《數(shù)學2.3.2.異或空間》
浙公網(wǎng)安備 33010602011771號