题意：令a[l..r]都+1，求a[1..n]的最大值
裸的成段更新+区间最值，但是本题坐标范围很大(10^9)，所以需要离散化
顺便离散化模板get
离散化的基本思路：
设一共有m个数，范围1--n （n>>m）
先用数组X[1..m]存下这些数，然后对X从小到大排序
每次读入一个数p时，在X中二分查找p，p在数组X中的位置对应的数组下标就是p离散化之后的值
这样就成功把范围1--n的数压缩到了1--m以内。
#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 = ; struct node
{
int l, r;
}; node D[MAXN];
int limit, Q;
int maxi[ MAXN << ];
int lazy[ MAXN << ];
int N;
int X[MAXN]; void build( int l, int r, int rt )
{
maxi[rt] = lazy[rt] = ;
if ( l == r ) return;
int m = ( l + r ) >> ;
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] = ;
}
return;
} void update( int L, int R, int l, int r, int rt )
{
if ( L <= l && r <= R )
{
lazy[rt] += ;
maxi[rt] += ;
return;
}
PushDown( rt );
int m = ( l + r ) >> ;
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 ) >> ; int res = -;
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 Bin(int key,int n,int X[]) {
int l = , r = n - ;
while (l <= r) {
int m = (l + r) >> ;
if (X[m] == key) return m;
if (X[m] < key) l = m + ;
else r = m - ;
}
return -;
} int main()
{
int T;
scanf( "%d", &T );
while ( T-- )
{
scanf( "%d", &Q );
int nnd=;
N = ;
for ( int i = ; i < Q; ++i )
{
int u, v;
scanf( "%d%d", &u, &v );
if (v>N) N=v;
D[i].l = u, D[i].r = v;
X[nnd++]=u;
X[nnd++]=v;
}
//build( 1, N, 1 );
//for (int i=0;i<Q;i++)
// update( D[i].l, D[i].r, 1, N, 1 ); sort(X , X + nnd);
int m = ;
for (int i = ; i < nnd; i ++) {
if (X[i] != X[i-]) X[m ++] = X[i];
}
for (int i = m - ; i > ; i --) {
if (X[i] != X[i-] + ) X[m ++] = X[i-] + ;
}
sort(X , X + m);
build(,m-,);
for (int i = ; i < Q ; i ++) {
int l = Bin(D[i].l, m, X);
int r = Bin(D[i].r, m, X);
update(l, r , , m - , );
} //int ans = query( 1, N , 1, N, 1 );
int ans=query(,m-,,m-,);
printf( "%d\n", ans);
//update( D[i].l, D[i].r, 1, N, 1 );
}
return ;
}