Home

# 岛屿观测

# 题目描述

一个长度为 nn 的数列 aia_i 和 长度为 nn 的河床，第 ii 个数表示 位置 ii 的河床高度，对于一个高度 hh，河床高度小于 hh 的地方被淹没，大于等于 hh 的连通块个数为岛屿数量。
操作一： 将位置为 pospos 的河床高度修改为 hh。
询问二： 询问河水高度为 hh 时的岛屿数量。

# 解题思路

查询的意义是找到高度大于等于 hh, 两边的最小值比 hh 要小的点的数量，我们可以用两棵权值树状数组维护点数和，修改的时候先减去原来的值，再加上要修改的值即可。
还需要注意的一点是， a0a_0 要赋值为 00，又因为树状数组的下标只能是正整数，所以需要将高度整体加一。

# Code

#define Aniciry Meteorshower_Y
#include<iostream>
#include<cstdio>
#define lowbit(i) (i&-i)
using namespace std;
const int A = 5e5+1;
const int MAXN = 5e5+10;
int n, m, a[MAXN], p, h;
int tr1[MAXN], tr2[MAXN];
char op; int lstans;
auto query1(int x) -> int;
auto query2(int x) -> int;
auto add1(int x, int k) -> void;
auto add2(int x, int k) -> void;
int main()
{
    freopen("patrick.in", "r", stdin);
    freopen("patrick.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i += 1) cin >> a[i];
    for(int i = 1; i <= n; i += 1)
    {
        add1(a[i], 1);
        add2(min(a[i], a[i-1]), 1);
    }
    for(int i = 1; i <= m; i += 1)
    {
        cin >> op;
        if(op == 'Q')
        {
            cin >> h; h ^= lstans;
            lstans = query2(h-1)-query1(h-1);
            printf("%d\n", lstans);
        }
        else
        {
            cin >> p >> h;
            p ^= lstans; h ^= lstans;
            add1(a[p], -1);
            add2(min(a[p-1], a[p]), -1);
            add2(min(a[p], a[p+1]), -1);
            a[p] = h;
            add1(a[p], 1);
            add2(min(a[p-1], a[p]), 1);
            add2(min(a[p], a[p+1]), 1);
        }
    }
}
auto query1(int x) -> int
{
    int ans = 0; x += 1;
    for(int i = x; i; i -= lowbit(i))
        ans += tr1[i]; 
    return ans;
}
auto query2(int x) -> int
{
    int ans = 0; x += 1;
    for(int i = x; i; i -= lowbit(i))
        ans += tr2[i]; 
    return ans;
}
auto add1(int x, int k) -> void
{
    x += 1;
    for(int i = x; i <= A; i += lowbit(i))
        tr1[i] += k;
}
auto add2(int x, int k) -> void
{
    x += 1;
    for(int i = x; i <= A; i += lowbit(i))
        tr2[i] += k;
}

# 闯关顺序

# 题目描述

一款游戏有 nn 个关卡，第 ii 关难度为 pip_i，数列 pip_i 为 1 . . . n1~.~.~.~n 的一个排列。
定义每一个关卡 ii 的重要度为 di=min⁡k=1i(pk)d_i = \min_{k=1}^{i}(p_k). 玩家每次会选择重要度最低的那一关，若重要度相同则选择编号最小的那个。现在给出玩家的闯关顺序，询问字典序最小的排列 pip_i。

# 解题思路

根据题意我们可以知道，关卡的重要度一定是一个不上升的序列，对于每一段重要度相等的关卡，玩家又是从左到右按顺序刷的。所以题中所给出的过关顺序是若干个上升序列拼接而成的，我们只需找出每个上升子序列的开头，从左到右编号，然后再编号每一段剩下的。这样的结果字典序最小。

# Code

#define Aniciry Meteorshower_Y
#include<iostream>
#include<climits>
#include<cstdio>
using namespace std;
const int MAXN = 1e5+10;
int n, cnt, a[MAXN], p[MAXN];
int main()
{
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; i += 1)
        scanf("%d", &a[i]);
    a[0] = INT_MAX;
    for(int i = 1; i <= n; i += 1)
        if(a[i] < a[i-1]) p[a[i]] = ++cnt;
    for(int i = 1; i <= n; i += 1)
    {
        if(p[i]) printf("%d ", p[i]);
        else printf("%d ", ++cnt);
    }
    return 0;
}

# 简单算术

# 题目描述

