_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));
反过来试试,先
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 我也不知道