HDU 2871 Memory Control 线段树（区间合并）+二分查找+vector的常用方法

这道题给人的感觉就是恶心人。

刚开始完全不懂怎么找含有x的区间，后来看别人都说用vector，然后用之，发现很好用啊，支持插入和擦除操作，我原来竟然不知道还有这些功能.

vector中的insert函数

iterator insert( iterator loc, const TYPE &val );
void insert( iterator loc, size_type num, const TYPE &val );
void insert( iterator loc, input_iterator start, input_iterator end );


insert() 函数有以下三种用法:

在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器,
在指定位置loc前插入num个值为val的元素
在指定位置loc前插入区间[start, end)的所有元素 .

这道题用到了第一个函数

然后还有erase函数

vector::erase()：从指定容器删除指定位置的元素或某段范围内的元素
vector::erase()方法有两种重载形式
如下：
iterator erase( iterator _Where);
1.iterator erase( iterator _First, iterator _Last);
如果是删除指定位置的元素时：
返回值是一个迭代器，指向删除元素下一个元素;如果是删除某范围内的元素时：返回值也表示一个迭代器，指向最后一个删除元素的下一个元素;

转载之： 来自http://blog.sina.com.cn/s/blog_6377b8e60100ino6.html

MSDN上的例子
// vector_erase.cpp
// compile with: /EHsc
#include <vector>
#include <iostream>
int main( )
{
using namespace std;
vector <int> v1;
vector <int>::iterator Iter;
v1.push_back( 10 );
v1.push_back( 20 );
v1.push_back( 30 );
v1.push_back( 40 );
v1.push_back( 50 );
cout << "v1 =" ;
for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ )
cout << " " << *Iter;
cout << endl;
v1.erase( v1.begin( ) );
cout << "v1 =";
for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ )
cout << " " << *Iter;
cout << endl;
v1.erase( v1.begin( ) + 1, v1.begin( ) + 3 );
cout << "v1 =";
for ( Iter = v1.begin( ) ; Iter != v1.end( ) ; Iter++ )
cout << " " << *Iter;
cout << endl;
}
Output
v1 = 10 20 30 40 50
v1 = 20 30 40 50
v1 = 20 50
大家可以知道，需删除元素10只要指定该元素对应的迭代器传给erase就OK了；
那现在如果该容器中有两个元素10要怎么删除呢？
接着我做下修改，向容器中添加一新的元素10
v1.push_back( 10 );
大多数初学者在不熟知erase的原理的时候，也会像我一样这样处理，
一一遍历容器找到元素值为10，然后一一删除
for(Iter = v1.begin(); Iter != v1.end(); Iter++)
{
if(*Iter == 10)
{
v1.erase(Iter);
}
}
当试着重新build程序后运行，会出现包含有如下信息的错误
_Myptr < ((_Myvec *)(this->_Mycont))->_Mylast
其他出现这种原因是没搞懂erase的原理，当调用erase()后Iter迭代器就失效了，变成了一野指针。
所以要处理这种问题，关键是要解决调用erase()方法后，Iter迭代器变成野指针的问题，
这个时候呢给他赋一个新的迭代器给他。
for(Iter = v1.begin(); Iter != v1.end(); Iter++)
{
if(*Iter == 10)
{
v1.erase(Iter);
Iter = v1.begin(); //当erase后，旧的容器会被重新整理成一个新的容器
}
}
重新Iter迭代器指定下一个元素.
上面那种方法是给Iter重新赋于新v1的begin迭代器。
还有一种方法是直接赋删除元素的下一个迭代器给Iter
实现方法的代码如下：
for(Iter = v1.begin(); Iter != v1.end(); Iter++)
{
if(*Iter == 10)
{
Iter = v1.erase(Iter);//Iter为删除元素的下一个元素的迭代器
//即第一次这段语句后Iter 会是20，大家可以通过debug调试出来查看下数值
}

if(Iter == v1.end()) //要控制迭代器不能超过整个容器
{
break;
}
}

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 50005
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct node
{
    int left, right, mid;
    int lmx, rmx, mx, cover;
}tree[4 * MAXN];
void up(int C)
{
    tree[C].lmx = tree[L(C)].lmx;
    tree[C].rmx = tree[R(C)].rmx;
    if(tree[L(C)].lmx == tree[L(C)].right - tree[L(C)].left + 1) tree[C].lmx += tree[R(C)].lmx;
    if(tree[R(C)].rmx == tree[R(C)].right - tree[R(C)].left + 1) tree[C].rmx += tree[L(C)].rmx;
    tree[C].mx = max(tree[L(C)].rmx + tree[R(C)].lmx, max(tree[L(C)].mx, tree[R(C)].mx));
}
void down(int C)
{
    if(tree[C].cover != -1)
    {
        tree[L(C)].cover = tree[R(C)].cover = tree[C].cover;
        tree[L(C)].lmx = tree[L(C)].rmx = tree[L(C)].mx = tree[C].cover ? 0 : tree[L(C)].right - tree[L(C)].left + 1;
        tree[R(C)].lmx = tree[R(C)].rmx = tree[R(C)].mx = tree[C].cover ? 0 : tree[R(C)].right - tree[R(C)].left + 1;
        tree[C].cover = -1;
    }
}
void make_tree(int s, int e, int C)
{
    tree[C].left = s;
    tree[C].right = e;
    tree[C].mid = (s + e) >> 1;
    tree[C].cover = 0;
    tree[C].lmx = tree[C].rmx = tree[C].mx = e - s + 1;
    if(s == e) return;
    make_tree(s, tree[C].mid, L(C));
    make_tree(tree[C].mid + 1, e, R(C));
}
void update(int s, int e, int v, int C)
{
    if(tree[C].left >= s && tree[C].right <= e)
    {
        tree[C].cover = v;
        tree[C].lmx = tree[C].rmx = tree[C].mx = v ? 0 : tree[C].right - tree[C].left + 1;
        return;
    }
    down(C);
    if(tree[C].mid >= s) update(s, e, v, L(C));
    if(tree[C].mid < e) update(s, e, v, R(C));
    up(C);
}
int query(int p, int C)
{
    if(tree[C].left == tree[C].right) return tree[C].left;
    down(C);
    if(tree[L(C)].mx >= p) return query(p, L(C));
    else if(tree[L(C)].rmx + tree[R(C)].lmx >= p) return tree[C].mid - tree[L(C)].rmx + 1;
    else return query(p, R(C));
}
struct Point
{
    int bg, ed;
    Point(){}
    Point(int a, int b) {bg = a; ed = b;}
};
vector<Point>g;
int find(int x) //二分的目的是找到左界比x大的区间
{
    int low = 0, high = g.size() - 1;
    int mid;
    while(low <= high)
    {
        mid = (low + high) >> 1;
        if(g[mid].bg <= x) low = mid + 1;
        else high = mid - 1;
    }
    return low;
}
int main()
{
    int n, m, x;
    char s[15];
    while(scanf("%d%d", &n, &m) != EOF)
    {
        make_tree(1, n, 1);
        g.clear();
        while(m--)
        {
            scanf("%s", s);
            if(s[0] == 'R')
            {
                tree[1].cover = 0;
                tree[1].lmx = tree[1].rmx = tree[1].mx = n;
                g.clear();
                printf("Reset Now\n");
            }
            else if(s[0] == 'N')
            {
                scanf("%d", &x);
                if(tree[1].mx < x)
                    printf("Reject New\n");
                else
                {
                    int t = query(x, 1);
                    printf("New at %d\n", t);
                    update(t, t + x - 1, 1, 1);
                    Point tmp(t, t + x - 1);
                    if(g.size() == 0) g.push_back(tmp);
                    else
                    {
                        int rt = find(t);
                        g.insert(g.begin() + rt, tmp);//插入操作
                    }
                }
            }
            else if(s[0] == 'G')
            {
                scanf("%d", &x);
                if(g.size() < x) printf("Reject Get\n");
                else printf("Get at %d\n", g[x - 1].bg);
            }
            else if(s[0] == 'F')
            {
                scanf("%d", &x);
                int rt = find(x) - 1;
                if(rt == -1 || g[rt].ed < x)
                printf("Reject Free\n");
                else
                {
                    printf("Free from %d to %d\n", g[rt].bg, g[rt].ed);
                    update(g[rt].bg, g[rt].ed, 0, 1);
                    g.erase(g.begin() + rt);//删除操作
                }
            }
        }
        puts("");
    }
    return 0;
}