3.3考试总结

A 区间的价值

题意：HDU 5696
给定序列\(a\)，分别求长度为\(1\sim n\)的区间最大价值。区间价值定义为区间内最大值乘最小值
题解：分治
暴力将\([l,r]\)内的最小值找出来，扩展到两边更新答案，再根据这个位置分治
复杂度:\(O(n\log n)\)

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T& x)
{
    x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
#define maxn 100005
#define ll long long
int a[maxn], n;
ll ans[maxn], tp[maxn];
void solve(int l, int r)
{
    if (l > r) return;
    int pos = l; ll max_val = 0;
    for (int i = l; i <= r; ++i)
        if (a[i] < a[pos]) pos = i;
    for (int i = 1; i <= r - l + 1; ++i) tp[i] = 0;
    for (int i = pos, maxval = a[pos]; i >= l; --i)
        maxval = max(maxval, a[i]), tp[pos - i + 1] = max(tp[pos - i + 1], 1ll * maxval * a[pos]);
    for (int i = pos, maxval = a[pos]; i <= r; ++i)
        maxval = max(maxval, a[i]), tp[i - pos + 1] = max(tp[i - pos + 1], 1ll * maxval * a[pos]);
    for (int i = 1; i <= r - l + 1; ++i)
    {
        max_val = max(max_val, tp[i]);
        ans[i] = max(ans[i], max_val);
    }
    solve(l, pos - 1), solve(pos + 1, r);
}
int main()
{
    read(n);
    for (int i = 1; i <= n; ++i) read(a[i]);
    solve(1, n);
    for (int i = 1; i <= n; ++i) printf("%lld\n", ans[i]);
    return 0;
}

B 树上的最远点对

题意：51nod 1766
\(n\)个点被\(n-1\)条边连接成了一颗树，给出\(a\sim b\)和\(c\sim d\)两个区间，表示点的标号请你求出两个区间内各选一点之间的最大距离，即你需要求出\(\max{dis(i,j)|a\leq i\leq b,c\leq j\leq d}\)
题解：线段树
显然一个区间内的直径由两个点组成，两个区间合并可以有6种方法（自己对自己2种，交叉6种）
用st表+欧拉序算lca（0202年居然还有出题人卡倍增和树剖lca），得出任意两点间的距离
用线段树维护每个区间的直径信息
复杂度:\(O(n\log n)\)

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T& x)
{
    x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
#define maxn 400005
struct Edge
{
    int fr, to, val;
}eg[maxn << 1];
int head[maxn], edgenum = 1;
inline void add(int fr, int to, int val)
{
    eg[++edgenum] = { head[fr],to,val };
    head[fr] = edgenum;
}
int dfn[maxn], pos[maxn], dfn_clock, dep[maxn], n, dis[maxn];
int st[maxn][20], lg[maxn];
void dfs(int rt)
{
    dfn[++dfn_clock] = rt;
    pos[rt] = dfn_clock;
    for (int i = head[rt]; i; i = eg[i].fr)
        if (eg[i].to != st[rt][0])
        {
            st[eg[i].to][0] = rt;
            dep[eg[i].to] = dep[rt] + 1;
            dis[eg[i].to] = dis[rt] + eg[i].val;
            dfs(eg[i].to);
            dfn[++dfn_clock] = rt;
        }
}
inline void make_st()
{
    for (int i = 1; i <= dfn_clock; ++i) st[i][0] = dfn[i];
    for (int i = 2; i <= dfn_clock; ++i) lg[i] = lg[i >> 1] + 1;
    for (int j = 1; j <= lg[dfn_clock]; ++j)
        for (int i = 1; i + (1 << j) - 1 <= dfn_clock; ++i)
        {
            if (dep[st[i][j - 1]] < dep[st[i + (1 << (j - 1))][j - 1]]) st[i][j] = st[i][j - 1];
            else st[i][j] = st[(i + (1 << (j - 1)))][j - 1];
        }
}
inline int getlca(int x, int y)
{
    x = pos[x], y = pos[y];
    if (x > y) swap(x, y);
    int tp = lg[y - x + 1];
    if (dep[st[x][tp]] < dep[st[y - (1 << tp) + 1][tp]]) return st[x][tp];
    return st[y - (1 << tp) + 1][tp];
}
inline int dist(int x, int y)
{
    return dis[x] + dis[y] - dis[getlca(x, y)] * 2;
}
struct SegmentTree
{
    struct Node
    {
        int l, r;
    }t[maxn << 2], tp;
#define ls rt<<1
#define rs rt<<1|1
    inline Node merge(Node l, Node r)
    {
        int p1 = l.l, p2 = l.r, p3 = r.l, p4 = r.r;
        int v1 = p1, v2 = p2, d0 = dist(v1, v2), d;
        if ((d = dist(p3, p4)) > d0) v1 = p3, v2 = p4, d0 = d;
        if ((d = dist(p1, p3)) > d0) v1 = p1, v2 = p3, d0 = d;
        if ((d = dist(p1, p4)) > d0) v1 = p1, v2 = p4, d0 = d;
        if ((d = dist(p2, p3)) > d0) v1 = p2, v2 = p3, d0 = d;
        if ((d = dist(p2, p4)) > d0) v1 = p2, v2 = p4, d0 = d;
        return { v1, v2 };
    }
    void build(int rt, int l, int r)
    {
        t[rt].l = l, t[rt].r = r;
        if (l == r)
        {
            t[rt].l = t[rt].r = l;
            return;
        }
        int mid = (l + r) >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        t[rt] = merge(t[ls], t[rs]);
    }
    Node query(int rt, int l, int r, int fr, int to)
    {
        if (fr == l && to == r) return t[rt];
        int mid = (l + r) >> 1;
        if (to <= mid) return query(ls, l, mid, fr, to);
        if (fr > mid) return query(rs, mid + 1, r, fr, to);
        return merge(query(ls, l, mid, fr, mid), query(rs, mid + 1, r, mid + 1, to));
    }
    inline friend Node Merge(Node l, Node r)
    {
        int p1 = l.l, p2 = l.r, p3 = r.l, p4 = r.r;
        int v1 = p1, v2 = p3, d0 = dist(v1, v2), d;
        if ((d = dist(p1, p4)) > d0) v1 = p1, v2 = p4, d0 = d;
        if ((d = dist(p2, p3)) > d0) v1 = p2, v2 = p3, d0 = d;
        if ((d = dist(p2, p4)) > d0) v1 = p2, v2 = p4, d0 = d;
        return { v1, v2 };
    }
}s;
int main()
{
    read(n);
    for (int i = 1, x, y, z; i < n; ++i)
        read(x), read(y), read(z), add(x, y, z), add(y, x, z);
    dfs(1);
    make_st();
    s.build(1, 1, n);
    int q; read(q);
    for (int i = 1, a, b, c, d; i <= q; ++i)
    {
        read(a), read(b), read(c), read(d);
        s.tp = Merge(s.query(1, 1, n, a, b), s.query(1, 1, n, c, d));
        printf("%d\n", dist(s.tp.l, s.tp.r));
    }
    return 0;
}

C 金牌赛事

题意：51nod 1611
题解：dp
设\(dp[i]\)为到了第\(i\)条路所能获得的最大收入
令\(s[i]\)为\(c[i]\)前缀和

• 如果不选则\(dp[i]=dp[i-1]\)
• 否则选了第\(j+1\)条路到第\(i\)条路\(dp[i]=dp[j]-(s[i]-s[j])+val\)

其中\(val\)为所有\(r\leq i,l\geq j\)的比赛奖励
所以用线段树维护\(dp[i]+s[i]+val\)的最大值，查询之后再减去\(s[i]\)即可
具体的维护方法就是先按\(r\)排序，对于一个\([l,r]\)的比赛，\([1,l-1]\)区间加\(p[i]\)（左端点大于等于\([1,l-1]\))
然后每次求出\(dp[i]\)时单点加
设\(dp[0]\)为所有路全修的收益（因为转移方程里\(j+1\not= 0\))
注意最大值还要和\(dp[0]\)取\(\max\)
复杂度:\(O(n\log n)\)

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T& x)
{
    x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
#define maxn 200005
#define ll long long
ll val[maxn];
struct SegmentTree
{
    struct Node
    {
        int l, r;
        ll val, lazy;
    }t[maxn << 2];
#define ls rt<<1
#define rs rt<<1|1
    inline void pushup(int rt)
    {
        t[rt].val = max(t[ls].val, t[rs].val);
    }
    inline void pushdown(int rt)
    {
        if (t[rt].lazy)
        {
            t[ls].val += t[rt].lazy;
            t[ls].lazy += t[rt].lazy;
            t[rs].val += t[rt].lazy;
            t[rs].lazy += t[rt].lazy;
            t[rt].lazy = 0;
        }
    }
    void build(int rt, int l, int r)
    {
        t[rt].l = l, t[rt].r = r;
        if (l == r)
        {
            t[rt].val = val[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        pushup(rt);
    }
    void update(int rt, int l, int r, int fr, int to, ll v)
    {
        if (fr <= l && to >= r)
        {
            t[rt].val += v, t[rt].lazy += v;
            return;
        }
        pushdown(rt);
        int mid = (l + r) >> 1;
        if (fr <= mid) update(ls, l, mid, fr, to, v);
        if (to > mid) update(rs, mid + 1, r, fr, to, v);
        pushup(rt);
    }
    ll query(int rt, int l, int r, int fr, int to)
    {
        if (fr <= l && to >= r) return t[rt].val;
        pushdown(rt);
        int mid = (l + r) >> 1; ll ans = 0;
        if (fr <= mid) ans = max(ans, query(ls, l, mid, fr, to));
        if (to > mid) ans = max(ans, query(rs, mid + 1, r, fr, to));
        return ans;
    }
}s;
struct Road
{
    int l, r; ll p;
    inline friend bool operator < (Road a, Road b)
    {
        if (a.r != b.r) return a.r < b.r;
        return a.l < b.l;
    }
}r[maxn];
ll dp[maxn];
int main()
{
    int n, m;
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(val[i]), val[i] += val[i - 1];
    for (int i = 1; i <= m; ++i) read(r[i].l), read(r[i].r), read(r[i].p);
    sort(r + 1, r + m + 1);
    s.build(1, 1, n);
    for (int i = 1, pos = 0; i <= n; ++i)
    {
        dp[i] = dp[i - 1];
        while (pos < m && r[pos + 1].r <= i)
        {
            ++pos;
            if (r[pos].l > 1) s.update(1, 1, n, 1, r[pos].l - 1, r[pos].p);
            dp[0] += r[pos].p;
        }
        if (i == 1) dp[i] = max(dp[i], dp[0] - val[i]);
        else dp[i] = max(dp[i], max(dp[0], s.query(1, 1, n, 1, i - 1)) - val[i]);
        s.update(1, 1, n, i, i, dp[i]);
    }
    printf("%lld\n", dp[n]);
    return 0;
}

D 迈克打电话

题意：CF547E
给定\(s[i]\)
\(q\)组询问，每组询问\(l,r,k\)表示求\(\sum_{i=l}^{r}{count(i,k)}\)，其中\(count(i,j)\)表示\(s[j]\)作为字串在\(s[i]\)中的出现次数
题解：这个不错
这个对trie树和这道题不错

#include<bits/stdc++.h>
using namespace std;

inline void read(int& x)
{
    x = 0; char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
}
#define maxn 200005
struct ChairmanTree
{
    int ls[maxn << 5], rs[maxn << 5], val[maxn << 5];
    int root[maxn], tot;
    void update(int& rt, int las, int l, int r, int pos)
    {
        rt = ++tot, ls[rt] = ls[las], rs[rt] = rs[las], val[rt] = val[las] + 1;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (pos <= mid) update(ls[rt], ls[rt], l, mid, pos);
        else update(rs[rt], rs[rt], mid + 1, r, pos);
    }
    int query(int rt, int las, int l, int r, int fr, int to)
    {
        if (fr <= l && to >= r) return val[las] - val[rt];
        int mid = (l + r) >> 1, ans = 0;
        if (fr <= mid) ans += query(ls[rt], ls[las], l, mid, fr, to);
        if (to > mid) ans += query(rs[rt], rs[las], mid + 1, r, fr, to);
        return ans;
    }
}CT;
struct FailTree
{
    struct Edge
    {
        int fr, to;
    }eg[maxn << 1];
    int head[maxn], edgenum, fail[maxn], dfn_l[maxn], dfn_r[maxn], dfn_clock;
    inline void add(int fr, int to)
    {
        eg[++edgenum] = { head[fr],to };
        head[fr] = edgenum;
    }
    void dfs(int rt)
    {
        dfn_l[rt] = ++dfn_clock;
        for (int i = head[rt]; i; i = eg[i].fr) dfs(eg[i].to);
        dfn_r[rt] = dfn_clock;
    }
    int son[maxn][26], fa[maxn], tot, pos[maxn];
    void insert(int id, char* s)
    {
        int rt = 0;
        for (int i = 0; s[i]; ++i)
        {
            if (!son[rt][s[i] - 'a']) son[rt][s[i] - 'a'] = ++tot;
            fa[son[rt][s[i] - 'a']] = rt;
            rt = son[rt][s[i] - 'a'];
        }
        pos[id] = rt;
    }
    void getfail()
    {
        queue<int> q;
        for (int i = 0; i < 26; ++i)
            if (son[0][i])
                q.push(son[0][i]), add(0, son[0][i]);
        while (!q.empty())
        {
            int tp = q.front();
            q.pop();
            for (int i = 0; i < 26; ++i)
            {
                if (son[tp][i])
                {
                    fail[son[tp][i]] = son[fail[tp]][i];
                    q.push(son[tp][i]);
                    add(fail[son[tp][i]], son[tp][i]);
                }
                else son[tp][i] = son[fail[tp]][i];
            }
        }
    }
}T;
int Root[maxn];
char s[maxn];
int main()
{
    int n, q;
    read(n), read(q);
    for (int i = 1; i <= n; ++i) scanf("%s", s), T.insert(i, s);
    T.getfail(); T.dfs(0);
    for (int i = 1, cur = 0; i <= n; ++i)
    {
        for (int j = T.pos[i]; j; j = T.fa[j])
            ++cur, CT.update(CT.root[cur], CT.root[cur - 1], 1, T.dfn_clock, T.dfn_l[j]);
        Root[i] = CT.root[cur];
    }
    for (int i = 1, l, r, k; i <= q; ++i)
    {
        read(l), read(r), read(k);
        printf("%d\n", CT.query(Root[l - 1], Root[r], 1, T.dfn_clock, T.dfn_l[T.pos[k]], T.dfn_r[T.pos[k]]));
    }
    return 0;
}