本体思路其实很简单,离散化后线段树段修改,最后统计一遍即可。
不过此题数据甚是恶心,HASH改了好几遍才AC,想想以后离散化还是不用HASH比较好= =。。
不过也借由此题促使咱回去看《统计的力量》熟悉重口味版线段树,收获良多>u<。。
# include <cstdio> # include <algorithm> # include <cstring> using namespace std; const int MOD = 50007; int t, n; struct POST { int l, r, id; bool show; POST(){ show = false; } }p[10003]; int list[40003], tot, f[MOD+2], trans[MOD+2]; int hash(int x) { int pos; pos = (3*x + x%107 + x>>2) % MOD; while ( f[pos] && f[pos] != x ) pos = (pos + 173)%MOD; if ( pos < 0 ) pos += MOD; return pos; } int M, tree[131077], tf[131007], time; const int tsize = sizeof(tree), fsize = sizeof(f); void modify(int s, int t, int c) { ++time; for ( s+=M-1, t+=M+1; s^t^1; s>>=1, t>>=1 ) { if (~s&1 ) tree[s^1] = c, tf[s^1] = time; if ( t&1 ) tree[t^1] = c, tf[t^1] = time; } } void ask(int x, int mt, int c) { if ( x <= M + tot && tree[x] && tf[x] > mt ) c = tree[x], mt = tf[x]; if ( x >= M ) { if (c) p1.show = true; return ; } ask(x<<1, mt, c); ask((x<<1)+1, mt, c); } void work() { int i, a, b; tot = time = 0; memset(f, 0, sizeof(f)); scanf("%d", &n); if ( n == 0 ) { printf("0\n"); return ; } for ( i = 1; i <= n; ++i ) scanf("%d%d", &p[i].l, &p[i].r); for ( i = 1; i <= n; ++i ) { p[i].id = i; p[i].show = false; a = hash(p[i].l); b = hash(p[i].r); if ( !f[a] ) f[a] = p[i].l, list[++tot] = p[i].l; if ( !f[b] ) f[b] = p[i].r, list[++tot] = p[i].r; } sort(list+1, list+1+tot); a = tot; for (i = 1; i < a; ++i ) if ( list[i] + 1 < list[i+1] ) list[++tot] = list[i] + 1; sort(list+1, list+1+tot); for ( i = 1; i <= tot; ++i ) trans[hash(list[i])] = i; for ( i = 1; i <= n; ++i ) { p[i].l = trans[hash(p[i].l)]; p[i].r = trans[hash(p[i].r)]; } for ( M = 1; M < tot+2; M<<=1 ); memset(tree, 0, tsize); for ( i = 1; i <= n; ++i ) modify(p[i].l, p[i].r, p[i].id); ask(1, 0, 0); for ( a = 0, i = 1; i<= n; ++i ) if ( p[i].show ) ++a; printf("%d\n", a); } int main() { scanf("%d", &t); while ( t-- ) work(); return 0; }