2021暑期hdu多校3

老鸽子了

A

吐槽

出题人的符号管理乱七八遭

E Didn't I Say to Make My Abilities Average in the Next Life?!

吐槽

二次元题目

看完题解感觉自己是...

题意

给定一个序列，\(q\)组询问，每次询问一个区间的所有子区间的最大值的和

题解

题解的两个做法感觉都有点复杂，看不太懂，自己写一个

离线从左到右扫描线，当我们扫到点\(r\)时，我们对于每个点\(l\)，维护\(max_r[l]\)表示\([l,r]\)中的最大值，那么\(\sum max_i[l]\)将表示\([l,l], [l,l+1],...,[l,r]\)的答案的和，从而\(\sum_{l \leq L \leq r} \sum max_i[L]\)将是答案

我们可以用线段树来做到这一点，理清之后还挺好写的

#include <bits/stdc++.h>
using namespace std;
    
#define gc getchar
inline int read() {
    int p = 0, w = 1; char c = gc();
    while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); }
    while(c >= '0' && c <= '9') { p = p * 10 + c - '0'; c = gc(); }
    return p * w;
}

#define rep(io, st, ed) for(int io = st; io <= ed; io ++)

const int mod = 1e9 + 7;
const int sid = 1e6 + 5;
const int inf = 1e9 + 5;

inline void inc(int &a, int b) { a += b; if(a >= mod) a -= mod; }
inline void dec(int &a, int b) { a -= b; if(a < 0) a += mod; }
inline int Inc(int a, int b) { return (a + b >= mod) ? a + b - mod : a + b; }
inline int Dec(int a, int b) { return (a - b < 0) ? a - b + mod : a - b; }
inline int mul(int a, int b) { return 1ll * a * b % mod; }
inline int fp(int a, int k) { 
    int ret = 1; 
    while(k) { 
        if(k & 1) ret = mul(ret, a); 
        a = mul(a, a); k >>= 1; 
    }
    return ret;
}

struct query {
    int l, id;
    query() {}
    query(int _l, int _id) : l(_l), id(_id) {}
} ;
vector <query> Q[sid];

int n, m;
int a[sid],  ans[sid];
int lst_time[sid], sumtag[sid], sum[sid];
int nowv[sid], presum[sid], pret[sid], newt[sid];

#define ls (o << 1)
#define rs (o << 1 | 1)
void build(int o, int l, int r) {
    lst_time[o] = sumtag[o] = sum[o] = 0;
    nowv[o] = presum[o] = pret[o] = newt[o] = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

void down(int o, int l, int r, int nv, int ps, int pt, int nt) {
    inc(sum[o], 1ll * sumtag[o] * (pt - lst_time[o]) % mod);
    inc(sum[o], 1ll * ps * (r - l + 1) % mod);
    if(!nowv[o])  // 先前没有标记
        nowv[o] = nv, presum[o] = ps, pret[o] = pt, newt[o] = nt; 
    else {
        inc(presum[o], ps);
        inc(presum[o], 1ll * nowv[o] * (pt - newt[o]) % mod);
        newt[o] = nt; nowv[o] = nv;
    }
    lst_time[o] = nt; sumtag[o] = mul(r - l + 1, nv);
}

void pushdown(int o, int l, int r) {
    if(!nowv[o]) return;
    int mid = (l + r) >> 1;
    down(ls, l, mid, nowv[o], presum[o], pret[o], newt[o]);
    down(rs, mid + 1, r, nowv[o], presum[o], pret[o], newt[o]);
    nowv[o] = 0; presum[o] = 0;
}

void pushup(int o, int l, int r, int t) {
    inc(sum[o], 1ll * (t - lst_time[o]) * sumtag[o] % mod);
    sumtag[o] = Inc(sumtag[ls], sumtag[rs]);
    lst_time[o] = t;
}

void mdf(int o, int l, int r, int ml, int mr, int v, int t) {
    if(ml > r || mr < l) return;
    if(ml <= l && mr >= r) { down(o, l, r, v, 0, t, t); return; }
    int mid = (l + r) >> 1;
    pushdown(o, l, r);
    mdf(ls, l, mid, ml, mr, v, t);
    mdf(rs, mid + 1, r, ml, mr, v, t);
    pushup(o, l, r, t);
}

int qry(int o, int l, int r, int ml, int mr, int t) {
    if(ml > r || mr < l) return 0;
    if(ml <= l && mr >= r) return Inc(sum[o], 1ll * sumtag[o] * (t-lst_time[o]) % mod);
    int mid = (l + r) >> 1;
    pushdown(o, l, r);
    return Inc(qry(ls, l, mid, ml, mr, t), qry(rs, mid + 1, r, ml, mr, t));
}

int st[sid], top;
void segment_work(int opt = 0) {
    a[0] = -inf; top = 0;
    build(1, 1, n);
    rep(r, 1, n) {
        while(top && a[r] >= a[ st[top] ]) top --;
        mdf(1, 1, n, st[top] + 1, r, (a[r] + mod) % mod, r - 1);
        st[++ top] = r;
        for(auto x : Q[r]) {
            int l = x.l, id = x.id;
            if(!opt) inc(ans[id], qry(1, 1, n, l, r, r));
            else dec(ans[id], qry(1, 1, n, l, r, r));
            if(opt) {
                int len = r - l + 1;
                ans[id] = mul(ans[id], fp(1ll * len * (len + 1) % mod, mod - 2));
            }
        }
    }
}

void solve() {
    n = read(); m = read();
    rep(i, 1, n) a[i] = read(), Q[i].clear();
    rep(i, 1, m) {
        int l = read(), r = read();
        Q[r].push_back( query(l, i) );
        ans[i] = 0;
    }
    segment_work();
    rep(i, 1, n) a[i] = -a[i];
    segment_work(1);
    rep(i, 1, m) printf("%d\n", ans[i]);
}

int main() {
    int T = read();
    while(T --) solve();
    return 0;
}

G Increasing Subsequence

题意

给定一个排列，求极大上升子序列的数量

题解

\(n^2\)做法不难想到，设\(f[i]\)表示\(a_1,...,a_i\)中的极大上升子序列的数量，考虑转移，\(j\)能转移到\(i\)，当且仅当\(a_j < a_i\)，并且区间\([j+1, i-1]\)中，没有在\([a_j,a_i]\)中的数

抽象一下，也即能转移到\(f[i]\)的\(j\)将构成一个满足下标\(j<i\)，权值\(a_j < a_i\)的数构成的单调栈

我们可以考虑用分治解决下标这一维，对于\([l, r]\)，考虑\([l, mid]\)对\([mid + 1, r]\)的贡献

由于分治，\([mid + 1, r]\)中的元素不存在下标上的影响，对权值上的影响，只需要预处理出\([mid + 1, r]\)中每个数左边比它小的最大数即可

对于\([l, mid]\)而言，我们按权值大小来建立单调栈，右边相应的按照权值在单调栈上二分即可