線分樹のメンテナンス(最大区間と最大サブセグメントと、最長連続上昇サブシーケンス)

17592 ワード

線分樹データ構造

本論文では主に線分樹を用いて維持する問題(最大区間と最大サブセグメントと最長連続上昇サブシーケンス)を紹介する.
HDU 1540 Tunnel Warfare(最長連続区間＋単点修正)
洛谷P 894[USACO 08 FEB]ホテルHotel(最長連続区間+区間修正)
吉首大学2019年プログラム設計コンテスト-白山茶と紅バラ(最長連続区間＋区間修正)
SPOJ-GS 1 Can 1 answer these queries I(最大サブセグメントと)
HU 3308 LCIS(区間最長連続上昇サブシーケンス)
HDU 1540 Tunnel Warfare(最長連続区間＋単点修正)
三つの操作があります.
操作一:ある村は壊滅された.
操作の2:1つの村の座標を与えて、この村を含む最長の未被村の長さを求めます.
操作三:最後に破壊された村が修復されます.
まず、一番長い連続区間の長さを線分の木で維持したいです.今は1の代表的な変更点で破壊されていません.0で改点が破壊されたことを表しています.そして、前回の破壊点をスタックや配列でセットします.そして線分樹のメンテナンス1の最長度です.コードをよく見てください.

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 5e4 + 5;
const int mod = 10007;
const int inf = 1e9;
const long long onf = 1e18;
#define me(a, b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define PI 3.14159265358979323846
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int ls[maxn << 2], rs[maxn << 2], sum[maxn << 2];
///sum          ，ls              ，rs   r      
int n, m;

void push_up(int l, int r, int rt) {
    int mid = (l + r) >> 1;
    ls[rt] = ls[rt << 1];
    if (ls[rt << 1] == mid - l + 1)///                ，                       
        ls[rt] += ls[rt << 1 | 1];
    rs[rt] = rs[rt << 1 | 1];
    if (rs[rt << 1 | 1] == r - mid)///       
        rs[rt] += rs[rt << 1];
    sum[rt] = max(ls[rt], rs[rt]);
    sum[rt] = max(sum[rt], max(sum[rt << 1], sum[rt << 1 | 1]));
    sum[rt] = max(sum[rt], rs[rt << 1] + ls[rt << 1 | 1]);
    ///          ，   ，         ，         +             。（                 ）
}

void build(int l, int r, int rt) {
    if (l == r) {
        ls[rt] = rs[rt] = sum[rt] = 1;///            
        return;
    }
    int mid = (l + r) >> 1;
    build(lson);
    build(rson);
    push_up(l, r, rt);
}

