C. 作弊
为了防止改不完题，这个神奇的东西我一定要现在就写！
%%%Chen_jr 一看就知道我又鹤了
设s(l, r)表示在[l, r]之间作一次弊的最大收益，这个东西居然可以优化！！转移方程是f[i] = max(f[i], f[j-1]+s(j, i))，发现每一个时刻只有右端点是i的s是有用的，线段树的一部分就是右端点为i时，左端点为(线段树下标)的s的大小，同时还把f[j-1]记录到了f[j]上，这样就可以让答案都在一个点上维护线段树的区间最值了！
现在就需要维护右端点移动时s的变化。(鹤一下)考虑分开计算每个人的贡献，i对s(i, j)产生贡献当且仅当mx(l, r)属于[li, ri]，将其拆成max(mx(l, i), mx(i, r))属于[li, ri]，也就是mx(l, i)，mx(i, r)都要<=ri，且其中至少一个>=li。
对于每个i预处理出mx(l, i)，mx(i, r)属于[li, ri]的l, r的范围，记为[lri, lli], [rli, rri](因为mx从i向左递增，从i向右递增)，第一个l/r表示是谁的范围，第二个l/r表示满足哪个条件(>=li还是<=ri)。具体实现的时候找的是(以l的范围为例)满足a[j]>=l[i]的i左边的最大的j和满足a[k]>r[i]的i左边的最大的k，它+1才是标准的范围，但是恰好可以在线段树上消去贡献时作为起点。
预处理可以用树状数组，下标是值域，val是位置，因为要找值更大的，可以直接往后找，也可以把树状数组翻转过来让a更大的在左边，向左要找val最小的，向右要找val最大的，原来的函数可以直接用，把权值和答案都变成相反的就好，这样负负得正。
当右端点属于[i, ri]时，左端点在[lli, lri]内有贡献；属于[rli, rri]时，左端点在[lli, i[内有贡献，注意[lri, lli]内的贡献不需要重复统计所以从lli+1开始；大于rri时，没有贡献。第一层循环的i既表示讨论到的位置，又表示当前的右端点，一开始先把i更新为f[i-1]修改之后它就变成i了，f[i-1]不是f[i]的初值因为s(i, i)可能不是0。记录以i为转折点的x，在适当的时候去掉x的贡献。
code
#include <bits/stdc++.h>
using namespace std;
//typedef long long ll;你猜为什么过不了编译
const int maxn = 1e5 + 5;
int f[maxn], a[maxn], n, l[maxn], r[maxn];
int ll[maxn], lr[maxn], rl[maxn], rr[maxn];
vector<int> RL[maxn], RR[maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
struct BIT
{
int t[maxn];
int lowbit(int x) {return x & -x;}
void modify(int x, int val) {x = n - x + 1; while(x <= n) {t[x] = max(t[x], val); x += lowbit(x);}}
int query(int x) {x = n - x + 1; int ans = 0; while(x) {ans = max(ans, t[x]); x -= lowbit(x);} return ans;}
void clear() {for(int i=1; i<=n; i++) t[i] = 0;}
}T;
struct seg
{
struct node
{
int val, tag;
}t[maxn<<2];
void pushdown(int x)
{
int ls = x<<1, rs = x<<1|1;
t[ls].val += t[x].tag;
t[rs].val += t[x].tag;
t[ls].tag += t[x].tag;
t[rs].tag += t[x].tag;
t[x].tag = 0;
}
void pushup(int x)
{
t[x].val = max(t[x<<1].val, t[x<<1|1].val);
}
void modify(int x, int l, int r, int L, int R, int val)
{
if(L <= l && r <= R)
{
t[x].val += val; t[x].tag += val;
return;
}
if(t[x].tag) pushdown(x);
int mid = (l + r) >> 1;
if(L <= mid) modify(x<<1, l, mid, L, R, val);
if(R > mid) modify(x<<1|1, mid+1, r, L, R, val);
pushup(x);
}
int query(int x, int l, int r, int L, int R)
{
if(L <= l && r <= R) return t[x].val;
if(t[x].tag) pushdown(x);
int mid = (l + r) >> 1, ans = 0;
if(L <= mid) ans = max(ans, query(x<<1, l, mid, L, R));
if(R > mid) ans = max(ans, query(x<<1|1, mid+1, r, L, R));
return ans;
}
}t;
int main()
{
freopen("cheat.in", "r", stdin);
freopen("cheat.out", "w", stdout);
n = read();
for(int i=1; i<=n; i++) a[i] = read();
for(int i=1; i<=n; i++) l[i] = read(), r[i] = read();
for(int i=1; i<=n; i++)
{
T.modify(a[i], i); ll[i] = T.query(l[i]), lr[i] = T.query(r[i]+1);
}
T.clear();
for(int i=n; i>=1; i--)
{
T.modify(a[i], n-i+1); rl[i] = n-T.query(l[i])+1, rr[i] = n-T.query(r[i]+1)+1;
}
for(int i=1; i<=n; i++)
{
if(rl[i]) RL[rl[i]].push_back(i);
if(rr[i]) RR[rr[i]].push_back(i);
}
for(int i=1; i<=n; i++)
{
t.modify(1, 1, n, i, i, t.query(1, 1, n, 1, n));
if(ll[i]) t.modify(1, 1, n, 1, ll[i], 1);
if(lr[i]) t.modify(1, 1, n, 1, lr[i], -1);
for(int x : RL[i]) if(ll[x] < x) t.modify(1, 1, n, ll[x]+1, x, 1);
for(int x : RR[i]) if(lr[x] < x) t.modify(1, 1, n, lr[x]+1, x, -1);
}
printf("%d\n", t.query(1, 1, n, 1, n));
return 0;
}标签：ch,2022NOIPA,23,int,lli,maxn,联测,端点,mx From： https://www.cnblogs.com/Catherine2006/p/16870762.html