ACdream 1157 （cdq分治）

题目链接

Segments

Time Limit: 4000/2000MS (Java/Others)Memory Limit: 20000/10000KB (Java/Others)

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操作，输出一行，答案

Sample Input
6

D 1 100

D 3 8

D 4 10

Q 3 8

C 1

Q 3 8
Sample Output
2

1
Hint

注意，删除第i条增加的线段，不是说第i行，而是说第i次增加。

比如

D 1 10

Q 1 10

D 2 3

D 3 4

Q 5 6

D 5 6

C 2是删除D 2 3

C 4是删除D 5 6

第一次听说cdq分治，cdq是陈丹琦orz。。

在我们平常使用的分治中，每一个子问题只解决它本身（可以说是封闭的）。

而在cdq分治中，对于划分出来的两个子问题，前一个子问题用来解决后一个子问题而不是它本身。

具体算法流程如下：

1.将整个操作序列分为两个长度相等的部分（分）

2.递归处理前一部分的子问题（治1）

3.计算前一部分的子问题中的修改操作对后一部分子问题的影响（治2）

4.递归处理后一部分子问题（治3）

另外，能使用常量引用的地方尽量使用，可以提高效率。

Accepted Code:

 /*************************************************************************

     > File Name: 1157.cpp

     > Author: Stomach_ache

     > Mail: sudaweitong@gmail.com

     > Created Time: 2014年08月10日 星期日 08时24分10秒

     > Propose:

  ************************************************************************/

 #include <cmath>

 #include <string>

 #include <cstdio>

 #include <vector>

 #include <fstream>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 int c[maxn<<], l[maxn], r[maxn], ans[maxn];

 struct node {

       int t, id, l, r;

     node() {}

     node(int a, int b, int c, int d) {

           t = a; id = b; l = c; r = d;

     }

 }a[maxn];

 vector<int> xs;

 int w;

 bool cmp1(const node &a, const node &b) {

       return a.id < b.id;

 }

 bool cmp2(const node &a, const node &b) {

       if (a.l != b.l) return a.l < b.l;

     return a.r > b.r;

 }

 int lowbit(int x) {

       return x & -x;

 }

 void add(int x, int v) {

       x = *maxn - x;

       while (x < maxn*) {

           c[x] += v;

         x += lowbit(x);

     }

 }

 int sum(int x) {

       int res = ;

     x = *maxn - x;

     while (x > ) {

           res += c[x];

         x -= lowbit(x);

     }

     return res;

 }

 void solve(int l, int r) {

       if (l >= r) return ;

     int mid = (l + r) >> ;

     solve(l, mid);

     sort(a+l, a+r+, cmp2);

     for (int i = l; i <= r; i++) {

           if (a[i].id <= mid) {

               if (a[i].t == ) add(a[i].r, );

             else if (a[i].t == -) add(a[i].r, -);

         } else {

               if (a[i].t == ) ans[a[i].id] += sum(a[i].r);

         }

     }

     for (int i = l; i <= r; i++) if (a[i].id <= mid) {

           if (a[i].t == ) add(a[i].r, -);

         if (a[i].t == -) add(a[i].r, );

     }

     sort(a+l, a+r+, cmp1);

     solve(mid+, r);

 }

 int main(void) {

       int n;

       while (~scanf("%d", &n)) {

           int cnt = ;

         xs.clear();

           for (int i = ; i <= n; i++) {

               char s[];

               scanf("%s", s);

             if (s[] == 'D') {

                   int x, y;

                 scanf("%d %d", &x, &y);

                 xs.push_back(x);

                 xs.push_back(y);

                 l[cnt] = x;

                 r[cnt++] = y;

                 a[i] = node(, i, x, y);

             } else if (s[] == 'Q') {

                   int x, y;

                 scanf("%d %d", &x, &y);

                 xs.push_back(x);

                 xs.push_back(y);

                 a[i] = node(, i, x, y);

             } else {

                   int id;

                 scanf("%d", &id);

                 a[i] = node(-, i, l[id], r[id]);

             }

         }

         sort(xs.begin(), xs.end());

         xs.erase(unique(xs.begin(), xs.end()), xs.end());

         w = xs.size();

         for (int i = ; i <= n; i++) {

               a[i].l = lower_bound(xs.begin(), xs.end(), a[i].l)-xs.begin()+;

               a[i].r = lower_bound(xs.begin(), xs.end(), a[i].r)-xs.begin()+;

             //printf("%d %d\n", a[i].l, a[i].r);

         }

         //memset(c, 0, sizeof(c));

         memset(ans, , sizeof(ans));

         solve(, n);

         for (int i = ; i <= n; i++) if (!a[i].t) printf("%d\n", ans[i]);

     }

     return ;

 }

巴特西

ACdream 1157 （cdq分治）

Segments

Problem Description

Input

Output

Sample Input

Sample Output

Hint

最新文章

热门文章