void push_date(int pos, int x, int l, int r, int rt) {
    sum[rt] = ls[rt] = rs[rt] = 0;
    if (l == r) {
        sum[rt] = ls[rt] = rs[rt] = x;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        push_date(pos, x, lson);
    else
        push_date(pos, x, rson);
    push_up(l, r, rt);
}

int query(int pos, int l, int r, int rt) {
    if (l == r)
        return sum[rt];
    int mid = (l + r) >> 1;
    if (pos <= mid) {///        
        if (pos >= mid - rs[rt << 1] + 1)
            return ls[rt << 1 | 1] + rs[rt << 1];///               ，                   +        （                     ）
        else
            return query(pos, lson);///           ，                 ，        
    } else {
        if (pos <= mid + ls[rt << 1 | 1])///       
            return ls[rt << 1 | 1] + rs[rt << 1];
        else
            return query(pos, rson);
    }
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        build(1, n, 1);
        stack q;
        while (m--) {
            char str[2];
            int x;
            scanf("%s", str);
            if (str[0] == 'D') {
                scanf("%d", &x);
                push_date(x, 0, 1, n, 1);
                q.push(x);
            } else if (str[0] == 'Q') {
                scanf("%d", &x);
                printf("%d
", query(x, 1, n, 1));
            } else {
                if (q.size()) {
                    push_date(q.top(), 1, 1, n, 1);
                    q.pop();
                }
            }
        }
    }
    return 0;
}

洛谷P 894[USACO 08 FEB]ホテルHotel(最長連続区間+区間修正)
注:nがあるという意味では、nの部屋があり、番号は1-nで、最初は全部空き部屋で、m行の操作があります.以下の行はまず一つの数iを入力して、一つの操作を表します.
iが1であれば、照会部屋を表し、もう一つの数xを入力して、1-nの部屋に長さxの連続空き部屋を見つけて、連続x部屋の左端の部屋番号を出力し、この部屋番号を最小にして、長さxの連続空き部屋が見つからない場合、0を出力する.
iが2であれば、チェックアウトを表し、2つの数xを入力します.yは部屋番号x-x+y-1の部屋を空けます.
これは一番長い連続区間です.区間修正の問題は連続区間の一番左端の部屋番号を探すだけです.

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 5e4 + 5;
const int mod = 10007;
const int inf = 1e9;
const long long onf = 1e18;
#define me(a, b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define PI 3.14159265358979323846
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int ls[maxn << 2], rs[maxn << 2], sum[maxn << 2];
int lazy[maxn << 2];
int n, m;

void push_up(int l, int r, int rt) {
    int mid = (l + r) >> 1;
    ls[rt] = ls[rt << 1];
    if (ls[rt << 1] == mid - l + 1)
        ls[rt] += ls[rt << 1 | 1];
    rs[rt] = rs[rt << 1 | 1];
    if (rs[rt << 1 | 1] == r - mid)
        rs[rt] += rs[rt << 1];
    sum[rt] = max(ls[rt], rs[rt]);
    sum[rt] = max(sum[rt], max(sum[rt << 1], sum[rt << 1 | 1]));
    sum[rt] = max(sum[rt], rs[rt << 1] + ls[rt << 1 | 1]);
}

void push_down(int l, int r, int rt) {
    if (lazy[rt] != -1) {
        int mid = (l + r) >> 1;
        lazy[rt << 1] = lazy[rt << 1 | 1] = lazy[rt];
        sum[rt << 1] = ls[rt << 1] = rs[rt << 1] = (mid - l + 1) * lazy[rt];
        sum[rt << 1 | 1] = ls[rt << 1 | 1] = rs[rt << 1 | 1] = (r - mid) * lazy[rt];
        lazy[rt] = -1;
    }
}

void build(int l, int r, int rt) {
    sum[rt] = ls[rt] = rs[rt] = 0;
    if (l == r) {
        sum[rt] = ls[rt] = rs[rt] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(lson);
    build(rson);
    push_up(l, r, rt);
}

void push_date(int L, int R, int opt, int l, int r, int rt) {
    if (L <= l && R >= r) {
        sum[rt] = ls[rt] = rs[rt] = (r - l + 1) * opt;
        lazy[rt] = opt;
        return;
    }
    push_down(l, r, rt);
    int mid = (l + r) >> 1;
    if (R <= mid)
        push_date(L, R, opt, lson);
    else if (L > mid)
        push_date(L, R, opt, rson);
    else {
        push_date(L, mid, opt, lson);
        push_date(mid + 1, R, opt, rson);
    }
    push_up(l, r, rt);
}

int Find_pos(int len, int l, int r, int rt) {
    if(l==r)
        return l;
    push_down(l, r, rt);
    int mid = (l + r) >> 1;
    if(len<=sum[rt<<1])
        return Find_pos(len,lson);
    else if(rs[rt<<1]+ls[rt<<1|1]>=len)
        return mid-rs[rt<<1]+1;
    else
        return Find_pos(len,rson);
}

int main() {
    me(lazy, -1);
    scanf("%d%d", &n, &m);
    build(1, n, 1);
    while (m--) {
        int opt, l, len;
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d", &len);
            if (len <= sum[1]) {
                int pos = Find_pos(len, 1, n, 1);
                printf("%d
", pos);
                push_date(pos, pos+len-1, 0, 1, n, 1);
            } else
                printf("0
");
        } else {
            scanf("%d%d", &l, &len);
            push_date(l, l + len - 1, 1, 1, n, 1);
        }
    }
    return 0;
}

吉首大学2019年プログラム設計コンテスト-白山茶と紅バラ(最長連続区間＋区間修正)
現在は1段のシーケンスを示していますが、0と1だけです.現在は2つの操作があります.
操作一:[l,r]を与え、この区間の最長連続0区間の長さを求める.
操作二:［l,r］を与え、この区間の0を全部1,1にして全部0にします.
現在は2本の線分樹を建立し、1つは最長連続1区間の長さを保存し、1つは最長連続0区間の長さを保存し、1つは従来の求法でいいです.2つを操作する時、対応区間の対応配列の値を全部交換します.
注意:反転2回は反転なしに等しいので、lazy配列は、初期値が0であり、1は反転することを表しています.その後、修正するたびに、lazy配列の値が異ならないか1でいいです.

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int maxn = 1e5 + 5;
const int mod = 10007;
const int inf = 1e9;
const long long onf = 1e18;
#define me(a, b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
#define lson L,mid,rt<<1
#define rson mid+1,R,rt<<1|1
#define PI 3.14159265358979323846
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int ls1[maxn << 2], rs1[maxn << 2], sum1[maxn << 2];
int ls2[maxn << 2], rs2[maxn << 2], sum2[maxn << 2];
int lazy[maxn << 2];
int n, m, x;

void push_up(int l, int r, int rt) {
    int mid = (l + r) >> 1;
    ls1[rt] = ls1[rt << 1];
    if (ls1[rt << 1] == mid - l + 1)
        ls1[rt] += ls1[rt << 1 | 1];
    rs1[rt] = rs1[rt << 1 | 1];
    if (rs1[rt << 1 | 1] == r - mid)
        rs1[rt] += rs1[rt << 1];
    sum1[rt] = max(sum1[rt << 1], sum1[rt << 1 | 1]);
    sum1[rt] = max(sum1[rt], max(ls1[rt], rs1[rt]));
    sum1[rt] = max(sum1[rt], rs1[rt << 1] + ls1[rt << 1 | 1]);
    ls2[rt] = ls2[rt << 1];
    if (ls2[rt << 1] == mid - l + 1)
        ls2[rt] += ls2[rt << 1 | 1];
    rs2[rt] = rs2[rt << 1 | 1];
    if (rs2[rt << 1 | 1] == r - mid)
        rs2[rt] += rs2[rt << 1];
    sum2[rt] = max(sum2[rt << 1], sum2[rt << 1 | 1]);
    sum2[rt] = max(sum2[rt], max(ls2[rt], rs2[rt]));
    sum2[rt] = max(sum2[rt], rs2[rt << 1] + ls2[rt << 1 | 1]);
}

void push_down(int rt) {
    if (lazy[rt]) {
        lazy[rt << 1] ^= 1;
        lazy[rt << 1 | 1] ^= 1;
        swap(ls1[rt << 1], ls2[rt << 1]);
        swap(rs1[rt << 1], rs2[rt << 1]);
        swap(sum1[rt << 1], sum2[rt << 1]);
        swap(ls1[rt << 1 | 1], ls2[rt << 1 | 1]);
        swap(rs1[rt << 1 | 1], rs2[rt << 1 | 1]);
        swap(sum1[rt << 1 | 1], sum2[rt << 1 | 1]);
        lazy[rt] = 0;
    }
}

void build(int l, int r, int rt) {
    if (l == r) {
        scanf("%d", &x);
        ls1[rt] = rs1[rt] = sum1[rt] = x;
        if (x == 1)
            ls2[rt] = rs2[rt] = sum2[rt] = 0;
        else
            ls2[rt] = rs2[rt] = sum2[rt] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    push_up(l, r, rt);
}

void push_date(int l, int r, int L, int R, int rt) {
    if (L <= l && R >= r) {
        lazy[rt] ^= 1;
        swap(ls1[rt], ls2[rt]);
        swap(rs1[rt], rs2[rt]);
        swap(sum1[rt], sum2[rt]);
        return;
    }
    push_down(rt);
    int mid = (l + r) >> 1;
    if (R <= mid)
        push_date(l, mid, L, R, rt << 1);
    else if (L > mid)
        push_date(mid + 1, r, L, R, rt << 1 | 1);
    else {
        push_date(l, mid, L, mid, rt << 1);
        push_date(mid + 1, r, mid + 1, R, rt << 1 | 1);
    }
    push_up(l, r, rt);
}

int query(int l, int r, int L, int R, int rt) {
    if (L <= l && R >= r)
        return sum1[rt];
    push_down(rt);
    int mid = (l + r) >> 1;
    if (R <= mid) {
        return query(l, mid, L, R, rt << 1);
    } else if (L > mid) {
        return query(mid + 1, r, L, R, rt << 1 | 1);
    } else {
        int len1 = query(l, mid, L, mid, rt << 1);
        int len2 = query(mid + 1, r, mid + 1, R, rt << 1 | 1);
        int len3 = min(mid - L + 1, rs1[rt << 1]) + min(R - mid, ls1[rt << 1 | 1]);
        return max(len1, max(len2, len3));
    }
    return 0;
}

int main() {
    scanf("%d", &n);
    build(1, n, 1);
    scanf("%d", &m);
    while (m--) {
        int opt, l, r;
        scanf("%d%d%d", &opt, &l, &r);
        if (opt == 1)
            push_date(1, n, l, r, 1);
        else
            printf("%d
", query(1, n, l, r, 1));
    }
    return 0;
}

SPOJ-GS 1 Can 1 answer these queries I(最大サブセグメントと)
セクションのシーケンスを与えて、m回の問い合わせを行います.この区間の最大連続サブセグメントと.
一番長い連続サブシーケンスと同じです.これはテンプレートの問題です.直接コードをつけます.

#pragma comment(linker, "/STACK:102400000,102400000")

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int mod = 998244353;
const int maxn = 5e4 + 5;
const int inf = 1e9;
const long long onf = 1e18;
#define me(a, b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
#define Lson l,mid,rt<<1
#define Rson mid+1,r,rt<<1|1
#define lson rt<<1
#define rson rt<<1|1
#define PI 3.14159265358979323846
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
struct node {
    int val, lmax, rmax, max;
} tree[maxn << 2];

void push_up(int rt) {
    tree[rt].max = max(max(tree[lson].max, tree[rson].max), tree[lson].rmax + tree[rson].lmax);
    tree[rt].lmax = max(tree[lson].lmax, tree[lson].val + tree[rson].lmax);
    tree[rt].rmax = max(tree[rson].rmax, tree[rson].val + tree[lson].rmax);
    tree[rt].val = tree[lson].val + tree[rson].val;
}

void build(int l, int r, int rt) {
    if (l == r) {
        scanf("%d", &tree[rt].val);
        tree[rt].lmax = tree[rt].rmax = tree[rt].max = tree[rt].val;
        return;
    }
    int mid = (l + r) >> 1;
    build(Lson);
    build(Rson);
    push_up(rt);
}

node query(int ql, int qr, int l, int r, int rt) {
    if (ql <= l && qr >= r)
        return tree[rt];
    int mid = (l + r) >> 1;
    if (qr <= mid)
        return query(ql, qr, Lson);
    else if (ql > mid)
        return query(ql, qr, Rson);
    else {
        node L = query(ql, mid, Lson);
        node R = query(mid + 1, qr, Rson);
        node ans;
        ans.max = max(max(L.max, R.max), L.rmax + R.lmax);
        ans.lmax = max(L.lmax, L.val + R.lmax);
        ans.rmax = max(R.rmax, R.val + L.rmax);
        return ans;
    }
}

int main() {
    int n, m;
    scanf("%d", &n);
    build(1, n, 1);
    scanf("%d", &m);
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d
", query(l, r, 1, n, 1).max);
    }
    return 0;
}

HU 3308 LCIS(区間最長連続上昇サブシーケンス)
区間の最長連続上昇サブシーケンスを求めます.
PS:ノードの値を変更するため、dpは使用できません.ここで線分樹でメンテナンスできます.
これは裸の線分樹で、最長の上昇を求めるサブシーケンスの問題です.詳細はコードを見て、主に左子樹、右子樹、区間の最長男シーケンスの長さを更新することに注意します.

#pragma comment(linker, "/STACK:102400000,102400000")

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include

const int mod = 998244353;
const int maxn = 1e5 + 5;
const int inf = 1e9;
const long long onf = 1e18;
#define me(a, b) memset(a,b,sizeof(a))
#define lowbit(x) x&(-x)
#define Lson l,mid,rt<<1
#define Rson mid+1,r,rt<<1|1
#define lson rt<<1
#define rson rt<<1|1
#define PI 3.14159265358979323846
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int a[maxn], sum[maxn << 2], ls[maxn << 2], rs[maxn << 2];

void updata(int l, int r, int rt)///           
{
    int mid = (l + r) >> 1;
    ls[rt] = ls[lson], rs[rt] = rs[rson];
    sum[rt] = max(sum[lson], sum[rson]);
    if (a[mid] < a[mid + 1]) {///       ，            
        if (ls[rt] == mid - l + 1)///               ，      ，                 
            ls[rt] = ls[lson] + ls[rson];
        if (rs[rt] == r - mid)///     
            rs[rt] = rs[rson] + rs[lson];
        sum[rt] = max(sum[rt], ls[rson] + rs[lson]);
    }
}

void build(int l, int r, int rt)///  
{
    if (l == r) {
        sum[rt] = ls[rt] = rs[rt] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(Lson);
    build(Rson);
    updata(l, r, rt);
}

void pushdata(int pos, int c, int l, int r, int rt)///     
{
    if (l == r) {
        a[l] = c;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        pushdata(pos, c, Lson);
    else
        pushdata(pos, c, Rson);
    updata(l, r, rt);
}

int query(int L, int R, int l, int r, int rt)///         
{
    if (l >= L && R >= r)
        return sum[rt];
    int ret = 0;
    int mid = (l + r) >> 1;
    if (mid >= L)
        ret = max(ret, query(L, R, Lson));
    if (mid < R)
        ret = max(ret, query(L, R, Rson));
    if (a[mid] < a[mid + 1]) {
        ret = max(ret, min(mid - L + 1, rs[lson]) + min(R - mid, ls[rson]));
        ///[m+1,R] [m+1,r]         +[L,m] [l,m]     .
    }
    return ret;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        build(1, n, 1);
        while (m--) {
            char s[2];
            int a, b;
            scanf("%s%d%d", s, &a, &b);
            if (s[0] == 'U')
                pushdata(a + 1, b, 1, n, 1);
            else
                printf("%d
", query(a + 1, b + 1, 1, n, 1));
        }
    }
    return 0;
}

UVA-10152 ShellSort