传送门：【BZOJ】4130: [PA2011]Kangaroos【KD树】

题意：给出一个长度为$N(N\leq 5\cdot 10^4)$的区间序列。然后接下来$M(M\leq 2\cdot 10^5)$个询问，每个询问给出一个区间$[L,R]$，问区间序列中最长的连续子序列长度，使得连续子序列中每个区间和询问给出的区间存在交集。

分析：将询问$[L,R]$看成平面点$(L,R)$，构建$KD$树。将区间序列看成操作，每次操作是将一个矩阵范围+1，或者置0，那么对每个询问的点，其实就是其曾经连续被加的长度最长是多少。对于一个$[L,R]$（序列中的点），询问$(x,y)$如果和其有交集，则须满足$y\leq L$，$x\geq R$。

转化成这个之后接下来就是各种奇（e）怪（xin）的做法了。我的做法是，维护$KD$树每个节点5个标记，自己的出现过的最大值，自己的最近一次被置0的时刻，所代表区域的出现过的最大值，所代表区域最近一次被置0的时刻，所代表区域最早一次被置0的时刻。然后对于一个区域+1的更新，如果当前节点代表区域完全不在+1区域内,则这个区域我们修改一下他的置0标记（之后我们详细解释如何修改）。如果整个区域都要被+1,则直忽略。如果只是部分要+1,那么先判一下节点自己是不是要被修改（即置零），然后递归下去。

根据最早置0的时刻以及最晚置0的时刻，我们可以很方便的完成标记的下传，即被下传的节点的最大值变成下传节点最早减去当前最晚的，然后当前最晚变成下传的节点的最晚的。相当于把下传节点和被下传节点的信息压在一起。然后对于节点自己的更新，类似。

这题还有很多奇（gui）怪（chu）的写法，我觉得我这个已经算比较简单的了……

$my~~~code:$

#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 ;struct Edge {int v , n ;Edge () {}Edge ( int v , int n ) : v ( v ) , n ( n ) {}
} ;struct Node {int p[2] ;int f , l , r ;int Min[2] , Max[2] ;int maxv[2] , mins , maxs[2] ;int operator [] ( const int idx ) const {return p[idx] ;}void init () {Min[0] = Max[0] = p[0] ;Min[1] = Max[1] = p[1] ;mins = 0 ;maxs[0] = maxs[1] = 0 ;maxv[0] = maxv[1] = 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 , int y ) {if ( x != -1 ) {if ( mins != -1 ) maxv[0] = max ( maxv[0] , x - maxs[0] - 1 ) ;else mins = x ;maxv[1] = max ( maxv[1] , x - maxs[1] - 1 ) ;maxs[0] = maxs[1] = y ;}}
} ;char buf[MAXM + 1] , *cur = buf ;
Node T[MAXN] ;
int idx[MAXN] ;
int root , cmpw ;
int X[MAXN] , Y[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].f] = o ;T[o].f = f ;T[o].init () ;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 , int y ) {int cnt = 0 ;if ( x1 <= x && y1 >= y ) ++ cnt ;if ( x1 <= x && y2 >= y ) ++ cnt ;if ( x2 <= x && y1 >= y ) ++ cnt ;if ( x2 <= x && y2 >= y ) ++ cnt ;if ( cnt == 4 ) return 1 ;if ( cnt ) return 2 ;return 0 ;
}void push_down ( int o ) {int x = T[o].mins , y = T[o].maxs[0] ;if ( T[o].l ) T[T[o].l].down ( x , y ) ;if ( T[o].r ) T[T[o].r].down ( x , y ) ;T[o].mins = -1 ;
}void upd ( int o , int x , int y , int t ) {int d = check ( T[o].Min[0] , T[o].Max[0] , T[o].Min[1] , T[o].Max[1] , x , y ) ;if ( !d ) {T[o].down ( t , t ) ;return ;}if ( d == 1 ) return ;if ( T[o][0] > x || T[o][1] < y ) {T[o].maxv[1] = max ( T[o].maxv[1] , t - T[o].maxs[1] - 1 ) ;T[o].maxs[1] = t ;}push_down ( o ) ;if ( T[o].l ) upd ( T[o].l , x , y , t ) ;if ( T[o].r ) upd ( T[o].r , x , y , t ) ;
}void down ( int o , int ans ) {push_down ( o ) ;T[o].maxv[1] = max ( T[o].maxv[1] , n - T[o].maxs[1] ) ;T[o].maxv[0] = max ( T[o].maxv[0] , ans ) ;T[o].maxv[1] = max ( ans , T[o].maxv[1] ) ;T[o].maxv[1] = max ( T[o].maxv[0] , T[o].maxv[1] ) ;if ( T[o].l ) down ( T[o].l , T[o].maxv[0] ) ;if ( T[o].r ) down ( T[o].r , T[o].maxv[0] ) ;
}void scanf ( int& x ) {while ( *cur < '0' ) ++ cur ;x = *cur - '0' , ++ cur ;while ( *cur >= '0' ) ( x *= 10 ) += *cur - '0' , ++ cur ;
}void solve () {for ( int i = 1 ; i <= n ; ++ i ) {scanf ( Y[i] ) ;scanf ( X[i] ) ;}for ( int i = 1 ; i <= m ; ++ i ) {scanf ( T[i].p[0] ) ;scanf ( T[i].p[1] ) ;T[i].f = i ;}root = build ( 1 , m , 0 , 0 ) ;for ( int i = 1 ; i <= n ; ++ i ) {upd ( root , X[i] , Y[i] , i ) ;}down ( root , 0 ) ;for ( int i = 1 ; i <= m ; ++ i ) {printf ( "%d\n" , T[idx[i]].maxv[1] ) ;}
}int main () {fread ( buf , 1 , MAXM , stdin ) ;scanf ( n ) ;scanf ( m ) ;solve () ;return 0 ;
}