首页 > 代码库 > ACdream 1157 Segments（CDQ分治）

ACdream 1157 Segments（CDQ分治）

2024-07-16 16:52:48   220人阅读

题目链接：http://acdream.info/problem?pid=1157

Problem Description

由3钟类型操作：
1）D L R(1 <= L <= R <= 1000000000) 增加一条线段[L,R]
2）C i (1-base) 删除第i条增加的线段，保证每条插入线段最多插入一次，且这次删除操作一定合法
3) Q L R(1 <= L <= R <= 1000000000) 查询目前存在的线段中有多少条线段完全包含[L,R]这个线段，线段X被线段Y完全包含即LY <= LX

<= RX <= RY)
给出N，接下来N行，每行是3种类型之一

Input

多组数据，每组数据N

接下来N行，每行是三种操作之一(1 <= N  <= 10^5)

Output

对于每个Q操作，输出一行，答案
 
题目大意：略。
思路：传说这个就叫做CDQ分治，我也不确定是不是。对每一段[l..r]，分治处理[l, mid]和[mid + 1..r]。对于[l..r]，处理[l..mid]中的线段对[mid + 1..r]的影响，用树状数组处理一下就可以了。
 
代码（1608MS）：
  1 #include <iostream>  2 #include <algorithm>  3 #include <cstring>  4 #include <cstdio>  5 using namespace std;  6   7 const int MAXN = 200010;  8   9 int hashmap[MAXN], hcnt; 10 int tree[MAXN]; 11  12 int hash(int x) { 13     return lower_bound(hashmap, hashmap + hcnt, x) - hashmap + 1; 14 } 15  16 inline int lowbit(int x) { 17     return x & -x; 18 } 19  20 void modify(int k, int val) { 21     while(k <= hcnt) { 22         tree[k] += val; 23         k += lowbit(k); 24     } 25 } 26  27 int get_sum(int k) { 28     int res = 0; 29     while(k) { 30         res += tree[k]; 31         k -= lowbit(k); 32     } 33     return res; 34 } 35  36 struct Node { 37     int v, l, r, id; 38     Node() {} 39     Node(int v, int l, int r, int id): v(v), l(l), r(r), id(id) {} 40     bool operator < (const Node &rhs) const { 41         if(r != rhs.r) return r > rhs.r; 42         if(l != rhs.l) return l < rhs.l; 43         return (v == 0) < (rhs.v == 0); 44     } 45 }; 46  47 bool cmp_id(const Node &a, const Node &b) { 48     return a.id < b.id; 49 } 50  51 Node p[MAXN]; 52 int ans[MAXN], tl[MAXN], tr[MAXN]; 53 int n; 54  55 void solve(int l, int r) { 56     if(l == r) return ; 57     int mid = (l + r) >> 1; 58     solve(l, mid); 59     solve(mid + 1, r); 60     sort(p + l, p + r + 1); 61     for(int i = l; i <= r; ++i) { 62         if(p[i].id <= mid) { 63             if(p[i].v) modify(p[i].l, p[i].v); 64         } else { 65             if(!p[i].v) ans[p[i].id] += get_sum(p[i].l); 66         } 67     } 68     for(int i = l; i <= r; ++i) { 69         if(p[i].id <= mid && p[i].v) modify(p[i].l, -p[i].v); 70     } 71     sort(p + l, p + r + 1, cmp_id); 72 } 73  74 int main() { 75     while(scanf("%d", &n) != EOF) { 76         int tcnt = 0; hcnt = 0; 77         char c; 78         for(int i = 1, t, u; i <= n; ++i) { 79             scanf(" %c", &c); 80             if(c == ‘D‘) { 81                 scanf("%d%d", &t, &u); 82                 p[i] = Node(1, t, u, i); 83                 hashmap[hcnt++] = t; hashmap[hcnt++] = u; 84                 tl[++tcnt] = t; tr[tcnt] = u; 85             } 86             if(c == ‘C‘) { 87                 scanf("%d", &t); 88                 p[i] = Node(-1, tl[t], tr[t], i); 89             } 90             if(c == ‘Q‘) { 91                 scanf("%d%d", &t, &u); 92                 p[i] = Node(0, t, u, i); 93                 hashmap[hcnt++] = t; hashmap[hcnt++] = u; 94             } 95         } 96         sort(hashmap, hashmap + hcnt); 97         hcnt = unique(hashmap, hashmap + hcnt) - hashmap; 98         for(int i = 1; i <= n; ++i) { 99             p[i].l = hash(p[i].l); p[i].r = hash(p[i].r);100         }101         memset(ans + 1, 0, n * sizeof(int));102         solve(1, n);103         for(int i = 1; i <= n; ++i)104             if(p[i].v == 0) printf("%d\n", ans[i]);105     }106 }
View Code

 


联系
我们