首页 > 代码库 > Poj2528Mayor's posters线段树
Poj2528Mayor's posters线段树
先贴,明天再补。
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1const int maxn = 44444;int color[maxn << 2];int vis[maxn];int q[maxn];int q1[maxn];int l[maxn];int r[maxn];int Hash[maxn];void down(int rt){ if (color[rt]){ color[rt << 1] = color[rt << 1 | 1] = color[rt]; color[rt] = 0; }}void build(int l, int r, int rt){ color[rt] = 0; if (l == r) return; int mid = (l + r) >> 1; build(lson); build(rson);}void update(int L, int R, int add, int l, int r, int rt){ if (L <= l&&r <= R){ color[rt] = add; return; } down(rt); int mid = (l + r) >> 1; if (L <= mid) update(L, R, add, lson); if (R>mid) update(L, R, add, rson);}void ask(int l, int r, int rt){ if (color[rt]){ Hash[color[rt]] = 1; return; } int mid = (l + r) >> 1; ask(lson); ask(rson);}int erfen(int key, int a[], int len){ int l = 0; int r = len - 1; while (l <= r){ int mid = (l + r) >> 1; if (a[mid] == key) return mid + 1; if (a[mid]<key) l = mid + 1; if (a[mid]>key) r = mid - 1; }}int cmp(const int &a, const int &b){ return a<b;}int main(){ int Icase, n; int ans, ans1; scanf("%d", &Icase); while (Icase--){ ans = 0; ans1 = 0; memset(Hash, 0, sizeof(Hash)); scanf("%d", &n); for (int i = 0; i<n; i++){ scanf("%d%d", &l[i], &r[i]); q[ans++] = l[i]; q[ans++] = r[i]; } sort(q, q + ans, cmp); memset(vis, 0, sizeof(vis)); for (int i = 0; i<ans - 1; i++){ if (q[i] == q[i + 1]) vis[i + 1] = 1; } int ans1 = 0; for (int i = 0; i<ans; i++) if (!vis[i]) q1[ans1++] = q[i]; for (int i = 0; i<n; i++){ l[i] = erfen(l[i], q1, ans1); r[i] = erfen(r[i], q1, ans1); } build(1, ans1, 1); for (int i = 0; i<n; i++){ update(l[i], r[i], i + 1, 1, ans1, 1); } ask(1, ans1, 1); int gg = 0; for (int i = 1; i <= n; i++) if (Hash[i]) gg++; cout << gg << endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。