首页 > 代码库 > bnu36905 Nested Segments 离散化+线段树
bnu36905 Nested Segments 离散化+线段树
bnu36905 Nested Segments
离散化+线段树区间更新
也可以用离散化+set(或双向链表)
#include <cstdio> #include <ctime> #include <cstdlib> #include <cstring> #include <queue> #include <string> #include <set> #include <stack> #include <map> #include <cmath> #include <vector> #include <iostream> #include <algorithm> #include <bitset> #include <fstream> using namespace std; //LOOP #define FF(i, a, b) for(int i = (a); i < (b); ++i) #define FE(i, a, b) for(int i = (a); i <= (b); ++i) #define FED(i, b, a) for(int i = (b); i>= (a); --i) #define REP(i, N) for(int i = 0; i < (N); ++i) #define CLR(A,value) memset(A,value,sizeof(A)) #define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++) //OTHER #define SZ(V) (int)V.size() #define PB push_back #define MP make_pair #define all(x) (x).begin(),(x).end() //INPUT #define RI(n) scanf("%d", &n) #define RII(n, m) scanf("%d%d", &n, &m) #define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k) #define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p) #define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q) #define RS(s) scanf("%s", s) #define sqr(x) (x) * (x) typedef long long LL; typedef unsigned long long ULL; typedef vector <int> VI; const int INF = 0x3f3f3f3f; const double EPS = 1e-9; const int MOD = 1000000007; const double PI = acos(-1.0); const int maxn = 410000; #define ll rt << 1 #define rr rt << 1 | 1 struct Node{ int l, r, m; int val; }st[maxn << 2]; void build(int l, int r, int rt) { st[rt].l = l; st[rt].r = r; int m = (l + r) >> 1; st[rt].m = m; st[rt].val = -1; if (l == r) return ; build(l, m, ll); build(m + 1, r, rr); } inline void segVal(int rt, int x) { st[rt].val = x; } inline void down(int rt) { if (st[rt].val != -1) { segVal(ll, st[rt].val); segVal(rr, st[rt].val); st[rt].val = -1; } } void update(int L, int R, int x, int rt) { if (L <= st[rt].l && st[rt].r <= R) { segVal(rt, x); return ; } down(rt); if (L <= st[rt].m) update(L, R, x, ll); if (R > st[rt].m) update(L, R, x, rr); } int query(int p, int rt) { if (st[rt].l == st[rt].r) return st[rt].val; down(rt); if (p <= st[rt].m) return query(p, ll); else return query(p, rr); } int n; struct Seg{ int l, r; int id; bool operator<(const Seg &rhs) const{ return r - l > rhs.r - rhs.l; } }seg[100010]; int a[maxn]; int asz; int main() { while (~RI(n)) { asz = 0; REP(i, n) { scanf("%d%d", &seg[i].l, &seg[i].r); a[asz++] = seg[i].l; a[asz++] = seg[i].r; seg[i].id = i + 1; } sort(seg, seg + n); ///离散化start a[asz++] = 0; a[asz++] = 1e9 + 1; sort(a, a + asz); asz = unique(a, a + asz) - a; int atot = asz; for (int i = 1; i < asz; i++) { if (a[i] - a[i - 1] > 1) a[atot++] = a[i] - 1;/// } asz = atot; sort(a, a + asz); ///离散化end build(1, asz, 1); for (int i = 0; i < n; i++) { int L = lower_bound(a, a + asz, seg[i].l) - a; int R = lower_bound(a, a + asz, seg[i].r) - a; update(L + 1, R + 1, seg[i].id, 1); } int q; RI(q); while (q--) { int x; RI(x); int xx = lower_bound(a, a + asz, x) - a; printf("%d\n", query(xx + 1, 1)); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。