[TJOI2016][HEOI2016]排序

题目大意：
　　给定一个$1\sim n(n\leq10^5)$的全排列，有$m(m\leq10^5)$次操作，每次把区间$[l,r]$按照升序或降序排序。最后询问所有操作完成后，位置为$q$的数是多少。

思路：
　　题目只需要求位置为$q$的数是多少，而并不关心其他的数是多少。因此排序时也只需要考虑答案的那个数。二分答案$k$，将$<k$的数当成0，$\geq k$的数当成1，原序列就变成了一个01序列。这样排序时只需要统计区间内0和1的个数，线段树区间修改即可。若排序后$q$上的值为1，则答案$\geq k$，否则$<k$。

 #include<cstdio>

 #include<cctype>

 #include<algorithm>

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=,M=;

 int n,m,q,a[N];

 struct Modify {

     bool type;

     int l,r;

 };

 Modify o[M];

 class SegmentTree {

     #define _left <<1

     #define _right <<1|1

     private:

         int val[N<<],tag[N<<];

         void push_up(const int &p) {

             val[p]=val[p _left]+val[p _right];

         }

         void push_down(const int &p,const int &b,const int &e) {

             if(tag[p]==-) return;

             const int mid=(b+e)>>;

             tag[p _left]=tag[p _right]=tag[p];

             val[p _left]=tag[p]*length(b,mid);

             val[p _right]=tag[p]*length(mid+,e);

             tag[p]=-;

         }

         int length(const int &b,const int &e) const {

             return e-b+;

         }

     public:

         void build(const int &p,const int &b,const int &e,const int &k) {

             if(b==e) {

                 val[p]=a[b]>=k;

                 return;

             }

             tag[p]=-;

             const int mid=(b+e)>>;

             build(p _left,b,mid,k);

             build(p _right,mid+,e,k);

             push_up(p);

         }

         void modify(const int &p,const int &b,const int &e,const int &l,const int &r,const bool &x) {

             if(b==l&&e==r) {

                 tag[p]=x;

                 val[p]=x*length(b,e);

                 return;

             }

             push_down(p,b,e);

             const int mid=(b+e)>>;

             if(l<=mid) modify(p _left,b,mid,l,std::min(mid,r),x);

             if(r>mid) modify(p _right,mid+,e,std::max(mid+,l),r,x);

             push_up(p);

         }

         int query(const int &p,const int &b,const int &e,const int &l,const int &r) {

             if(b==l&&e==r) return val[p];

             push_down(p,b,e);

             const int mid=(b+e)>>;

             int ret=;

             if(l<=mid) ret+=query(p _left,b,mid,l,std::min(mid,r));

             if(r>mid) ret+=query(p _right,mid+,e,std::max(mid+,l),r);

             return ret;

         }

     #undef _left

     #undef _right

 };

 SegmentTree t;

 inline bool check(const int &k) {

     t.build(,,n,k);

     for(register int i=;i<m;i++) {

         const int opt=o[i].type,l=o[i].l,r=o[i].r,cnt1=t.query(,,n,l,r),cnt0=r-l+-cnt1;

         if(opt==) {

             if(cnt0) t.modify(,,n,l,l+cnt0-,);

             t.modify(,,n,l+cnt0,r,);

         }

         if(opt==) {

             if(cnt1) t.modify(,,n,l,l+cnt1-,);

             t.modify(,,n,l+cnt1,r,);

         }

     }

     return t.query(,,n,q,q);

 }

 int main() {

     n=getint(),m=getint();

     for(register int i=;i<=n;i++) a[i]=getint();

     for(register int i=;i<m;i++) {

         const int opt=getint(),l=getint(),r=getint();

         o[i]=(Modify){opt,l,r};

     }

     q=getint();

     int l=,r=n;

     while(l<=r) {

         const int mid=(l+r)>>;

         if(check(mid)) {

             l=mid+;

         } else {

             r=mid-;

         }

     }

     printf("%d\n",l-);

     return ;

 }

巴特西

[TJOI2016][HEOI2016]排序

最新文章

热门文章