Codeforces 739C Alyona and towers 线段树

Alyona and towers

这个题写起来真的要人命。。。

我们发现一个区间被加上一个d的时候， 内部的结构是不变的， 改变的只是左端点右端点的值， 这样就能区间合并了。

如果用差分的话会简单一些， 就变成了求前一段是负数，后一段是正数的最长段多长。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ull unsigned long long

using namespace std;

const int N = 3e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

const double PI = acos(-);

int n, m;

LL lazy[N << ];

struct Node {

    LL lv, rv;

    int mx, rup, rdn, lup, ldn;

    bool up, dn, mon;

    void print() {

        puts("");

        printf("lv: %lld  rv: %lld\n", lv, rv);

        printf("mx: %d\n", mx);

        printf("rup: %d  rdn: %d  lup: %d  ldn: %d\n", rup, rdn, lup, ldn);

        printf("up: %d  dn: %d  mon: %d\n", up, dn, mon);

        puts("");

    }

} a[N << ];

Node operator + (const Node& a, const Node& b) {

    Node c;

    c.lv = a.lv; c.rv = b.rv;

    c.mx = max(a.mx, b.mx);

    c.rup = b.rup;

    c.rdn = b.rdn;

    c.lup = a.lup;

    c.ldn = a.ldn;

    if(a.rv < b.lv) c.mx = max(c.mx, a.rup + b.lup);

    if(a.rv > b.lv) c.mx = max(c.mx, a.rdn + b.ldn);

    if(a.rv != b.lv) c.mx = max(c.mx, a.rup + b.ldn);

    if(b.up && a.rv < b.lv) c.rup = max(c.rup, a.rup + b.rup);

    if(b.mon && a.rv < b.lv) c.rdn = max(c.rdn, a.rup + b.rdn);

    if(b.dn && a.rv > b.lv) c.rdn = max(c.rdn, a.rdn + b.rdn);

    if(a.mon && a.rv > b.lv) c.lup = max(c.lup, a.lup + b.ldn);

    if(a.up && a.rv < b.lv) c.lup = max(c.lup, a.lup + b.lup);

    if(a.dn && a.rv > b.lv) c.ldn = max(c.ldn, a.ldn + b.ldn);

    c.up = a.up && b.up && a.rv < b.lv;

    c.dn = a.dn && b.dn && a.rv > b.lv;

    c.mon = false;

    if(c.up || c.dn) c.mon = true;

    else {

        if(a.up && b.dn && a.rv != b.lv) c.mon = true;

        if(a.mon && b.dn && a.rv > b.lv) c.mon = true;

        if(b.mon && a.up && a.rv < b.lv) c.mon = true;

    }

    return c;

}

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

void push(int rt) {

    if(lazy[rt]) {

        a[rt << ].lv += lazy[rt]; a[rt << ].rv += lazy[rt];

        a[rt <<  | ].lv += lazy[rt]; a[rt <<  | ].rv += lazy[rt];

        lazy[rt << ] += lazy[rt];

        lazy[rt <<  | ] += lazy[rt];

        lazy[rt] = ;

    }

}

void build(int l, int r, int rt) {

    if(l == r) {

        int x; scanf("%d", &x);

        a[rt] = Node{x, x, , , , , , , , };

        return;

    }

    int mid = l + r >> ;

    build(lson); build(rson);

    a[rt] = a[rt << ] + a[rt <<  | ];

}

void update(int L, int R, int val, int l, int r, int rt) {

    if(l >= L && r <= R) {

        a[rt].lv += val; a[rt].rv += val;

        lazy[rt] += val;

        return;

    }

    int mid = l + r >> ;

    push(rt);

    if(L <= mid) update(L, R, val, lson);

    if(R > mid)  update(L, R, val, rson);

    a[rt] = a[rt << ] + a[rt <<  | ];

}

int main() {

    scanf("%d", &n);

    build(, n, );

    scanf("%d", &m);

    while(m--) {

        int L, R, d;

        scanf("%d%d%d", &L, &R, &d);

        update(L, R, d, , n, );

        printf("%d\n", a[].mx);

    }

    return ;

}

/*

*/