题目
比赛界面。
T1
比较简单。容易想到是求鱼竿的最大独立集。由于题目的鱼竿可以被分割为二分图，就可以想到最大匹配。
尝试建边之后会发现边的数量不小，但联系题目性质会发现对于一条鱼竿，它会影响的垂直方向上的鱼竿一定是一个区间，因此再套一发线段树优化即可。
这里不建议写倍增优化，因为倍增的点是\(O(n\log_2n)\)，而网络流的时间是\(O(n^2m)\)，因此可能会慢一些。
当然，你知道，这细网咯流咩......时间复杂度还是比较emmmm......的
代码：
#include <cstdio>
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 5, MAXE = 1e6 + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
struct edge
{
int to, nxt, w;
}Graph[MAXN << 1];
const int S = 1, T = 2;
int ID[MAXN], q[MAXN];
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int head[MAXN], dep[MAXN], cur[MAXN];
int N, cnt = 1, siz = 2;
void addEdge( const int from, const int to, const int W )
{
Graph[++ cnt].to = to, Graph[cnt].nxt = head[from], Graph[cnt].w = W;
head[from] = cnt;
}
void addE( const int from, const int to, const int W )
{
addEdge( from, to, W ), addEdge( to, from, 0 );
}
bool build( const int u, const int l, const int r )
{
if( l > r ) return false;
ID[u] = ++ siz;
if( l == r ) { addE( siz, T, 1 ); return true; }
int mid = l + r >> 1;
if( build( u << 1, l, mid ) ) addE( ID[u], ID[u << 1], INF );
if( build( u << 1 | 1, mid + 1, r ) ) addE( ID[u], ID[u << 1 | 1], INF );
return true;
}
void update( const int u, const int l, const int r, const int segL, const int segR, const int sta )
{
if( segL > segR ) return ;
if( segL <= l && r <= segR ) { addE( sta, ID[u], INF ); return ; }
int mid = l + r >> 1;
if( segL <= mid ) update( u << 1, l, mid, segL, segR, sta );
if( mid < segR ) update( u << 1 | 1, mid + 1, r, segL, segR, sta );
}
bool BFS( const int Sta, const int Tar )
{
int h = 1, t = 0, u;
for( int i = 1 ; i <= siz ; i ++ ) dep[i] = INF;
dep[q[++ t] = Sta] = 0;
while( h <= t )
{
u = q[h ++];
for( int i = head[u], v ; i ; i = Graph[i].nxt )
if( Graph[i].w && dep[v = Graph[i].to] == INF )
dep[q[++ t] = v] = dep[u] + 1;
}
return dep[Tar] < INF;
}
int DFS( const int u, const int lin, const int T )
{
if( u == T ) return lin;
int v, w, used = 0, res = 0;
for( int &i = cur[u] ; i ; i = Graph[i].nxt )
{
v = Graph[i].to, w = Graph[i].w;
if( dep[v] == dep[u] + 1 && w && ( res = DFS( v, MIN( lin - used, w ), T ) ) )
{
used += res, Graph[i].w -= res, Graph[i ^ 1].w += res;
if( used == lin ) break;
}
}
if( used < lin ) dep[u] = INF;
return used;
}
int Dinic()
{
int ret = 0;
while( BFS( S, T ) )
{
for( int i = 1 ; i <= siz ; i ++ ) cur[i] = head[i];
ret += DFS( S, INF, T );
}
return ret;
}
int main()
{
freopen( "B.in", "r", stdin );
freopen( "B.out", "w", stdout );
read( N );
for( int i = 1 ; i <= N ; i ++ ) read( a[i] );
for( int i = 1 ; i <= N ; i ++ ) read( b[i] );
for( int i = 1 ; i <= N ; i ++ ) read( c[i] );
for( int i = 1 ; i <= N ; i ++ ) read( d[i] );
for( int i = 1 ; i <= N << 1 ; i ++ ) addE( S, ++ siz, 1 );
//Up and Down
int lmost, rmost;
build( 1, 1, N << 1 );
for( int i = 1 ; i <= N ; i ++ )
{
lmost = INF, rmost = -INF;
for( int j = 1 ; j <= a[i] ; j ++ ) if( c[j] >= i ) { lmost = j; break; }
for( int j = a[i] ; j ; j -- ) if( c[j] >= i ) { rmost = j; break; }
update( 1, 1, N << 1, lmost, rmost, i + 2 );
lmost = INF, rmost = -INF;
for( int j = 1 ; j <= a[i] ; j ++ ) if( d[j] > N - i ) { lmost = j; break; }
for( int j = a[i] ; j ; j -- ) if( d[j] > N - i ) { rmost = j; break; }
update( 1, 1, N << 1, lmost + N, rmost + N, i + 2 );
lmost = INF, rmost = -INF;
for( int j = N - b[i] + 1 ; j <= N ; j ++ ) if( c[j] >= i ) { lmost = j; break; }
for( int j = N ; j > N - b[i] ; j -- ) if( c[j] >= i ) { rmost = j; break; }
update( 1, 1, N << 1, lmost, rmost, i + N + 2 );
lmost = INF, rmost = -INF;
for( int j = N - b[i] + 1 ; j <= N ; j ++ ) if( d[j] > N - i ) { lmost = j; break; }
for( int j = N ; j > N - b[i] ; j -- ) if( d[j] > N - i ) { rmost = j; break; }
update( 1, 1, N << 1, lmost + N, rmost + N, i + N + 2 );
}
write( 4 * N - Dinic() ), putchar( '\n' );
return 0;
}
T2
非常比较难受的题目。
考虑\(5\sim7\)的部分分，可以想到一个做法：设\(suf(i)\)为\(\min\{j|j\in(i,n],a_j=a_i+1\}\)（不存在则为\(n+1\)）。那么我们求解的过程实际上就是在询问区间的范围内，尝试在\(suf\)上走最远。
由于没有修改，因此\(suf\)也不会变，我们就可以倍增一发，然后询问的复杂度就降下来了。
时间复杂度\(O(n\log_2n)-O(q\log_2n)\)。
考虑把上面的做法扩展到可修改。不难发现，如果从\(i\)向\(suf(i)\)连边，那么我们可以得到一棵树。于是我们就想到了使用 LCT 。
不过，还有问题是，如果树变成了菊花图（比如\(1,1,1,1,...,2\)）的情况，那么对根的修改的复杂度将会大得无法接受。
对于这个问题，我们重新构树——\(suf(i)\)变成\(\min\{j|j\in(i,n],a_j=a_i+1\lor a_j=a_i\}\)。这样的话，树最多是二叉的，修改的时间就可降下来。我们对于\(a_i=a_{suf(i)}\)的点，将它点权赋 0 ，对于另一类点赋 1 ，这样链上的点权和就可以对应到询问答案。
用 set 维护每种颜色的点的出现位置。修改的时候，把所有会被影响的点都拉出来改一遍；查询的时候，先找到区间里面第一个\(k\)的位置\(p\)，再在 LCT 上找出\([l,r]\)区间中最后一个在\(p\)到根的链上的点，然后求解。
时间\(O(n\log_2n)-O(q\log_2n)\)。
代码：
#include <set>
#include <cstdio>
using namespace std;
typedef set<int> :: iterator iter;
const int MAXN = 1e6 + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
void swapp( _T &x, _T &y )
{
_T t = x; x = y, y = t;
}
template<typename _T>
_T MIN( const _T a, const _T b )
{
return a < b ? a : b;
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
set<int> pos[MAXN];
int ch[MAXN][2], fa[MAXN], val[MAXN], su[MAXN];
int a[MAXN], nxt[MAXN];
int N, Q;
bool rev[MAXN];
bool chk( const int x ) { return ch[fa[x]][1] == x; }
void upt( const int x ) { su[x] = su[ch[x][0]] + su[ch[x][1]] + val[x]; }
bool isRt( const int x ) { return ch[fa[x]][0] ^ x && ch[fa[x]][1] ^ x; }
bool nrt( const int x ) { return ! isRt( x ); }
void reverse( const int x ) { if( x ) swapp( ch[x][0], ch[x][1] ), rev[x] ^= 1; }
void normalize( const int x ) { if( x && rev[x] ) reverse( ch[x][0] ), reverse( ch[x][1] ), rev[x] = false; }
void tagClean( const int x ) { if( nrt( x ) ) tagClean( fa[x] ); normalize( x ); }
void rotate( const int x )
{
if( ! x || isRt( x ) ) return ;
int y = fa[x], z = fa[y], side = chk( x ), son = ch[x][! side];
if( z && nrt( y ) ) ch[z][chk( y )] = x; ch[x][! side] = y, ch[y][side] = son;
if( son ) fa[son] = y; fa[y] = x, fa[x] = z;
upt( y ), upt( x ), upt( z );
}
void splay( const int x )
{
tagClean( x );
for( int y ; nrt( x ) ; rotate( x ) )
if( nrt( y = fa[x] ) )
rotate( chk( y ) == chk( x ) ? y : x );
}
void access( int x ) { for( int y = 0 ; x ; x = fa[y = x] ) splay( x ), ch[x][1] = y, upt( x ); }
void makeRt( const int x ) { access( x ), splay( x ), reverse( x ); }
int findRt( int x ) { access( x ), splay( x ); while( ch[x][0] ) normalize( x ), x = ch[x][0]; splay( x ); return x; }
void link( const int x, const int y ) { makeRt( x ); if( findRt( y ) == x ) return; fa[x] = y; }
void cut( const int x, const int y )
{
makeRt( x ), access( y ), splay( x );
fa[y] = ch[x][1] = 0, upt( x );
}
int query( const int u, const int r )
{
makeRt( N + 1 ), access( u ), splay( N + 1 );
int cur = N + 1, rp = 0; normalize( cur );
while( ch[cur][cur > r] )
{
if( cur == r ) break;
normalize( cur ), cur = ch[cur][cur > r];
if( cur <= r ) rp = MAX( rp, cur );
}
makeRt( rp );
access( u );
splay( rp );
return su[rp] - val[rp];
}
void linkto( const int i, const int v )
{
iter nxa = pos[v].lower_bound( i + 1 ),
nxb = pos[v + 1].lower_bound( i );
nxt[i] = MIN( *nxa, *nxb );
val[i] = nxt[i] == *nxb, upt( i ), link( i, nxt[i] );
}
void relink( const int i, const int sid )
{
iter cur = pos[sid].lower_bound( i );
if( cur != pos[sid].begin() )
{
int p = *( -- cur );
cut( p, nxt[p] );
linkto( p, a[p] );
}
}
int main()
{
int opt, x, y, z;
read( N ), read( Q );
for( int i = 1 ; i <= N ; i ++ ) read( a[i] ), pos[a[i]].insert( i );
for( int i = 1 ; i <= N + 1 ; i ++ ) pos[i].insert( N + 1 );
for( int i = 1 ; i <= N ; i ++ ) linkto( i, a[i] );
while( Q -- )
{
read( opt ), read( x ), read( y );
if( opt == 1 )
{
int lst = a[x]; a[x] = y;
pos[lst].erase( x ), pos[y].insert( x );
relink( x, lst );
relink( x, lst - 1 );
relink( x, y );
relink( x, y - 1 );
cut( x, nxt[x] );
linkto( x, a[x] );
//link
}
else
{
read( z );
iter p = pos[z].lower_bound( x );
int lmost = *p;
if( lmost > y ) puts( "-1" );
else write( query( lmost, y ) ), putchar( '\n' );
}
}
return 0;
}
T3
构造题目。
首先发现题目一定有解。
我们现在在\(A=[0,a)\)和\(B=[b,b+a)\)里面进行匹配。假设它们都在\([0,2^n)\)中。
如果\(A\cap B\not=\varnothing\)，那么我们就可以进行匹配，直到\(A\cap B=\varnothing\)。
此时\(A\)一定是在\([0,2^{n-1})\)里面（否则\(B\)就会超过\(2^n\)）。
那么\(A\)就可以直接折到\([0,2^{n-1})\)里面来。考虑\(B\)的分布情况。
1. \(B\)的元素在二进制\(n-1\)位上相同，那么对它们全部模\(2^{n-1}\)之后，它们就落在了区间\([b',b'+a')\)中，可以继续和\(A\)匹配，规模减半。
2. \(B\)的元素在二进制\(n-1\)位上不同，那么取模之后一定是\([x,2^{n-1})\cup [0,y)\)的形式。我们可以将\([0,y)\)和\(A\)中的元素匹配。剩下的继续匹配，返回的匹配结果可以映射到当前的结果上来。
代码：
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
const int MAXN = 1e6 + 5;
int N, M;
void match( int n, int m, int addn, int addm, vector<int> &res )
{
if( ! n ) return ;
int k = 1;
while( k < n ) k <<= 1;
m &= k - 1;
if( m < n )
{
for( int i = 0 ; i < n - m ; i ++ )
res[i + addm] = i + m + addn;
match( m, n, addn, addm + n - m, res );
}
else
{
int q = k - m;
for( int i = 0 ; i < n + m - k ; i ++ )
res[addm + q + i] = addn + i;
vector<int> tmp( q );
match( q, k - n, 0, 0, tmp );
for( int i = 0 ; i < q ; i ++ )
res[q - tmp[i] - 1 + addm] = n - 1 - i + addn;
}
}
int main()
{
scanf( "%d %d", &N, &M );
vector<int> ans( N );
match( N, M, 0, 0, ans );
for( int i = 0 ; i < N ; i ++ )
printf( "%d %d\n", ans[i], i + M );
return 0;
}