2022-10-2总结(上午)

序列问题

设 $f(i,j)$ 为前 $i$ 个数中选出了 $j$ 个数的最大值，时间复杂度 $O(n^2)$

考虑优化一下上面那个东西，如果 $A_i > i$, 那么这个数一定无法造成贡献，直接忽略即可。

设 $f(i)$ 为将第 $i$ 个数作为 $B$ 序列最后一个数且造成 $1$ 贡献的最大值。

考虑由 $f(j)$ 转移至 $f(i)$ 的条件：

1. $j < i$

2. $A_j < A_i$

3. $A_i-A_j \le i-j$

可以将其看作三维偏序问题，使用 CDQ 分治优化 DP, 时间复杂度 $O(n \log^2 n)$，但是过不去。

仔细观察条件，发现满足条件 2,3 一定可以满足条件 1，然后就变成一个二维的问题了，可以先按 $A_i$ 排序，然后求一个 $i-A_i$ 的最长不下降子序列，其长度即为答案。

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("sequence.in", "r", stdin);
        freopen("sequence.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

const int N = 1e6+10;

struct node {
    int a, id;
};

int n;
node x[N];
int t[N], cnt;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> x[i].a, x[i].id = i;
    
    sort(x+1, x+n+1, [](node a, node b){
        if(a.a != b.a) return a.a < b.a;
        else return a.id > b.id;
    });
    for(int i = 1; i <= n; i++)
    {
        if(x[i].a > x[i].id) continue;
        int p = upper_bound(t+1, t+cnt+1, x[i].id-x[i].a)-t;
        if(p == cnt+1)
            t[++cnt] = x[i].id-x[i].a;
        else
            t[p] = x[i].id-x[i].a;
    }
    
    cout << cnt << "\n";
}

区间排序

套路数据结构，如果 $a_i$ 互不相同，那么一个合法区间的条件就是 $极差-区间长度=-1$，如果出现 $a_i$ 相同的情况，就改成 $极差-区间种类数=-1$ 即可。

极差可以分别维护最大值最小值的单调栈，区间种类数可以统计区间里第一次出现的数的个数。

然后枚举右端点，线段树维护每个左端点当前的值， 查询的时候查询区间最小值个数即可。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
struct Rhine_Lab {
    Rhine_Lab()
    {
        freopen("easy.in", "r", stdin);
        freopen("easy.out", "w", stdout);
    }
};
Rhine_Lab Ptilopsis_w;

const int N = 1e5+10;
const int INF = 0x3f3f3f3f;

namespace tree {
    struct node {
        int l, r;
        int min, cnt;
        int lz;
    } a[N*4];
    void build(int l, int r, int i = 1);
    void add(int ql, int qr, int val, int i = 1);
    node query(int ql, int qr, int i = 1);
}

struct stack {
    int a[N], tp;
    stack() { tp = 0; memset(a, 0, sizeof(a)); }
    void push(int x) { a[++tp] = x; }
    int top() { return tp ? a[tp] : 0; }
    int bottom() { return a[1]; }
    int second() { return tp ? a[tp-1] : 0; }
    void pop() { if(tp) a[tp--] = 0; }
    int size() { return tp; }
};

int n;
int a[N];
map<int,int> pos;
int last[N];
stack stmax, stmin;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        last[i] = pos[a[i]];
        pos[a[i]] = i;
    }
    
    long long ans = 0;
    tree::build(1, n);
    for(int i = 1; i <= n; i++)
    {
        tree::add(last[i]+1, i, -1);
        while(stmax.size()&&a[stmax.top()]<a[i])
        {
            tree::add(stmax.second()+1, stmax.top(), a[i]-a[stmax.top()]);
            stmax.pop();
        }
        stmax.push(i);
        while(stmin.size()&&a[stmin.top()]>a[i])
        {
            tree::add(stmin.second()+1, stmin.top(), a[stmin.top()]-a[i]);
            stmin.pop();
        }
        stmin.push(i);
        
        auto tmp = tree::query(1, i);
        if(tmp.min == -1) ans += tmp.cnt;
    }
    
    cout << ans << "\n";
}

namespace tree {
    #define ls (i<<1)
    #define rs (i<<1|1)
    node operator + (node a, node b)
    {
        node c;
        c.l = a.l, c.r = b.r;
        c.min = min(a.min, b.min);
        if(a.min == b.min)
            c.cnt = a.cnt+b.cnt;
        else if(a.min < b.min)
            c.cnt = a.cnt;
        else
            c.cnt = b.cnt;
        c.lz = 0;
        return c;
    }
    void add(node &i, int val)
    {
        i.min += val;
        i.lz += val;
    }
    void push_down(int i)
    {
        if(!a[i].lz) return; 
        add(a[ls], a[i].lz);
        add(a[rs], a[i].lz);
        a[i].lz = 0;
    }
    void build(int l, int r, int i)
    {
        a[i].l = l, a[i].r = r;
        if(l == r)
        {
            a[i].min = 0;
            a[i].cnt = 1;
            return void();
        }
        int mid = (l+r)>>1;
        build(l, mid, ls);
        build(mid+1, r, rs);
        a[i] = a[ls]+a[rs];
    }
    void add(int ql, int qr, int val, int i)
    {
        if(ql <= a[i].l and a[i].r <= qr)
            return add(a[i], val);
        push_down(i);        
        if(ql <= a[ls].r) add(ql, qr, val, ls);
        if(qr >= a[rs].l) add(ql, qr, val, rs);
        a[i] = a[ls]+a[rs];
    }
    node query(int ql, int qr, int i)
    {
        if(ql <= a[i].l and a[i].r <= qr)
            return a[i];
        push_down(i);
        node ans;
        if(qr <= a[ls].r) return query(ql, qr, ls);
        if(ql >= a[rs].l) return query(ql, qr, rs);
        return query(ql, qr, ls)+query(ql, qr, rs);
    }
}