正題

題目鏈接:https://www.luogu.com.cn/problem/P2824

---

題目大意

$n$個數，每次將一個區間正序或者倒序排序，求最后位置$p$的數。

---

解題思路

思路確實巧妙

二分答案，定義大于$mid$的數為1，小于$mid$的數為2，然后用線段樹排序即可。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; int n,m,q,maxs; int a[N],op[N],l[N],r[N]; int w[N*4],lazy[N*4]; struct Seq_Tree{void Build(int x,int l,int r,int z){w[x]=lazy[x]=0;if(l==r){w[x]=(a[l]>=z);return;}int mid=(l+r)>>1;Build(x*2,l,mid,z);Build(x*2+1,mid+1,r,z);w[x]=w[x*2]+w[x*2+1];return;}void Downdata(int x,int l,int r){if(!lazy[x])return;int mid=(l+r)>>1;lazy[x*2]=lazy[x*2+1]=lazy[x];if(lazy[x]==2)w[x*2]=mid-l+1,w[x*2+1]=r-mid;else w[x*2]=w[x*2+1]=0;lazy[x]=0;return;}void Change(int x,int L,int R,int l,int r,int z){if(L==l&&R==r){lazy[x]=z+1;w[x]=(R-L+1)*z;return;}int mid=(L+R)>>1;Downdata(x,L,R);if(r<=mid)Change(x*2,L,mid,l,r,z);else if(l>mid)Change(x*2+1,mid+1,R,l,r,z);else Change(x*2,L,mid,l,mid,z),Change(x*2+1,mid+1,R,mid+1,r,z);w[x]=w[x*2]+w[x*2+1];return;}int Ask(int x,int L,int R,int l,int r){if(L==l&&R==r)return w[x];int mid=(L+R)>>1;Downdata(x,L,R);if(r<=mid)return Ask(x*2,L,mid,l,r);if(l>mid)return Ask(x*2+1,mid+1,R,l,r);return Ask(x*2,L,mid,l,mid)+Ask(x*2+1,mid+1,R,mid+1,r);} }T; bool Check(int w){T.Build(1,1,n,w);for(int i=1;i<=m;i++){int z=T.Ask(1,1,n,l[i],r[i]);T.Change(1,1,n,l[i],r[i],0);if(z==0)continue;if(op[i]==1)T.Change(1,1,n,l[i],l[i]+z-1,1);else T.Change(1,1,n,r[i]-z+1,r[i],1);}return T.Ask(1,1,n,q,q); } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]),maxs=max(maxs,a[i]);for(int i=1;i<=m;i++)scanf("%d%d%d",&op[i],&l[i],&r[i]);scanf("%d",&q);int L=1,R=maxs;while(L<=R){int mid=(L+R)>>1;if(Check(mid))L=mid+1;else R=mid-1;}printf("%d",R); }

總結

以上是生活随笔為你收集整理的P2824-[HEOI2016/TJOI2016]排序【线段树,二分】的全部內容，希望文章能夠幫你解決所遇到的問題。

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