LOJ#3033. 「JOISC 2019 Day2」两个天线

用后面的天线更新前面的天线，线段树上存历史版本的最大值

也就是线段树需要维护历史版本的最大值，后面的天线的标记中最大的那个和最小的那个，区间中最小的可用天线值，区间中最大的可用天线值

\(i\)可以被\(j\)用到，那么\(j\)在\([i + A_{i},i + B_{i}]\)中，我们枚举右端点的时候，假如到了\(i + A_{i}\)就把\(i\)标记为可用，如果到了\(i + B_{i} + 1\)就把\(i\)标记为不可用

然后枚举右端点，对于一个新加的端点，现在线段树中区间\([i - B_{i},i- A_{i}]\)是可用的，所以我们需要给这个区间打上标记

然后对于一个询问到了对应的右端点，只需要查找区间中历史版本的最大值就好了

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 200005

#define ba 47

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 +c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

struct node {

    int l,r,mn,mx,lzmn,lzmx,oldmx;

}tr[MAXN * 4];

int N,Q,H[MAXN],A[MAXN],B[MAXN],ans[MAXN];

int ql[MAXN],qr[MAXN];

vector<int> ed[MAXN],st[MAXN],qe[MAXN];

void update(int u) {

    tr[u].mn = min(tr[u << 1].mn,tr[u << 1 | 1].mn);

    tr[u].mx = max(tr[u << 1].mx,tr[u << 1 | 1].mx);

    tr[u].oldmx = max(tr[u << 1].oldmx,tr[u << 1 | 1].oldmx);

}

void addlz(int u,int v) {

    tr[u].oldmx = max(tr[u].oldmx,v - tr[u].mn);

    tr[u].oldmx = max(tr[u].oldmx,tr[u].mx - v);

    tr[u].lzmn = min(v,tr[u].lzmn);

    tr[u].lzmx = max(v,tr[u].lzmx);

}

void pushdown(int u) {

    if(tr[u].lzmn <= 1e9) {

	addlz(u << 1,tr[u].lzmn);

	addlz(u << 1 | 1,tr[u].lzmn);

	tr[u].lzmn = 2e9;

    }

    if(tr[u].lzmx > 0) {

	addlz(u << 1,tr[u].lzmx);

	addlz(u << 1 | 1,tr[u].lzmx);

	tr[u].lzmx = 0;

    }

}

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

    tr[u].l = l;tr[u].r = r;

    tr[u].mn = 1e9 + 1,tr[u].mx = 0;

    tr[u].lzmn = 2e9;tr[u].lzmx = 0;tr[u].oldmx = -1;

    if(l == r) return;

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

    build(u << 1,l,mid);

    build(u << 1 | 1,mid + 1,r);

}

void change(int u,int pos,int op) {

    if(tr[u].l == tr[u].r) {

	if(op == 1) tr[u].mn = tr[u].mx = H[pos];

	else {

	    tr[u].mn = 1e9 + 1,tr[u].mx = 0;

	}

	return;

    }

    pushdown(u);

    int mid = (tr[u].l + tr[u].r) >> 1;

    if(pos <= mid) change(u << 1,pos,op);

    else if(pos > mid) change(u << 1 | 1,pos,op);

    update(u);

}

void add(int u,int l,int r,int v) {

    if(tr[u].l == l && tr[u].r == r) {

	addlz(u,v);return;

    }

    pushdown(u);

    int mid = (tr[u].l + tr[u].r) >> 1;

    if(r <= mid) add(u << 1,l,r,v);

    else if(l > mid) add(u << 1 | 1,l,r,v);

    else {add(u << 1,l,mid,v);add(u << 1 | 1,mid + 1,r,v);}

    update(u);

}

int Query(int u,int l,int r) {

    if(tr[u].l == l && tr[u].r == r) return tr[u].oldmx;

    int mid = (tr[u].l + tr[u].r) >> 1;

    pushdown(u);

    if(r <= mid) return Query(u << 1,l,r);

    else if(l > mid) return Query(u << 1 | 1,l,r);

    else {return max(Query(u << 1,l,mid),Query(u << 1 | 1,mid + 1,r));}

}

void Solve() {

    read(N);

    for(int i = 1 ; i <= N ; ++i) {

	read(H[i]);read(A[i]);read(B[i]);

	int l = i + A[i],r = min(i + B[i],N);

	if(l <= r) {st[l].pb(i),ed[r + 1].pb(i);}

    }

    read(Q);

    for(int i = 1 ; i <= Q ; ++i) {

	read(ql[i]);read(qr[i]);

	qe[qr[i]].pb(i);

    }

    build(1,1,N);

    for(int i = 1 ; i <= N ; ++i) {

	for(auto t : st[i]) change(1,t,1);

	for(auto t : ed[i]) change(1,t,-1);

	int l = i - B[i],r = i - A[i];

	l = max(l,1);

	if(l <= r) add(1,l,r,H[i]);

	for(auto id : qe[i]) {

	    ans[id] = Query(1,ql[id],qr[id]);

	}

    }

    for(int i = 1 ; i <= Q ; ++i) {

	out(ans[i]);enter;

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}