NC19055. Generator and Monitor
描述
输入描述
The first line contains an integer T, the number of test cases.For each test case, the first line contains an integer m and n. The following n lines describe events. The i-th line describe the event happens at the i-th second. If the event is to give a condition, then it contains a character ”C” followed by li, ri and ci. Otherwise, the event is to generate a number and it contains a character ”G” followed by bi. ai, the number generated at the i-th second equals to the XOR sum of bi and the moments of all conditions met before i-th second.It is guaranteed that 1 ≤ m ≤ 104 and 1 ≤ n ≤ 2×105.
输出描述
For each test case, the output starts with a line ”Case #i:” where i is the test case number, starting from 1. Then you need to report the alerts in order. If some conditions are met at the i-th second, output a line containing i and moments when these conditions were given. Output moments in increasing order.
示例1
输入:
1 6 5 C 1 3 1 C 3 5 2 G 4 G 1 G 3 G 2
输出:
Case #1: 4 1 6 2
说明:
At the 1st second, a condition is given. We need to make an alert when 1 number in range [1, 3] are generated.C++14(g++5.4) 解法, 执行用时: 7015ms, 内存消耗: 18256K, 提交时间: 2018-10-07 13:30:28
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;
#define clr( a , x ) memset ( a , x , sizeof a )
const int MAXN = 200005 ;
const int MAXM = 10000005 ;
const int INF = 0x3f3f3f3f ;
struct Node {
int p[2] ;
int f , l , r , idx ;
int Min[2] , Max[2] ;
int minv , v , pos ;
int addv ;
int operator [] ( const int idx ) const {
return p[idx] ;
}
void init () {
Min[0] = Max[0] = p[0] ;
Min[1] = Max[1] = p[1] ;
pos = minv = v = INF ;
addv = 0 ;
}
void up ( Node& a ) {
Min[0] = min ( Min[0] , a.Min[0] ) ;
Max[0] = max ( Max[0] , a.Max[0] ) ;
Min[1] = min ( Min[1] , a.Min[1] ) ;
Max[1] = max ( Max[1] , a.Max[1] ) ;
}
void down ( int x ) {
if ( x ) minv += x , v += x , addv += x ;
}
} ;
struct Op {
int x , y , c ;
} ;
Op p[MAXN] ;
char buf[MAXM + 1] , *cur = buf ;
Node T[MAXN] ;
int idx[MAXN] ;
int root , cmpw , tot ;
int res[MAXN] ;
int n , m ;
bool cmp ( const Node& a , const Node& b ) {
return a.p[cmpw] < b.p[cmpw] ;
}
int build ( int l , int r , int w , int f ) {
int o = l + r >> 1 ;
cmpw = w ;
nth_element ( T + l , T + o , T + r + 1 , cmp ) ;
idx[T[o].idx] = o ;
T[o].init () ;
T[o].f = f ;
T[o].l = l != o ? build ( l , o - 1 , !w , o ) : 0 ;
T[o].r = r != o ? build ( o + 1 , r , !w , o ) : 0 ;
if ( T[o].l ) T[o].up ( T[T[o].l] ) ;
if ( T[o].r ) T[o].up ( T[T[o].r] ) ;
return o ;
}
int check ( int x1 , int x2 , int y1 , int y2 , int x ) {
if ( x2 <= x && y1 >= x ) return 0 ;
if ( x1 <= x && y2 >= x ) return 2 ;
return 1 ;
}
void up ( int o ) {
T[o].minv = T[o].v ;
T[o].pos = T[o].idx ;
if ( T[o].l && T[T[o].l].minv < T[o].minv ) {
T[o].minv = T[T[o].l].minv ;
T[o].pos = T[T[o].l].pos ;
}
if ( T[o].r && T[T[o].r].minv < T[o].minv ) {
T[o].minv = T[T[o].r].minv ;
T[o].pos = T[T[o].r].pos ;
}
}
void down ( int o ) {
int x = T[o].addv ;
if ( !x ) return ;
if ( T[o].l ) T[T[o].l].down ( x ) ;
if ( T[o].r ) T[T[o].r].down ( x ) ;
T[o].addv = 0 ;
}
void sign_down ( int o ) {
if ( T[o].f ) sign_down ( T[o].f ) ;
down ( o ) ;
}
void upd ( int o , int x , int v ) {
int d = check ( T[o].Min[0] , T[o].Max[0] , T[o].Min[1] , T[o].Max[1] , x ) ;
if ( !d ) {
T[o].down ( v ) ;
return ;
}
if ( d == 1 ) return ;
if ( T[o][0] <= x && T[o][1] >= x ) {
T[o].v += v ;
T[o].minv += v ;
}
down ( o ) ;
if ( T[o].l ) upd ( T[o].l , x , v ) ;
if ( T[o].r ) upd ( T[o].r , x , v ) ;
up ( o ) ;
}
void add ( int o , int v ) {
for ( sign_down ( o ) , T[o].v = v ; o ; o = T[o].f ) up ( o ) ;
}
void scanf ( int& x ) {
while ( *cur < '0' ) ++ cur ;
x = *cur - '0' , ++ cur ;
while ( *cur >= '0' ) ( x *= 10 ) += *cur - '0' , ++ cur ;
}
void solve () {
tot = 0 ;
scanf ( n ) ;
scanf ( m ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
char op ;
while ( ( op = *cur ) < 'A' ) ++ cur ;
++ cur ;
if ( op == 'C' ) {
scanf ( p[i].x ) ;
scanf ( p[i].y ) ;
scanf ( p[i].c ) ;
++ tot ;
T[tot].p[0] = p[i].x ;
T[tot].p[1] = p[i].y ;
T[tot].idx = i ;
} else p[i].c = 0 , scanf ( p[i].x ) ;
}
root = build ( 1 , tot , 0 , 0 ) ;
int now = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
if ( p[i].c ) add ( idx[i] , p[i].c ) ;
else upd ( root , p[i].x ^ now , -1 ) ;
int val = 0 , top = 0 ;
while ( !T[root].minv ) {
val ^= T[root].pos ;
res[++ top] = T[root].pos ;
add ( idx[T[root].pos] , INF ) ;
}
now ^= val ;
if ( top ) {
printf ( "%d" , i ) ;
sort ( res + 1 , res + top + 1 ) ;
for ( int j = 1 ; j <= top ; ++ j ) {
printf ( " %d" , res[j] ) ;
}
puts ( "" ) ;
}
}
}
int main () {
fread ( buf , 1 , MAXM , stdin ) ;
int T ;
scanf ( T ) ;
for ( int i = 1 ; i <= T ; ++ i ) {
printf ( "Case #%d:\n" , i ) ;
solve () ;
}
return 0 ;
}
C++11(clang++ 3.9) 解法, 执行用时: 7394ms, 内存消耗: 18156K, 提交时间: 2018-10-07 16:01:18
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;
#define clr( a , x ) memset ( a , x , sizeof a )
const int MAXN = 200005 ;
const int MAXM = 10000005 ;
const int INF = 0x3f3f3f3f ;
struct Node {
int p[2] ;
int f , l , r , idx ;
int Min[2] , Max[2] ;
int minv , v , pos ;
int addv ;
int operator [] ( const int idx ) const {
return p[idx] ;
}
void init () {
Min[0] = Max[0] = p[0] ;
Min[1] = Max[1] = p[1] ;
pos = minv = v = INF ;
addv = 0 ;
}
void up ( Node& a ) {
Min[0] = min ( Min[0] , a.Min[0] ) ;
Max[0] = max ( Max[0] , a.Max[0] ) ;
Min[1] = min ( Min[1] , a.Min[1] ) ;
Max[1] = max ( Max[1] , a.Max[1] ) ;
}
void down ( int x ) {
if ( x ) minv += x , v += x , addv += x ;
}
} ;
struct Op {
int x , y , c ;
} ;
Op p[MAXN] ;
char buf[MAXM + 1] , *cur = buf ;
Node T[MAXN] ;
int idx[MAXN] ;
int root , cmpw , tot ;
int res[MAXN] ;
int n , m ;
bool cmp ( const Node& a , const Node& b ) {
return a.p[cmpw] < b.p[cmpw] ;
}
int build ( int l , int r , int w , int f ) {
int o = l + r >> 1 ;
cmpw = w ;
nth_element ( T + l , T + o , T + r + 1 , cmp ) ;
idx[T[o].idx] = o ;
T[o].init () ;
T[o].f = f ;
T[o].l = l != o ? build ( l , o - 1 , !w , o ) : 0 ;
T[o].r = r != o ? build ( o + 1 , r , !w , o ) : 0 ;
if ( T[o].l ) T[o].up ( T[T[o].l] ) ;
if ( T[o].r ) T[o].up ( T[T[o].r] ) ;
return o ;
}
int check ( int x1 , int x2 , int y1 , int y2 , int x ) {
if ( x2 <= x && y1 >= x ) return 0 ;
if ( x1 <= x && y2 >= x ) return 2 ;
return 1 ;
}
void up ( int o ) {
T[o].minv = T[o].v ;
T[o].pos = T[o].idx ;
if ( T[o].l && T[T[o].l].minv < T[o].minv ) {
T[o].minv = T[T[o].l].minv ;
T[o].pos = T[T[o].l].pos ;
}
if ( T[o].r && T[T[o].r].minv < T[o].minv ) {
T[o].minv = T[T[o].r].minv ;
T[o].pos = T[T[o].r].pos ;
}
}
void down ( int o ) {
int x = T[o].addv ;
if ( !x ) return ;
if ( T[o].l ) T[T[o].l].down ( x ) ;
if ( T[o].r ) T[T[o].r].down ( x ) ;
T[o].addv = 0 ;
}
void sign_down ( int o ) {
if ( T[o].f ) sign_down ( T[o].f ) ;
down ( o ) ;
}
void upd ( int o , int x , int v ) {
int d = check ( T[o].Min[0] , T[o].Max[0] , T[o].Min[1] , T[o].Max[1] , x ) ;
if ( !d ) {
T[o].down ( v ) ;
return ;
}
if ( d == 1 ) return ;
if ( T[o][0] <= x && T[o][1] >= x ) {
T[o].v += v ;
T[o].minv += v ;
}
down ( o ) ;
if ( T[o].l ) upd ( T[o].l , x , v ) ;
if ( T[o].r ) upd ( T[o].r , x , v ) ;
up ( o ) ;
}
void add ( int o , int v ) {
for ( sign_down ( o ) , T[o].v = v ; o ; o = T[o].f ) up ( o ) ;
}
void scanf ( int& x ) {
while ( *cur < '0' ) ++ cur ;
x = *cur - '0' , ++ cur ;
while ( *cur >= '0' ) ( x *= 10 ) += *cur - '0' , ++ cur ;
}
void solve () {
tot = 0 ;
scanf ( n ) ;
scanf ( m ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
char op ;
while ( ( op = *cur ) < 'A' ) ++ cur ;
++ cur ;
if ( op == 'C' ) {
scanf ( p[i].x ) ;
scanf ( p[i].y ) ;
scanf ( p[i].c ) ;
++ tot ;
T[tot].p[0] = p[i].x ;
T[tot].p[1] = p[i].y ;
T[tot].idx = i ;
} else p[i].c = 0 , scanf ( p[i].x ) ;
}
root = build ( 1 , tot , 0 , 0 ) ;
int now = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
if ( p[i].c ) add ( idx[i] , p[i].c ) ;
else upd ( root , p[i].x ^ now , -1 ) ;
int val = 0 , top = 0 ;
while ( !T[root].minv ) {
val ^= T[root].pos ;
res[++ top] = T[root].pos ;
add ( idx[T[root].pos] , INF ) ;
}
now ^= val ;
if ( top ) {
printf ( "%d" , i ) ;
sort ( res + 1 , res + top + 1 ) ;
for ( int j = 1 ; j <= top ; ++ j ) {
printf ( " %d" , res[j] ) ;
}
puts ( "" ) ;
}
}
}
int main () {
fread ( buf , 1 , MAXM , stdin ) ;
int T ;
scanf ( T ) ;
for ( int i = 1 ; i <= T ; ++ i ) {
printf ( "Case #%d:\n" , i ) ;
solve () ;
}
return 0 ;
}