倒序处理...没想到这个就一直写不出来啊...
用线段树维护区间信息。如果这个海报的区间被覆盖了，那么显然就是被后面的海报覆盖过了，那么最后肯定就看不到这张海报了，这张海报就不用统计了
更新区间信息的时候&一下左右儿子就可以了
#include <bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f #define il inline namespace io { #define in(a) a=read() #define out(a) write(a) #define outn(a) out(a),putchar(‘\n‘) #define I_int int inline I_int read() { I_int x = 0 , f = 1 ; char c = getchar() ; while( c < ‘0‘ || c > ‘9‘ ) { if( c == ‘-‘ ) f = -1 ; c = getchar() ; } while( c >= ‘0‘ && c <= ‘9‘ ) { x = x * 10 + c - ‘0‘ ; c = getchar() ; } return x * f ; } char F[ 200 ] ; inline void write( I_int x ) { I_int tmp = x > 0 ? x : -x ; if( x < 0 ) putchar( ‘-‘ ) ; int cnt = 0 ; while( tmp > 0 ) { F[ cnt ++ ] = tmp % 10 + ‘0‘ ; tmp /= 10 ; } while( cnt > 0 ) putchar( F[ -- cnt ] ) ; } #undef I_int } using namespace io ; using namespace std ; #define N 100010 const int M = 1e7 + 10 ; #define lc (rt<<1) #define rc (rt<<1|1) int n = read() , m = read() ; int a[ N ] , b[ N ] ; int cover[ M << 2 ] ; int bc = 0 ; void upd( int L , int R , int l , int r , int rt ) { if( cover[ rt ] ) return ; if( L <= l && r <= R && !cover[ rt ] ) { cover[ rt ] = 1 ; bc = 0 ; return ; } int mid = ( l + r ) >> 1 ; if( L <= mid ) upd( L , R , l , mid , lc ) ; if( R > mid ) upd( L , R , mid + 1 , r , rc ) ; cover[ rt ] = cover[ lc ] & cover[ rc ] ; } int main() { int ans = 0 ; for( int i = 1 ; i <= m ; i ++ ) a[ i ] = read() , b[ i ] = read() ; for( int i = m ; i ; i -- ) { bc = 1 ; upd( a[ i ] , b[ i ] , 1 , n , 1 ) ; if( !bc ) ans ++ ; } outn( ans ) ; }
原文：https://www.cnblogs.com/henry-1202/p/BZOJ5168.html