題目鏈接

---

對于序列上每一段連續區間的數我們都可以動態開點建一棵值域線段樹。初始時就是\(n\)棵。
對于每次操作，我們可以將\([l,r]\)的數分別從之前它所屬的若干段區間中分離出來，合并。
對于升序與降序，只需要維護一個標記，若為降序，則給左區間大的那部分。
具體實現還要用set存下每棵線段樹維護的區間左端點，便于快速查找包含\([l,r]\)的區間；對每個區間維護其右端點便于快速得到區間大小。
時間、空間復雜度都是\(O((n+m)\log n)\)。

但是在洛谷上要么RE要么MLE。。其它OJ上還是能過的。

---

Another Solution：
對于詢問二分一個值，將所有數根據與這個值的大小關系設為0/1。模擬每次操作，就是將一段區間的0/1分別放在兩邊。用線段樹維護區間和、區間覆蓋即可。最后判斷是否僅p之前全是0，

---

線段樹合并做法：

//57628kb 1692ms #include <set> #include <cstdio> #include <cctype> #include <algorithm> //#define gc() getchar() #define MAXIN 150000 #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) const int N=1e5+5;int n,m,R[N],root[N],tmp[N]; bool type[N];//0:↑ std::set<int> st; char IN[MAXIN],*SS=IN,*TT=IN;struct Segment_Tree {#define S N*34//!#define lson son[x][0]#define rson son[x][1]int tot,top,sk[S],sz[S],son[S][2];#define Del_Node(x) sk[++top]=xinline int New_Node(){int x=top?sk[top--]:++tot;lson=rson=0, sz[x]=1;return x;}void Insert(int &x,int l,int r,int p){x=New_Node();if(l==r) return;int m=l+r>>1;if(p<=m) Insert(lson,l,m,p);else Insert(rson,m+1,r,p);}void Split(int &y,int x,int k)//將線段樹分為x,y兩棵，使得sz[x]==k。{y=New_Node();int ls=sz[lson];if(ls<k) Split(son[y][1],rson,k-ls);else son[y][1]=rson, rson=0;if(ls>k) Split(son[y][0],lson,k);sz[y]=sz[x]-k, sz[x]=k;}int Merge(int x,int y){if(!x||!y) return x^y;lson=Merge(lson,son[y][0]), rson=Merge(rson,son[y][1]);sz[x]+=sz[y], Del_Node(y); return x;}int Query(int x,int l,int r,int k){if(l==r) return l;int ls=sz[lson], m=l+r>>1;if(ls>=k) return Query(lson,l,m,k);return Query(rson,m+1,r,k-ls);} // void Print(int x,int l,int r) // { // if(!x) return; // printf("%d:%d~%d sz:%d\n",x,l,r,sz[x]); // if(l==r) ; // else Print(lson,l,l+r>>1), Print(rson,(l+r>>1)+1,r); // } // void Output(int x){ // printf("%d root:%d type:%d:\n",x,root[x],type[x]), Print(root[x],1,n), putchar('\n'); // } }T;inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; } void Split(int x,int y)//將x~y劃分為一段 {if(y<x||y>=R[x]) return;if(!type[x]) T.Split(root[y+1],root[x],y-x+1);else root[y+1]=root[x], T.Split(root[x],root[y+1],R[x]-y);//保留右邊那部分R[x]-x+1-y+x-1 R[y+1]=R[x], R[x]=y, type[y+1]=type[x], st.insert(y+1); } void Merge(int x,int y) {if(x==y) return;//root[x]=T.Merge(root[x],root[y]);R[x]=R[y], st.erase(y); } int Query(int k) {std::set<int>::iterator p=st.upper_bound(k);int x=*(--p); k-=x-1;return type[x]?T.Query(root[x],1,n,R[x]-x+2-k):T.Query(root[x],1,n,k); }int main() {n=read(), m=read();for(int i=1; i<=n; ++i)T.Insert(root[i],1,n,read()), st.insert(i), R[i]=i;std::set<int>::iterator p1,p2;for(int opt,l,r; m--; ){opt=read(), l=read(), r=read();p1=st.upper_bound(l), Split(*(--p1),l-1);p1=st.upper_bound(r), Split(*(--p1),r);p1=st.lower_bound(l), p2=st.upper_bound(r);int now=*p1, t=0;for(++p1; p1!=p2; ++p1) tmp[++t]=*p1;//Merge要修改set，所以還是先存下來吧。for(int i=1; i<=t; ++i) Merge(now,tmp[i]);type[l]=opt; //type[now]=opt; }printf("%d\n",Query(read()));return 0; }

轉載于:https://www.cnblogs.com/SovietPower/p/9300070.html

總結

以上是生活随笔為你收集整理的BZOJ.4552.[HEOI2016/TJOI2016]排序(线段树合并/二分 线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

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