2014
11-27

# Fast Arrangement

Chinese always have the railway tickets problem because of its’ huge amount of passangers and stations. Now goverment need you to develop a new tickets query system.
One train can just take k passangers. And each passanger can just buy one ticket from station a to station b. Each train cannot take more passangers any time. The one who buy the ticket earlier which can be sold will always get the ticket.

The input contains servel test cases. The first line is the case number. In each test case:
The first line contains just one number k( 1 ≤ k ≤ 1000 ) and Q( 1 ≤ Q ≤ 100000 )
The following lines, each line contains two integers a and b, ( 1 ≤ a < b ≤ 1000000 ), indicate a query.
Huge Input, scanf recommanded.

The input contains servel test cases. The first line is the case number. In each test case:
The first line contains just one number k( 1 ≤ k ≤ 1000 ) and Q( 1 ≤ Q ≤ 100000 )
The following lines, each line contains two integers a and b, ( 1 ≤ a < b ≤ 1000000 ), indicate a query.
Huge Input, scanf recommanded.

1
3 6
1 6
1 6
3 4
1 5
1 2
2 4

Case 1:
1 2 3 5 

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define lc rt << 1
#define rc rt << 1 | 1

using namespace std;

const int MAXN = 1000100;

struct node
{
int l, r;
};

node D[MAXN];
int limit, Q;
int maxi[ MAXN << 2 ];
int lazy[ MAXN << 2 ];
int N;

void build( int l, int r, int rt )
{
maxi[rt] = lazy[rt] = 0;
if ( l == r ) return;
int m = ( l + r ) >> 1;
build( lson );
build( rson );
return;
}

void PushUp( int rt )
{
maxi[rt] = max( maxi[lc], maxi[rc] );
return;
}

void PushDown( int rt )
{
if ( lazy[rt] )
{
lazy[lc] += lazy[rt];
lazy[rc] += lazy[rt];
maxi[lc] += lazy[rt];
maxi[rc] += lazy[rt];
lazy[rt] = 0;
}
return;
}

void update( int L, int R, int l, int r, int rt )
{
if ( L <= l && r <= R )
{
lazy[rt] += 1;
maxi[rt] += 1;
return;
}
PushDown( rt );
int m = ( l + r ) >> 1;
if ( L <= m ) update( L, R, lson );
if ( R > m )  update( L, R, rson );
PushUp( rt );
return;
}

int query( int L, int R, int l, int r, int rt )
{
if ( L <= l && r <= R )
{
return maxi[rt];
}
PushDown( rt );
int m = ( l + r ) >> 1;

int res = -10;
if ( L <= m ) res = max( res, query( L, R, lson ) );
if ( R > m )  res = max( res, query( L, R, rson ) );
PushUp( rt );
return res;
}

int main()
{
int T, cas = 0;
scanf( "%d", &T );
while ( T-- )
{
scanf( "%d%d", &limit, &Q );
N = 0;
for ( int i = 0; i < Q; ++i )
{
int u, v;
scanf( "%d%d", &u, &v );
N = max( N, v );
--v;
D[i].l = u, D[i].r = v;
}

build( 1, N, 1 );
printf( "Case %d:\n", ++cas );
for ( int i = 0; i < Q; ++i )
{
int ans = query( D[i].l, D[i].r, 1, N, 1 );
if ( ans < limit )
{
printf( "%d ", i + 1 );
update( D[i].l, D[i].r, 1, N, 1 );
}
}
puts("\n");
}
return 0;
}

1. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。

2. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