$S a i l$

题目描述见链接 .

$<mstyle mathcolor="red"> 正解部分 </mstyle>$

首先旗杆的顺序是对答案没有影响的, 我们只需关注每一行放置了多少旗帜,
于是可以先按照旗杆的高度排序, 然后考虑从左向右按顺序安插旗子,
对当前的旗杆 $i$ , 为了使得它对答案贡献最小, 贪心地选取 $[1, H_{i}]$ 高度内旗子个数前 $K_{i}$ 小的高度放置旗子,
这样能保证答案最优 .

$证明 :$
为了保证答案最优, 放旗子少的高度在后面肯定会放置旗子, 而先放置和后放置对答案是不造成影响的 .

题目就转化为了: 给出一个数组 $A []$ , 有 $N$ 次操作, 第 $i$ 次操作是将 $A []$ 的前 $H_{i}$ 项的前 $K_{i}$ 小项加 $1$ .

可以证明保持 $A []$ 单调递减可以得到最优方案,

$证明 :$
假设已有一个最优方案, 对于 $H_{1} > H_{2}$ 且 $A [H_{1}] > A [H_{2}]$ 的情况, 可以将 $H_{1}$ 的旗子数与 $H_{2}$ 的旗子数反转, 从而保证 $A []$ 的递减性 .

所以要进行操作的元素就可以转化成一个连续的区间: $[H_{i} - K_{i} + 1, H_{i}]$ , 直接使用 线段树 进行区间加减 $?$

仍然不行, 设 $L = H_{i} - K_{i} + 1, R = H_{i}$ , 若 $A [L - 1] = = A [L]$ , 直接进行区间加会破坏单调性, 于是需要找到 $A [j] = = A [L]$ 的最小 $j$ , 和 $A [k] = = A [L]$ 的最大 $k$ .

若 $k \geq R$ , 则直接对区间 $[L, L + K_{i} - 1]$ 进行操作 .
若 $k < R$ , 则分别对区间 $[L, L + (R - k)], <mtext> </mtext> [k + 1, R]$ 进行操作 .

$<mstyle mathcolor="red"> 实现部分 </mstyle>$

找 $L$ 时先找到 $A [H_{i}]$ , 然后在线段树查询时尽量往左子树 $" 靠 "$ ,
具体地说, 若左子树的最小值小于 $A [H_{i}]$ , 说明左子树可能存在 $A [H_{i}]$ , 否则向右走 .
找 $R$ 时先找到 $A [H_{i}]$ , 然后在线段树查询时尽量往右子树 $" 靠 "$ ,
具体地说, 若右子树的最大值小于 $A [H_{i}]$ , 说明右子树可能存在 $A [H_{i}]$ , 否则向左走 .

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

const int maxn = 100005;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

int N;
int Max_h;

struct Mast{ int h, k; } A[maxn];

bool cmp_1(Mast a, Mast b){ return a.h < b.h; }

struct Seg_tree{ 
        struct Node{ int l, r, max_v, min_v, tag; } T[maxn<<2];
        void Build(int k, int l, int r){
                T[k].l = l, T[k].r = r;
                if(l == r) return ; int mid = l+r >> 1;
                Build(k<<1, l, mid), Build(k<<1|1, mid+1, r);
        }
        void Push_down(int k){
                T[k<<1].tag += T[k].tag, T[k<<1].min_v += T[k].tag, T[k<<1].max_v += T[k].tag;
                T[k<<1|1].tag += T[k].tag, T[k<<1|1].min_v += T[k].tag, T[k<<1|1].max_v += T[k].tag;
                T[k].tag = 0;
        }
        int Query_val(int k, int aim_id){
                int l = T[k].l, r = T[k].r; 
                if(l == r) return T[k].min_v; if(T[k].tag) Push_down(k);
                int mid = l+r >> 1;
                if(aim_id <= mid) return Query_val(k<<1, aim_id);
                return Query_val(k<<1|1, aim_id);
        }
        int Query_L(int k, int aim_v){
                int l = T[k].l, r = T[k].r;
                if(l == r) return l; if(T[k].tag) Push_down(k);
                if(T[k<<1].min_v <= aim_v) return Query_L(k<<1, aim_v);
                return Query_L(k<<1|1, aim_v);
        }
        int Query_R(int k, int aim_v){
                int l = T[k].l, r = T[k].r;
                if(l == r) return l; if(T[k].tag) Push_down(k);
                if(T[k<<1|1].max_v >= aim_v) return Query_R(k<<1|1, aim_v);
                return Query_R(k<<1, aim_v);
        }
        void Modify(int k, int ql, int qr, int add){
                int l = T[k].l, r = T[k].r;
                if(ql <= l && r <= qr){ T[k].tag += add, T[k].max_v += add, T[k].min_v += add; return ; }
                if(T[k].tag) Push_down(k);
                int mid = l+r >> 1;
                if(ql <= mid) Modify(k<<1, ql, qr, add);
                if(qr > mid) Modify(k<<1|1, ql, qr, add);
                T[k].min_v = std::min(T[k<<1].min_v, T[k<<1|1].min_v);
                T[k].max_v = std::max(T[k<<1].max_v, T[k<<1|1].max_v);
        }
        ll calc_ans(int k){
                int l = T[k].l, r = T[k].r;
                if(l == r) return 1ll*T[k].min_v*(T[k].min_v-1)/2;
                if(T[k].tag) Push_down(k);
                return calc_ans(k<<1) + calc_ans(k<<1|1);
        }
} seg_t;

int main(){
        N = read();
        for(reg int i = 1; i <= N; i ++) Max_h = std::max(Max_h, A[i].h=read()), A[i].k = read();
        std::sort(A+1, A+N+1, cmp_1);
        seg_t.Build(1, 1, Max_h);
        for(reg int i = 1; i <= N; i ++){
                int tmp = seg_t.Query_val(1, A[i].h-A[i].k+1);
                int L = seg_t.Query_L(1, tmp), R = seg_t.Query_R(1, tmp);
                if(R >= A[i].h) seg_t.Modify(1, L, L+A[i].k-1, 1);
                else{
                        int len = A[i].k - (A[i].h - R);
                        seg_t.Modify(1, R+1, A[i].h, 1), seg_t.Modify(1, L, L+len-1, 1);
                }
        }
        printf("%lld\n", seg_t.calc_ans(1));
        return 0;
}
/* 1. calc_ans() leak of push_down; 2. Query_val() swap(mid, aim_v) */

官方题解

BZOJ1805: [Ioi2007]Sail 船帆 [思维题,线段树优化贪心]

S a i l Sail Sail

<mstyle mathcolor="red"> 正 解 部 分 </mstyle> \color{red}{正解部分} 正解部分

<mstyle mathcolor="red"> 实 现 部 分 </mstyle> \color{red}{实现部分} 实现部分

$S a i l$

$<mstyle mathcolor="red"> 正解部分 </mstyle>$

$<mstyle mathcolor="red"> 实现部分 </mstyle>$