题意：一个1~n的排列，m个操作：
0 x y：将ax~ay按升序排列；
1 x y：将ax~ay按降序排列。
询问m次操作后第aq的值。
输入：第一行：两个正整数n,m,表示序列的长度与询问的个数；
第二行：一个1~n的排列；
第3~m+2行：每行一个操作。
第m+3行：一个数q表示询问的位置。
输出：一个数表示aq的值。
样例输入：
6 3 1 6 2 5 3 4 0 1 4 1 3 6 0 2 4 3
样例输出：
5
解析：考虑二分答案，将小于答案的数变为0，将大于等于答案的变为1，这样整个序列就变成了一个01序列。后对于每个二分出来的01序列建一个线段树，由于数列由0和1组成，所以在每次操作时，若为变为升序，则将0往前放，将1往后放，反之亦然。
代码如下：
1 #include<cstdio> 2 #define lc o<<1 3 #define rc o<<1|1 4 using namespace std; 5 6 const int MAXN=100010; 7 int n,m,a[MAXN],bj[MAXN],x[MAXN],y[MAXN],inx,b[MAXN],sum[MAXN*4],set[MAXN*4]; 8 9 int read(void) { 10 char c; while (c=getchar(),c<'0' || c>'9'); int x=c-'0'; 11 while (c=getchar(),c>='0' && c<='9') x=x*10+c-'0'; return x; 12 } 13 14 void build(int o,int l,int r) { //建树 15 set[o]=-1; 16 if (l==r) { 17 sum[o]=b[l]==1; return; 18 } 19 int mid=l+r>>1; 20 build(lc,l,mid); build(rc,mid+1,r); 21 sum[o]=sum[lc]+sum[rc]; 22 } 23 24 void pushdown(int o,int l,int r) { //标记下方 25 set[lc]=set[rc]=set[o]; set[o]=-1; 26 int mid=l+r>>1; 27 sum[lc]=set[lc]*(mid-l+1); 28 sum[rc]=set[rc]*(r-mid); 29 } 30 31 int query_range(int o,int l,int r,int ql,int qr) { //区间查询1的个数 32 if (ql<=l && qr>=r) return sum[o]; 33 int mid=l+r>>1,ans=0; 34 if (set[o]!=-1) pushdown(o,l,r); 35 if (ql<=mid) ans+=query_range(lc,l,mid,ql,qr); 36 if (qr>mid) ans+=query_range(rc,mid+1,r,ql,qr); 37 return ans; 38 } 39 40 void modify(int o,int l,int r,int ql,int qr,int c) { //区间修改 41 if (ql>qr) return; 42 if (ql<=l && qr>=r) { 43 set[o]=c; sum[o]=c*(r-l+1); 44 return; 45 } 46 int mid=l+r>>1; 47 if (set[o]!=-1) pushdown(o,l,r); 48 if (ql<=mid) modify(lc,l,mid,ql,qr,c); 49 if (qr>mid) modify(rc,mid+1,r,ql,qr,c); 50 sum[o]=sum[lc]+sum[rc]; 51 } 52 53 int query_single(int o,int l,int r,int p) { //单点查询(其实不用那么麻烦) 54 if (l==r) return sum[o]; 55 int mid=l+r>>1; 56 if (set[o]!=-1) pushdown(o,l,r); 57 if (p<=mid) return query_single(lc,l,mid,p); else return query_single(rc,mid+1,r,p); 58 } 59 60 int check(int midd) { //判断 61 for (int i=1;i<=n;++i) b[i]=a[i]>=midd; 62 build(1,1,n); 63 for (int i=1;i<=m;++i) { 64 if (bj[i]==0) { 65 int tmp=query_range(1,1,n,x[i],y[i]); //找1的个数 66 modify(1,1,n,x[i],y[i]-tmp,0); //前一段变为0 67 modify(1,1,n,y[i]-tmp+1,y[i],1); //后一段变为1 68 } 69 else { 70 int tmp=query_range(1,1,n,x[i],y[i]); 71 modify(1,1,n,x[i],x[i]+tmp-1,1); //前一段变为1 72 modify(1,1,n,x[i]+tmp,y[i],0); //后一段变为0 73 } 74 } 75 int tmp=query_single(1,1,n,inx); //查找当前位置的值 76 return tmp==1; 77 } 78 79 int main() { 80 n=read(); m=read(); 81 for (int i=1;i<=n;++i) a[i]=read(); 82 for (int i=1;i<=m;++i) { 83 bj[i]=read(); x[i]=read(); y[i]=read(); 84 } 85 inx=read(); 86 int l=1,r=n,mid,res; 87 while (l<=r) { 88 mid=l+r>>1; 89 if (check(mid)) res=mid,l=mid+1; 90 else r=mid-1; 91 } 92 printf("%d",res); 93 return 0; 94 }其实用合并线段树可以把复杂度降到nlogn，但我不会打。
转载于:https://www.cnblogs.com/Gaxc/p/9738017.html