给定一个只由非负整数和加减号组成的式子，需要我们添加 合法的 括号，使其运算结果最大。
括号可以嵌套。

# 解题思路

第一眼是区间 DP
一个常识小结论：多层嵌套的括号都可以拆成两层及以下括号嵌套的组合。
定义 fi,jf_{i,j} 为 第 ii 个数，有 jj 个没有匹配的左括号的最大值，O(n)O(n) 的 DP 可以接受。

# Code

#define Aniciry Meteorshowe_Y
#include<iostream>
#include<cstring>
#include<cstdio>
#define long long long
using namespace std;
const int MAXN = 2e5+10;
const long inf = 0x3f3f3f3f3f3f3f3f;
int T, n, cnt, a[MAXN], op[MAXN]; 
char ch; long f[MAXN][3]; 
auto solve() -> void;
auto prework() -> void;
auto max(long a, long b, long c) -> long;
signed main()
{
    freopen("arithmetic.in", "r", stdin);
    freopen("arithmetic.out", "w", stdout);
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}
auto solve() -> void
{
    prework();
    for(int i = 1; i <= n; i += 1)
    {
        if(op[i])
        {
            f[i][0] = f[i-1][0]-a[i];
            f[i][1] = max(f[i-1][0], f[i-1][1], f[i-1][2])-a[i];
            f[i][2] = max(f[i-1][1], f[i-1][2]) + a[i];
        }
        else
        {
            f[i][0] = max(f[i-1][0], f[i-1][1], f[i-1][2])+a[i];
            f[i][1] = max(f[i-1][1], f[i-1][2]) - a[i];
            f[i][2] = f[i-1][2] + a[i];
        }
    }
    printf("%lld\n", max(f[n][0], f[n][1], f[n][2]));
}
auto prework() -> void
{
    cin >> n >> a[1];
    for(int i = 2; i <= n; i += 1)
    {
        cin >> ch >> a[i];
        op[i] = (ch=='-');
    }
    f[0][0] = 0;
    f[0][1] = -inf;
    f[0][2] = -inf;
}
auto max(long a, long b, long c) -> long
{
    if(a >= b and a >= c) return a;
    if(b >= a and b >= c) return b;
    return c;
}

# 基因突变

# 题目描述

A 和 B 两种生物的基因由 l 和 t 组成。一开始基因只由一个 l ，A 生物的 l 可以突变成 lt 和 ltl ，B 生物的基因可以突变成 lt ， tl 和 ltl 。
现在给出一段基因（可能有其他基因），判断可不可能是 A 生物，可不可能是 B 生物。

# 解题思路

观察性质：

  1. 有其他基因 . . . . . . 啥也不是。
  2. t 开头，一定不是 B 生物。
  3. 有两个连续的 l ，啥也不是。

# Code

#define Aniciry Meteorshower_Y
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN = 1e6+10;
int T, n; char s[MAXN];
bool IA, IB, flag;
auto work() -> void;
int main()
{
    freopen("gene.in", "r", stdin);
    freopen("gene.out", "w", stdout);
    cin >> T; while(T--) work(); return 0;
}
auto work() -> void
{
    cin >> s; n = strlen(s);
    IA = true, IB = true; flag = false;
    if(s[0] == 't') IA = false;
    for(int i = 0; i < n; i += 1)
    {
        if(s[i] == 'l') flag = true;
        if(s[i] != 'l' and s[i] != 't') IA = IB = false;
        if(i != 0 and s[i] == 'l' and s[i-1] == 'l') IA = IB = false;
    }
    if(!flag) IA = IB = false;
    cout << IA << " " << IB << endl;
}

# 树点编号

# 题目描述

有一颗 nn 个点构成的树，给树上的点编号，aa 个点编号 1 . . . a1~.~.~.~a，作为白点，剩下 bb 个点编号 −1 . . . −b-1~.~.~.~-b，作为黑点，保证 a+b=na+b = n。

现有一个程序，会对这棵树进行 n−1n-1 次如下操作：

  1. 从黑色和白色中随机一个颜色，且需要保证目前图上仍然存在这种颜色的点。
  2. 如果随机到的是白色，程序将会删除编号绝对值最小的白点，并删除与之相连的所有边。
  3. 如果随机到的是黑色，程序将会删除编号绝对值最小的黑点，并删除与之相连的所有边。

请给这些点合适的编号，使得任何情况下，程序运行过程中都不会出现剩余未被删除的点不连通的情况。

# 解题思路

