网站建设先进城市,wordpress 淘客代码,智能建造师,购买手表网站Description 在2016年#xff0c;佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题#xff0c;现在他在研究一个难题#xff0c;需要你来帮助他。这个难题是这样子的#xff1a;给出一个1到n的全排列#xff0c;现在对这个全排列序列进行m次局部排序…Description 在2016年佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题现在他在研究一个难题需要你来帮助他。这个难题是这样子的给出一个1到n的全排列现在对这个全排列序列进行m次局部排序排序分为两种1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。 solution 在看到二分答案这个标签后就是SBT了 首先常规套路如果值域较小那么枚举值域线段树区间覆盖 那么这题这么做这个转换呢直接二分答案把小于的部分赋为0大于等于部分1这样转换过来了注意线段树只要存1就好,0直接可以相减得出 #include algorithm
#include iostream
#include cstdlib
#include cstring
#include cstdio
#include cmath
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)(b)?(a):(b))
#define Min(a,b) ((a)(b)?(a):(b))
using namespace std;
const int N100005;
#define ls (node1)
#define rs (node1|1)
int n,m,a[N],t[N2],L[N],R[N],op[N],mark[N2],P;
void upd(int node){t[node]t[ls]t[rs];}
il void pushdown(RG int node,int l,int r){if(mark[node]-1)return ;int kmark[node],mid(lr)1;t[ls]k*(mid-l1);t[rs]k*(r-mid);mark[ls]mark[rs]k;mark[node]-1;
}
il void build(int l,int r,RG int node,int li){mark[node]-1;t[node]0;if(lr){t[node](a[l]li);return ;}int mid(lr)1;build(l,mid,ls,li);build(mid1,r,rs,li);upd(node);
}
il int query(int l,int r,RG int node,int sa,int se){if(lse || rsa)return 0;if(sal rse)return t[node];pushdown(node,l,r);int mid(lr)1;int q1query(l,mid,ls,sa,se);int q2query(mid1,r,rs,sa,se);return q1q2;
}
il void updata(int l,int r,RG int node,int sa,int se,int i){if(lse || rsa)return ;if(sal rse){t[node]i*(r-l1);mark[node]i;return ;}pushdown(node,l,r);int mid(lr)1;updata(l,mid,ls,sa,se,i);updata(mid1,r,rs,sa,se,i);upd(node);
}
bool check(int mid){build(1,n,1,mid);int l,r,re[2];for(int i1;im;i){lL[i];rR[i];re[1]query(1,n,1,l,r);re[0]r-l1-re[1];if(op[i]){updata(1,n,1,l,lre[1]-1,1);updata(1,n,1,lre[1],r,0);}else{updata(1,n,1,l,lre[0]-1,0);updata(1,n,1,lre[0],r,1);}}return query(1,n,1,P,P);
}
void work()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,a[i]);for(int i1;im;i)scanf(%d%d%d,op[i],L[i],R[i]);int l1,rn,mid,ans;scanf(%d,P);while(lr){mid(lr)1;if(check(mid))ansmid,lmid1;else rmid-1;}printf(%d\n,ans);
}int main()
{work();return 0;
}转载于:https://www.cnblogs.com/Yuzao/p/7663085.html
