CF 338 E Optimize(線分樹)

2917 ワード

転載は出典を明記してください.ありがとうございます.    by---cxlove
出題者の問題が分かりませんでした.囧
そしてtouristコードを見て、短くてよく分かりました.
私たちはbを並べた後、明らかに組み合わせたら必ず欲張りです.
aのあるサブストリングa'に対して条件を満たすと、明らかにすべての数とbの最大要素が加算されてh以下ではない.
少なくともlen−1個の数があるbの中の次数の大きい要素の加算はhより小さくない.このように類推すると、まず前処理してaの各要素に対して、b列のどの要素との加算はhより小さくなく、明らかに順序付けの後の2つの要素である.
 
ある区間の数を選択すると、区間がカバーされています.bの第iの要素は少なくともi回上書きされていますか?
便利さのために、i番目の位からiを引いて、区間の最小値が負でないかどうかを判断します.
 
#include <iostream>

#include <queue>

#include <algorithm>

#include <cstdio>

#include <cstring>

#define lson step << 1

#define rson step << 1 | 1

using namespace std;

typedef long long LL;

const int N = 150005;

struct Node {

    int left , right , add , mn;

}L[N << 2];

int n , h , b[N] , len , a[N];

void bulid (int step , int l , int r) {

    L[step].left = l;

    L[step].right = r;

    L[step].add = 0;

    L[step].mn = 0;

    if (l == r) return ;

    int m = (l + r) >> 1;

    bulid (lson , l , m);

    bulid (rson , m + 1 , r);

}

void update (int step , int l , int r , int v);

void push_down (int step) {

    int l = L[step].left , r = L[step].right , m = (l + r) >> 1;

    if (L[step].add) {

        update (lson , l , m , L[step].add);

        update (rson , m + 1 , r , L[step].add);

        L[step].add = 0;

    }

}

void push_up (int step) {

    L[step].mn = min (L[lson].mn , L[rson].mn);

}

void update (int step , int l , int r , int v) {

    if (L[step].left == l && L[step].right == r) {

        L[step].mn += v;

        L[step].add += v;

        return ;

    }

    push_down (step);

    int m = (L[step].left + L[step].right) >> 1;

    if (r <= m) update (lson , l , r , v);

    else if (l > m) update (rson , l , r , v);

    else {

        update (lson , l , m , v);

        update (rson , m + 1 , r , v);

    }

    push_up (step);

} 

int main() {

    int t;

    #ifndef ONLINE_JUDGE

        freopen ("input.txt" , "r" , stdin);

        // freopen ("output.txt" , "w" , stdout);

    #endif

    scanf ("%d %d %d" , &n , &len , &h);

    for (int i = 0 ; i < len ; i ++)

        scanf ("%d" , &b[i]);

    sort (b , b + len);

    bulid (1 , 0 , len);

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

        scanf ("%d" , &a[i]);

        a[i] = lower_bound (b , b + len , h - a[i]) - b;

    } 

    for (int i = 0 ; i < len ; i ++) 

        update (1 , i , i , -(i + 1));

    for (int i = 0 ; i < len - 1 ; i ++)

        update (1 , a[i] , len , 1);

    int ans = 0;

    for (int i = len - 1 ; i < n ; i ++) {

        update (1 , a[i] , len , 1);

        if (L[1].mn >= 0) ans ++;

        update (1 , a[i - len + 1] , len , -1);

    }

    printf ("%d
" , ans); return 0; }