luoguP2824 [HEOI2016/TJOI2016]排序

题很好但是我不会。

二分答案%%%

二分一下询问位置的值。然后把整个序列变成一个01序。如果一个数字大于等于它就看成1,如果小于等于就看成0.

然后对所有待处理区间排序。这里由于是01序,排序只需要
1.统计1的个数
2.全部清0
3.后面/前面部分赋1

这是个显然的线段树操作,但是我打了ODT

于是wa了

填坑 今天发现了以前代码的漏洞

首先,正解线段树窝也打了

/*Heroes Never Die!*/
#include "iostream"
#include "cstring"
#include "cstdio"
#include "set"
#include "algorithm"
using namespace std;
#define MAXN 50006
int A[MAXN] , k , n , m;

struct query { int l , r , k ; } q[MAXN];

int S[MAXN<<2] , lazy[MAXN<<2];

void pushup( int rt ) {
    S[rt] = S[rt<<1] + S[rt<<1|1];
}

void pushdown( int rt , int m ) {
    if( lazy[rt] == 1 ) {
        S[rt<<1] = ( m - ( m >> 1 ) ) , S[rt<<1|1] = ( m >> 1 );
        lazy[rt<<1] = 1, lazy[rt<<1|1] = 1, lazy[rt] = 0;
    }
    if( lazy[rt] == -1 ) {
        S[rt<<1] = 0 , S[rt<<1|1] = 0 ,
        lazy[rt<<1] = -1 , lazy[rt<<1|1] = -1 , lazy[rt] = 0;
    }
}

void build( int l , int r , int rt , int x ) {
    if( l == r ) {if( A[l] >= x ) S[rt] = 1;else S[rt] = 0;return;}
    int m = l + r >> 1;
    build( l , m , rt<<1 , x );
    build( m + 1 , r , rt<<1|1, x );
    pushup( rt );
}

void change( int L , int R , int c, int l=1 , int r = n , int rt = 1 ) {
    if( L <= l && R >= r ) { S[rt] = c?(r-l+1):0 , lazy[rt] = c?1:-1; return; }
    int m = l + r >> 1;
    pushdown( rt , r - l + 1 );
    if( L <= m ) change( L,R,c,l,m,rt<<1 );
    if( R >  m ) change( L,R,c,m+1,r,rt<<1|1 );
    pushup( rt );
}

int countone( int L , int R , int l = 1 , int r = n , int rt = 1 ) {
    if( L <= l && R >= r ) return S[rt];
    int m = l + r >> 1 , res = 0;
    pushdown( rt , r - l + 1 );
    if( L <= m ) res += countone( L,R,l,m,rt<<1 );
    if( R >  m ) res += countone( L,R,m+1,r,rt<<1|1 );
    return res;
}

bool check( int x ) {
    memset( S,0,sizeof S ) , memset( lazy , 0 , sizeof lazy );
    build( 1,n,1,x );
    for( int i = 1 ; i <= m ; ++ i ) {
        int l = q[i].l , r = q[i].r , k = q[i].k , numone = countone( l , r );
        if( !k ) change( r - numone + 1 , r , 1 ) , change( l , r - numone , 0 );
        else change( l , l + numone - 1 , 1 ) , change( l + numone , r , 0 );
    }
    return countone( k,k ) == 1;
}

int main() {
    cin >> n >> m;
    for( int i = 1 ; i <= n ; ++ i ) scanf( "%d" , & A[i] );
    for( int i = 1 ; i <= m ; ++ i ) scanf( "%d%d%d" , &q[i].k , &q[i].l , &q[i].r);
    cin >> k;
    int l = 1 , r = n , m , ans;
    while( l <= r ) {
        m = l + r >> 1;
        if( check(m) ) ans = m , l = m + 1;//最后这个位置上是1 , 那么选的数字大了
        else r = m - 1;
    }
    cout << ans;
}

然后ODT 开O2 随便跑

// luogu-judger-enable-o2
/*Heroes Never Die!*/
#include "iostream"
#include "cstring"
#include "cstdio"
#include "set"
#include "algorithm"
using namespace std;
#define MAXN 100006
int A[MAXN] , k , n , m;

struct query { int l , r , k ; } q[MAXN];

struct node{
    int l , r , v;
    node( int l , int r = -1 , int v = 0 ) :l(l) , r(r) ,v(v) {}
    node( ) {}
    bool operator < ( const node& t ) const {
        return l < t.l;
    }
};

set<node> S;

set<node>::iterator spli( int pos ) {
    auto it = S.lower_bound( node( pos ) );
    if( it != S.end( ) && it->l == pos ) return it; --it;
    int l = it->l , r = it->r , v = it->v;
    S.erase( it ) , S.insert( node( l , pos - 1 , v ) );
    return S.insert( node( pos , r , v ) ).first;
}
int countone( int l ,int r ) {
    auto itr = spli( r + 1 ) , itl = spli( l ); int res = 0;
    for( ; itl != itr ; ++ itl )
        if( itl->v == 1 ) res += itl->r - itl->l + 1;
    return res;
}

void change( int l , int  r , int v ) {
    auto itr = spli( r + 1 ) , itl = spli( l );
    S.erase( itl , itr ) , S.insert( node( l , r , v ) );
}

bool check( int x ) {
    S.clear();
    for( int i = 1 ; i <= n ; ++ i )
        S.insert( node( i , i , A[i] >= x ) );
    S.insert( node( n + 1 , n + 1 , -1 ) );
    for( int i = 1 ; i <= m ; ++ i ) {
        int l = q[i].l , r = q[i].r , k = q[i].k , numone = countone( l , r );
        if( !k ) change( r - numone + 1 , r , 1 ) , change( l , r - numone , 0 );
        else change( l , l + numone - 1 , 1 ) , change( l + numone , r , 0 );
    }
    return spli( k )->v == 1 ;
}

int main() {
    cin >> n >> m;
    for( int i = 1 ; i <= n ; ++ i ) scanf( "%d" , & A[i] );
    for( int i = 1 ; i <= m ; ++ i ) scanf( "%d%d%d" , &q[i].k , &q[i].l , &q[i].r);
    cin >> k;
    int l = 1 , r = n , m , ans;
    while( l <= r ) {
        m = l + r >> 1;
        if( check(m) ) ans = m , l = m + 1 ;//最后这个位置上是1 , 那么选的数字大了
        else r = m - 1;
    }
    cout << ans;
}

题真的敲好的说