题目地址 题意：给你n个海报，海报的宽度是一样的，告诉你长度为l-r，求最后你能看到多少张广告 思路：蛮基础的延迟更新，但是要注意一点就是离散化的时候要加入分割点，因为如果直接离散化的话，就会出现有的区间就会忽略了，就这个要注意的地方
#include <iostream> #include <cstring> #include <string> #include <queue> #include <vector> #include <map> #include <set> #include <stack> #include <cmath> #include <cstdio> #include <algorithm> #include <iomanip> #define N 10010 #define LL __int64 #define inf 0x3f3f3f3f #define lson l,mid,ans<<1 #define rson mid+1,r,ans<<1|1 #define getMid (l+r)>>1 #define movel ans<<1 #define mover ans<<1|1 using namespace std; struct node { int x, y; }point[N]; int cnt; int sum[N << 4]; vector<int> v; int flag[N << 1]; int x, y; void init() { cnt = 0; v.clear(); memset(flag, 0, sizeof(flag)); } void build(int l, int r, int ans) { memset(sum, 0, sizeof(sum)); } void print(int l, int r, int ans) { if (l == r) { cout << sum[ans] << " "; return; } int mid = (l + r) >> 1; print(lson); print(rson); } void updata(int l, int r, int ans, int num) { if (l >= x&&r <= y) { sum[ans] = num; return; } int mid = (l + r) >> 1; if (sum[ans]>0) { sum[ans << 1] = sum[ans << 1 | 1] = sum[ans]; sum[ans] = 0; } if (mid<x) { updata(rson, num); } else if (mid >= y) { updata(lson, num); } else { updata(lson, num); updata(rson, num); } } void solve(int l, int r, int ans) { if (sum[ans]) { if (!flag[sum[ans]]) { cnt++; flag[sum[ans]] = 1; } return; } if (l == r) { return; } int mid = (l + r) >> 1; solve(lson); solve(rson); } int main() { int T, n; scanf("%d", &T); while (T--) { scanf("%d", &n); init(); for (int i = 1; i <= n; i++) { scanf("%d %d", &point[i].x, &point[i].y); v.push_back(point[i].x); v.push_back(point[i].y); } sort(v.begin(), v.end()); int len = v.size(); for (int i = 1; i < len; i++) { if (v[i] - v[i - 1] > 1) { v.push_back(v[i] + 1); } } sort(v.begin(), v.end()); len = unique(v.begin(), v.end()) - v.begin(); if (len == 0) { printf("0\n"); continue; } build(1, len, 1); for (int i = 1; i <= n; i++) { x = lower_bound(v.begin(), v.begin() + len, point[i].x) - v.begin() + 1; y = lower_bound(v.begin(), v.begin() + len, point[i].y) - v.begin() + 1; updata(1, len, 1, i); } solve(1, len, 1); printf("%d\n", cnt); } return 0; }