刚学OI 求救 odt写炸了

P2572 [SCOI2010] 序列操作

_louhc @ 2019-01-12 23:07:04

蜜汁RE*8(刚学的odt)

#include<bits/stdc++.h>
using namespace std;

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

#define IT set<node>::iterator
set<node> S;

void print(){
    for ( IT i = S.begin(); i != S.end(); ++i ) printf( "%d  %d  %d\n", i->l, i->r, i->val );
}

inline IT Split( int pos ){
    IT t(S.lower_bound(node(pos)));
    if ( t != S.end() && t->l == pos ) return t;
    t--;
    int L(t->l), R(t->r); bool v(t->val);
    S.erase(t);
    S.insert( node( L, pos - 1, v ) );
    return S.insert( node( pos, R, v ) ).first;
}

inline void Assign( int L, int R, bool v ){
    IT it1(Split(L)), it2(Split(R + 1));
    S.erase( it1, it2 );
    S.insert(node( L, R, v ));
}

inline void Change( int l, int r ){
    IT be(Split(l)), ed(Split(r + 1));
    for ( IT it = be; it != ed; ++it ) it->val = !(it->val);
}

inline int Get1( int l, int r ){
    IT be(Split(l)), ed(Split(r + 1)); int ans(0);
    for ( IT it = be; it != ed; ++it ) if ( it->val ) ans += (it->r) - (it->l) + 1;
    return ans;
}

inline int Get2( int l, int r ){
    IT be(Split(l)), ed(Split(r + 1)); int ans(0), cur(0);
    for ( IT it = be; it != ed; ++it )
        if ( it->val ) cur += (it->r) - (it->l) + 1;
        else ans = max( ans, cur ), cur = 0;
    ans = max( ans, cur );
    return ans;
}

int N, M, t, ls;
int a[100005];

int main(){
    scanf( "%d%d", &N, &M ); ls = 1;
    for ( int i = 1; i <= N; ++i ) scanf( "%d", &a[i] );
    for ( int i = 2; i <= N; ++i ) if ( a[i] ^ a[i - 1] ) S.insert( node( ls, i - 1, a[i - 1] ) ), ls = i;
    S.insert( node( ls, N, a[N] ) ); 
    for ( int i = 1; i <= M; ++i ){
        int op, a, b; scanf( "%d%d%d", &op, &a, &b ); a++; b++;
        if ( op < 2 ) Assign( a, b, op );
        if ( op == 2 ) Change( a, b );
        if ( op == 3 ) printf( "%d\n", Get1( a, b ) );
        if ( op == 4 ) printf( "%d\n", Get2( a, b ) );
    }
    return 0;
} 

by NaCly_Fish @ 2019-01-13 00:10:19

ODT是啥


by NaCly_Fish @ 2019-01-13 00:10:31

@Sinner QAQ


by 星灵王小号 @ 2019-01-13 01:01:07

刚学OI做紫题,ODT是啥抱歉我母鸡


by star_city @ 2019-01-13 01:51:35

老司机珂树?


by 少名针妙丸 @ 2019-01-13 06:22:01

我怀疑这题ODT复杂度不对


by Aleph1022 @ 2019-01-13 07:19:34

@Sinner 把所有的 IT be(Split(l)), ed(Split(r + 1)); 反过来试试,先 r + 1


by Qiuly @ 2019-01-13 08:05:48

%%%


by _louhc @ 2019-01-13 08:06:41

@alpha1022 还是不行QAQ


by _louhc @ 2019-01-13 08:21:15

@alpha1022 哦 我只改了Split(l)和Split(r)的位置,没有换be和ed的位置QAQ
你是对的 现在过了
但是求教为什么(我好菜呀


by Aleph1022 @ 2019-01-13 10:52:48

@Sinner 我也不知道


| 下一页