離散化—区間被覆——線分樹実践POJ 258


セグメントツリーの最適化
区間カバー問題-伝統的なcover配列に加えて--このテーマの特殊性--最終的にポスターが見える数を計算します--だからノードの値はここで私の意味は何枚目のポスターがこのノードをカバーしているのか、準備を見てください

#include 
#include 
#include 
using namespace std;
#define lson i << 1,left,mid
#define rson i << 1 | 1,mid + 1,right
const int Max = 20010;
int ans;
int vis[Max];
struct Line{
    int point;
    int num;
}line[Max];
bool cmp(Line a,Line b)
{
    return a.point < b.point;
}
int poster[Max / 2][2];
int t[Max << 2];

テーマに基づいて20000+を開く
vis配列,line構造体,cmp関数,posterはいずれもポスターx軸の左右端点を離散化処理し記憶するためである
tツリーグループはツリーです

 for(int i = 1;i <= n;i++)
            {
                scanf("%d%d",&poster[i][0],&poster[i][1]);
                line[i * 2 - 1].point = poster[i][0];
                line[i * 2 - 1].num = -i;// 
                line[i * 2].point = poster[i][1];
                line[i * 2].num = i;// 
            }
            sort(line + 1,line + 2 * n + 1,cmp);
            int flag = -0x3f3f;
            int N = 0;
            for(int i = 1;i <= 2 * n;i++)
            {
                if(line[i].point != flag)
                {
                    N++;
                    flag = line[i].point;

                }
                if(line[i].num < 0)poster[-line[i].num][0] = N;
                else poster[line[i].num][1] = N;
            }

離散化は各ノードに値を割り当てるため、2*n
構造体のpointの記憶は元のx座標であり、numはマッピング|i|が何枚目のポスターを表し、pointが左端点であれば、タグ-iの右端点を+iとする.
最後にカスタム順序付け後、マッピングを定義します.Nは元のエンドポイントごとにマッピングされ、重複しないエンドポイントごとにN++
最後に得られたNは線分木に必要なメンテナンスの幅である
次に通常のツリーを作成

void build(int i,int left,int right)
{
    t[i] = 0;
    if(left == right)return;
    int mid = (left + right) >> 1;
    build(lson);
    build(rson);
}

そして最初から最後までポスター

for(int i = 1;i <= n;i++)
            {
                //cout<

updateはノードの値を更新します.lazyタグの考え方と同じように、ポスターのカバーの長さを葉ノードまで維持することはありません.最小包容区間を見つけると停止します.このポスターを更新する過程で、前のポスターのlazyタグがついでに伝わります.

void pd(int i)
{
    if(t[i])
    {
        t[i << 1] = t[i];
        t[i << 1 | 1] = t[i];
        t[i] = 0;
    }
}
void update(int i,int left,int right,int le,int re,int v)
{
    if(le <= left && right <= re )
    {
        t[i] = v;
        return;
    }
    pd(i);
    int mid = (left + right) >> 1;
    if(le <= mid) update(lson,le,re,v);
    if(re > mid)update(rson,le,re,v);
}

vis配列を定義してクエリーを開始すると、いくつかの値の異なるノードが見つかることを意味します.

void query(int i,int left,int right)
{

    if(t[i] != 0)
    {

        if(!vis[t[i]])
        {

            vis[t[i]] = 1;
            ans++;
        }
        return;
    }
    if(left == right)return;
    int mid = (left + right) >> 1;
    query(lson);
    query(rson);
}

ここを上から下に探すことに注意して、いったんゼロではないノードの値を見つけたら、returnすることができます.彼のサブノードはもう下に探す必要はありません.それらはすでにカバーされている場所です.