A Four Points
题目大意
给定矩形的三个顶点,求其剩下的顶点。
思路
签到
B Get Closer
题目大意
给定直线过点 $(0,0)$, $(a,b)$,求从 $(0,0)$ 出发,方向朝右,长度为一的线段的右端点。
思路
一开始是二分硬做的,然后被卡精度了。
求出两点距离,对 $a,b$ 分别除于这个这个距离即可。
Continue reading “Atcoder Beginner Contest 246 解题报告”「Jump up HIGH!!」
给定矩形的三个顶点,求其剩下的顶点。
签到
给定直线过点 $(0,0)$, $(a,b)$,求从 $(0,0)$ 出发,方向朝右,长度为一的线段的右端点。
一开始是二分硬做的,然后被卡精度了。
求出两点距离,对 $a,b$ 分别除于这个这个距离即可。
Continue reading “Atcoder Beginner Contest 246 解题报告”很明显,这个题目需要我们维护 $ n + 1 $ 个序列
这些序列要支持
动点脑子的话,树状树组上二分也是可行的,反正我不会
不动脑子的话, Splay 下高问题也不大
如果把每个节点都单独储存的话,空间 $O(n + m)$ 承受不能
但是考虑到总修改次数很小,而且 Splay 维护的很多节点都是连续的
所以可以让 Splay 把连续的区间当作一个节点
空间问题就解决了
这样时间大概是 $O(q\log m)$ 的…
但是 Splay 的常数巨大…
于是就被 LibreOJ 无情卡常了
大概大力卡还是能过,但是我懒得搞了,反正 Luogu 上过了
#include <cstdio>
inline long long seg_len( long long left, long long rig ) { return rig - left + 1; }
template <class T>
T read() {
T res = 0; char x = getchar();
while( x < '0' || x > '9' ) {
x = getchar();
continue;
}
while( x >= '0' && x <= '9' ) {
res = res * 10 + x - '0';
x = getchar();
}
return res;
}
int st_cnt, st[30];
template <class T>
void write( T res ) {
while( res ) {
st_cnt ++;
st[ st_cnt ] = res % 10;
res /= 10;
}
while( st_cnt ) {
putchar( st[ st_cnt ] + '0' );
st_cnt --;
}
}
const int N = 3e5 + 1e4;
int n, m, q;
struct splay_node {
splay_node *son[2], *fa;
long long left, rig, size;
splay_node( long long _left = 0, long long _rig = 0 ) {
son[0] = son[1] = fa = 0; size = seg_len( _left, _rig );
left = _left, rig = _rig;
}
void push_up() {
this -> size = ( this -> son[0]? this -> son[0] -> size: 0 )
+ ( this -> son[1]? this -> son[1] -> size: 0 )
+ seg_len( left, rig );
}
bool get_son() {
if( this -> fa && this -> fa -> son[1] )
return ( this -> fa -> son[1] ) == this;
return 0;
}
inline long long len() { return seg_len( this -> left, this -> rig ); }
};
struct Splay {
splay_node *rt;
void init( long long left, long long rig ) {
splay_node *c = new splay_node( left, rig );
rt = c;
rt -> push_up();
}
void rotate( splay_node *cur ) {
bool kind = cur -> get_son();
splay_node *tmp_fa = cur -> fa;
if( tmp_fa == 0 )
return ;
if( tmp_fa -> fa == 0 )
rt = cur;
else
tmp_fa -> fa -> son[ tmp_fa -> get_son() ] = cur;
cur -> fa = tmp_fa -> fa;
tmp_fa -> son[kind] = cur -> son[ kind ^ 1 ];
if( tmp_fa -> son[kind] )
tmp_fa -> son[kind] -> fa = tmp_fa;
cur -> son[ kind ^ 1 ] = tmp_fa; tmp_fa -> fa = cur;
tmp_fa -> push_up(); cur -> push_up();
}
void splay( splay_node *from, splay_node *to = 0 ) {
while( from -> fa != to ) {
splay_node *fa = from -> fa;
if( fa -> fa != to )
rotate( ( fa -> get_son() ) == ( from -> get_son() )? fa: from );
rotate(from);
}
}
splay_node* find_kth( long long k ) {
if( k == 0 )
return 0;
splay_node *cur = rt;
while( cur ) {
if( cur -> son[0] ) {
if( cur -> son[0] -> size < k )
k -= cur -> son[0] -> size;
else {
cur = cur -> son[0];
continue;
}
}
if( k <= cur -> len() )
break;
k -= cur -> len();
if( cur -> son[1] ) {
cur = cur -> son[1];
continue;
}
return 0;
}
return cur;
}
splay_node* split_kth( long long k ) {/*{{{*/
splay_node *cur = find_kth(k); splay(cur);
if( cur -> son[0] )
k -= cur -> son[0] -> size;
k = ( cur -> left ) + k - 1;
splay_node *ori_left = cur -> son[0], *ori_rig = cur -> son[1],
*left = 0, *rig = 0, *mid;
mid = new splay_node( k, k );
if( cur -> left <= k - 1 ) {
left = new splay_node( cur -> left, k - 1 );
left -> fa = mid;
}
if( k + 1 <= cur -> rig ) {
rig = new splay_node( k + 1, cur -> rig );
rig -> fa = mid;
}
mid -> son[0] = left; mid -> son[1] = rig;
splay_node *tmp_left = (left? left: mid), *tmp_rig = (rig? rig: mid);
tmp_left -> son[0] = ori_left; tmp_rig -> son[1] = ori_rig;
if( ori_left )
ori_left -> fa = tmp_left;
if( ori_rig )
ori_rig -> fa = tmp_rig;
if( left )
left -> push_up();
if( rig )
rig -> push_up();
mid -> push_up();
if( rt == cur )
rt = mid;
delete( cur );
return mid;
}/*}}}*/
void del_kth( long long k ) {
splay_node *cur = split_kth(k);
splay_node *left = find_kth( k - 1 ), *rig = find_kth( k + 1 );
if( left == 0 || rig == 0 ) {
splay( cur );
rt = ( cur -> son[ left == 0 ] ); rt -> fa = 0;
delete( cur );
return ;
}
splay( left ); splay( rig, left );
delete( rt -> son[1] -> son[0] );
rt -> son[1] -> son[0] = 0;
rt -> son[1] -> push_up(); rt -> push_up();
}
void pull_up( splay_node *cur ) {
if( cur ) {
cur -> push_up();
pull_up( cur -> fa );
}
}
splay_node* push_back( long long val ) {
splay_node *cur = rt;
while( cur ) {
if( cur -> son[1] ) {
cur = cur -> son[1];
continue;
}
cur -> son[1] = new splay_node( val, val );
cur -> son[1] -> fa = cur;
cur = cur -> son[1];
break;
}
pull_up( cur );
splay(cur);
return cur;
}
#ifdef debug
void zxbl( splay_node *cur ) {
if( cur == 0 )
return ;
zxbl( cur -> son[0] );
for( int i = cur -> left; i <= cur -> rig; i ++ )
printf( "%2lld ", i );
zxbl( cur -> son[1] );
}
void _zxbl() {
zxbl( this -> rt );
}
#endif
} T[N];
int main() {
#ifdef woshiluo
freopen( "luogu.3960.in", "r", stdin );
freopen( "luogu.3960.out", "w", stdout );
#endif
n = read<int>(); m = read<int>(); q = read<int>();
T[0].init( m, m );
T[1].init( 1, m - 1 );
for( int i = 2; i <= n; i ++ ){
T[i].init( 1LL * ( i - 1 ) * m + 1, 1LL * i * m - 1 );
T[0].push_back( 1LL * i * m );
}
while( q -- ) {
int x, y;
x = read<int>(); y = read<int>();
if( y == m ) {
long long cur = T[0].split_kth(x) -> left;
write(cur);
printf( "\n" );
T[0].push_back(cur); T[0].del_kth(x);
}
else {
Splay &tree = T[x];
long long cur = tree.split_kth(y) -> left;
write(cur);
printf( "\n" );
tree.push_back( T[0].split_kth(x) -> left ); tree.del_kth(y);
T[0].push_back(cur); T[0].del_kth(x);
}
#ifdef debug
printf( "%d %d\n", x, y );
for( int i = 0; i <= n; i ++ ) {
printf( "T[%d]: ", i );
T[i]._zxbl();
printf( "\n" );
}
#endif
}
}