題目鏈接：點擊查看

題目分析：剛看到這個題目的時候，口胡了一個假算法，覺得對于每次詢問的操作 $[l,r]$ ，只需要找到指令集區間 $[l,r]$ 內覆蓋到點 $k$ 的最大并集，然后求出這段區間中 $a$ 數組的最大值就是答案了，這樣一來直接用線段樹維護一下數組 $a$，再用主席樹維護一下區間交集即可

但后來轉念一想，覆蓋的區間還有時序問題，也就是兩個區間執行的先后順序不同，會造成不一樣的結果，到此為止這個題也就卡住了

今天看了題解和楊大佬討論了一下就豁然開朗了，其實卡住的部分就差預處理出一個樹上倍增了

因為本題中的指令集操作，本質上是將一個區間的數值都賦值為該區間的最大值。所以我們的最終目標仍然是需要找到包含點 $k$ 的區間向左向右分別可以擴展到什么位置，記為 $[ll,rr]$，那么答案就是數組 $a$ 在 $[ll,rr]$ 中的最大值了，下面以向右擴展為例來講解，向左擴展的話只需要類比過去就好啦

將指令集視為一棵樹，對于第 $i$ 個指令來說，其代表的區間為 $[l_i,r_i]$，因為我們需要盡可能向右擴展，所以我們查找一下點 $r_i$ 最后一次被哪個指令集所覆蓋，記為 $j$，那么此時就會產生一條 $j?>i$ 的有向邊，如此建圖的話，最后就會形成一棵以點 $0$ 為根節點的樹（其實嚴格意義上來說，是以點 $0$ 為根節點的一棵森林）

而且不難發現，假設 $j$ 到 $i$ 有一條邊，且 $j$ 是 $i$ 的父節點，那么滿足兩個性質：

$j<i$

$r_j>=r_i$

所以對于給定的點 $k$ ，我們只需要找到其最多可以擴展到的位置就是上文中需要求的 $rr$ 了

而不斷向上跳 $fa$ 的過程也可以利用倍增快速實現

如果每次詢問的都是 $[1,m]$ 中的指令集，那么問題就已經解決了所以現在只剩下了一個問題，那就是指令集限制在 $[l,r]$ 內該如何實現呢？

注意到上面提到的，建出來的樹的性質一，即從根節點到任意節點的編號都是單調遞增的，所以我們可以從第 $r$ 個指令集不斷向上跳，跳到深度最低，且指令集的編號仍然大于等于 $l$ 的那個祖先為止

所以現在的目標就轉換為了，如何建出上文中的那棵樹呢？其實只需要實現下面兩個操作即可：

將某個版本的的某個區間覆蓋成指定顏色

查詢某個版本指定位置的顏色的最大值

因為涉及到了歷史版本和區間問題，所以用主席樹來維護就好啦

需要注意的是，區間修改要用到標記永久化，并且對于某段區間的修改，保守估計會有 $3logn$ 個節點會被修改，所以主席樹的數組大小需要注意一下

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e5+100; int n,L[N][25],R[N][25],ql[N],qr[N]; struct Seg {struct Node {int l,r,mmax;}tree[N<<2];void pushup(int k) {tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax);}void build(int k,int l,int r) {tree[k]={l,r,0};if(l==r) {read(tree[k].mmax);return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k);}void update(int k,int pos,int val) {if(tree[k].l==tree[k].r) {tree[k].mmax=val;return;}int mid=(tree[k].l+tree[k].r)>>1;if(pos<=mid) {update(k<<1,pos,val);} else {update(k<<1|1,pos,val);}pushup(k);}int query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) {return 0;}if(tree[k].l>=l&&tree[k].r<=r) {return tree[k].mmax;}return max(query(k<<1,l,r),query(k<<1|1,l,r));} }SEG; struct CMT {struct Node {int l,r,lazy;}tree[N*60];int root[N],tot;int newnode() {tot++;tree[tot].l=tree[tot].r=tree[tot].lazy=0;return tot;}void update(int &k,int l,int r,int L,int R,int val) {//[l,r]:target [L,R]:curif(L>r||R<l) {return;}int nk=newnode();tree[nk]=tree[k];k=nk;if(L>=l&&R<=r) {tree[k].lazy=val;return;}int mid=(L+R)>>1;update(tree[k].l,l,r,L,mid,val);update(tree[k].r,l,r,mid+1,R,val);}int query(int k,int L,int R,int pos,int val) {//[L,R]:curval=max(val,tree[k].lazy);if(L==R) {return val;}int mid=(L+R)>>1;if(pos<=mid) {return query(tree[k].l,L,mid,pos,val);} else {return query(tree[k].r,mid+1,R,pos,val);}}void update(int l,int r,int val) {//將[l,r]染色成valupdate(root[val],l,r,1,n,val);}int query(int k,int pos) {//查詢第k個版本點pos的顏色return query(root[k],1,n,pos,0);} }CMT; int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int m,q;read(n),read(m),read(q);SEG.build(1,1,n);for(int i=1;i<=m;i++) {read(ql[i]),read(qr[i]);L[i][0]=CMT.query(i-1,ql[i]);R[i][0]=CMT.query(i-1,qr[i]);CMT.root[i]=CMT.root[i-1];CMT.update(ql[i],qr[i],i);for(int j=1;j<=20;j++) {L[i][j]=L[L[i][j-1]][j-1];R[i][j]=R[R[i][j-1]][j-1];}}while(q--) {int op;read(op);if(op==1) {int x,y;read(x),read(y);SEG.update(1,x,y);} else if(op==2) {int l,r,k;read(l),read(r),read(k);int ll=CMT.query(r,k);int rr=ll;for(int i=20;i>=0;i--) {if(R[rr][i]>=l) {rr=R[rr][i];}if(L[ll][i]>=l) {ll=L[ll][i];}}if(ll<l) {printf("%d\n",SEG.query(1,k,k));} else {printf("%d\n",SEG.query(1,ql[ll],qr[rr]));}}}return 0; } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的2020-2021年度第二届全国大学生算法设计与编程挑战赛 （春季赛）- 天才的操作(线段树+主席树+树上倍增)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。