因为需要保证任意的删除顺序都保证图联通，所以白色黑色分别只能构成一个联通块。
我们直接在树上 dfs 一遍找出子树大小为 aa 或者 bb 的一棵子树，将其染成相应的颜色，剩下的部分染成另一个颜色即可，因为每次删除编号绝对值最小的，所以按后序遍历分配编号即可。

# Code

#define Aniciry Meteorshower_Y
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 1e5+10;
struct edge{
    int from, to;
    int next;
}e[MAXN<<1];
int n, a, b, u, v, rt;
int head[MAXN], cnt = 1;
int siz[MAXN], id[MAXN];
int sf, tp, cnta, cntb;
auto dfs(int x, int fa) -> void;
auto add_edge(int from, int to) -> void;
auto color(int x, int fa, int tp) -> void;
int main()
{
    freopen("tom.in", "r", stdin);
    freopen("tom.out", "w", stdout);
    scanf("%d%d%d", &n, &a, &b);
    for(int i = 1; i < n; i += 1)
    {
        scanf("%d%d", &u, &v);
        add_edge(u, v); 
        add_edge(v, u);
    }
    dfs(1, 0);
    if(!rt) return printf("-1"),0;
    else if(!a) color(rt, 0, 0);
    else if(!b) color(rt, 0, 1);
    else
    {
        color(sf, rt, tp);
        color(rt, sf, tp^1);
    }
    for(int i = 1; i <= n; i += 1)
        printf("%d\n", id[i]);
    return 0;
}
auto add_edge(int from, int to) -> void
{
    cnt += 1;
    e[cnt].from = from;
    e[cnt].to = to;
    e[cnt].next = head[from];
    head[from] = cnt;
}
auto dfs(int x, int fa) -> void
{
    int y; siz[x] = 1;
    for(int i = head[x]; i; i = e[i].next)
    {
        y = e[i].to; if(y == fa) continue;
        dfs(y, x); siz[x] += siz[y];
        if(siz[y] == a) rt = x, sf = y, tp = 0;
        if(siz[y] == b) rt = x, sf = y, tp = 1;
    }
    if(n-siz[x] == a) rt = x, sf = fa, tp = 0;
    if(n-siz[x] == b) rt = x, sf = fa, tp = 1;
}
auto color(int x, int fa, int tp) -> void
{
    for(int i = head[x], y; i; i = e[i].next)
    {
        y = e[i].to; if(y == fa) continue;
        color(y, x, tp);
    }
    id[x] = ++(tp?cntb:cnta);
    if(tp) id[x] = -id[x];
}
# 序列问题


# 题目描述


有一个长度为 nn 的序列 AA，删去一些树（或不删），将剩下的数按原顺序组成的新序列 BB。

若 BB 长度为 mm，则问 ∑i=1m[Bi=i]\sum\limits_{i=1}^{m} [B_i = i] 的最大值是多少。


# 解题思路


一个 O(n2)O(n^2) 的暴力算法，记 f(i,j)f(i,j) 为选到第 ii 个数，当前匹配到 jj 的最大匹配数。


下面考虑正解，设 f(i)f(i) 为将第 ii 个数作为 BB 序列最后一个数且造成 11 贡献的最大值。

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


    

  1. j<ij < i
    2. 

  2. Aj<AiA_j < A_i
    3. 

  3. Ai−Aj≤i−jA_i-A_j \le i-j
    
 当满足条件二、三 时，条件一肯定也已经满足了。所以我们将问题转化为将 AiA_i 排序后，Ai−iA_i - i 的最长不下降子序列的长度。
    4. 



# Code


#define Aniciry Meteorshower_Y
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 5e5+10;
struct node{
    int val, id;
}x[MAXN];
int n, ans, a[MAXN], f[MAXN], d[MAXN];
auto work1() -> void;
int main()
{
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; i += 1)
    {
        scanf("%d", &x[i].val);
        x[i].id = i;
    }
    sort(x+1, x+n+1, [](node a, node b){
        if(a.val != b.val) return a.val < b.val;
        return a.id > b.id;
    });
    for(int i = 1; i <= n; i += 1) a[i] = x[i].id-x[i].val;
    int len = 0;
    for(int i = 1; i <= n; i += 1)
    {
        if(a[i] < 0) continue;
        if(a[i] >= d[len]) d[++len] = a[i];
        else *upper_bound(d+1, d+len+1, a[i]) = a[i];
    }
    printf("%d", len);
    return 0;
}