T1 好数

设ctz(x)为x二进制下末尾0的个数，如ctz(1001000)=3。
设ppc(x)为x二进制下1的个数，如ppc(1001000)=2。
定义一个数是好数，当且仅当ctz(x)=ppc(x)。
给定Q，有Q次询问，每次给出区间[l,r]，你需要求出[l,r]中任意一个好数，或判断无输出-1。

考虑逐位模拟，我们从大到小考虑，如果 \(x\) 非法时如何操作。

• \(\operatorname{ctz}(x) > \operatorname{ppc}(x)\) 时，我们将 \(x\) 减去 \(1\)，再去考虑新的数。

• \(\operatorname{ctz}(x) < \operatorname{ppc}(x)\) 时，我们将 \(x\) 减去 \(\operatorname{lowbit}(x)\)，此时一定是一个最接近 \(x\) 的可能的合法操作，减少一个 \(1\) 的同时增加一个 \(0\)，因为对于 \((x -\operatorname{lowbit}(x), x]\) 中一定不存在合法的 \(x\)，否则 \(1\) 比末尾 \(0\) 多。

时间复杂度 \(O(Q\log{n} \sim Q\log^2{n})\)，但上界是远远达不到的。

参考代码

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

int ctz(ull x)
{
    x = x & -x;
    int cnt = 0;
    while (x) x >>= 1, cnt ++ ;
    return cnt - 1;
}

void solve()
{
    ull l, r;
    cin >> l >> r;
    while (r >= l)
    {
        if (__builtin_popcount(r) < ctz(r)) r -- ;
        else if (__builtin_popcount(r) > ctz(r)) r -= r & -r;
        else return cout << r << "\n", void();
    }
    cout << "-1\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int T;
    cin >> T;
    while (T -- ) solve();
    return 0;
}

T2 排序

今天是YQH的生日，她得到了一个长度为n排列a1,a2,...,an 作为生日礼物，这 个排列包含了 1,2,...,n 里每个元素恰好一次。
由于YQH十分喜欢升序，于是她打算把这个排列进行排序使得最后排列升序。
但是她发现一个问题：她太笨了，不会各种O(nlogn)的排序算法，于是她退而求次，准备使用O(n) 的“斯大林排序”。
斯大林排序是这样一个过程：
假设我们要排序的序列是a1,a2,...,an，那么维护一个初始为空的栈，然后从 1 到 n 枚 举i：
• 假如ai 比栈顶严格大或者栈为空，那么把ai加入栈中。
• 否则，此刻有ai小于等于栈顶，那么什么都不干。
最后把栈里的元素从底到顶输出作为结果。
容易发现，这样我们获得就是原排列的一个上升子序列，但是可能会失去太多的元 素，比如假如我们要排序[5,1,2,3,4]，我们最后只得到了 [5]。
于是YQH进行了改进，现在排序变成这样一个过程：
假设我们要排序的序列是a1,a2,...,an，那么维护一个初始为空的栈，然后从 1 到 n 枚举 i：
• 假如 ai 比栈顶严格大或者栈为空，那么把ai加入栈中。
• 否则，此刻有 ai 小于等于栈顶，那么有两种选择：把栈顶弹出并把ai加入栈中， 或什么都不干。
注意，你需要保证任意时刻，栈中的元素从底到顶严格单调上升。
最后把栈里的元素从底到顶输出作为结果。
比如现在我们要排序[5,1,2,3,4]，栈的变化是 [] → [5] → [1] → [1,2] → [1,2,3] → [1,2,3,4]。
容易发现，最后栈的大小与排序时进行的选择有关。YQH当然希望最后栈越大越 好，于是她找到了你，希望你对于她给出的排列，求出最后栈大小的最大值。

容易发现，对于一个位置的 \(a_i\)，所有后续连续的 \(a_j < a_i(j > i)\)，我们是可以进行删除或替换当前 \(a_i\) 操作的，记 \(ne_i = \min(\{j \mid a_j > a_i, j > i\})\)，但 \(dp_i\) 对 \(a_j > a_i, j \in [ne_i, ne_{ne_i})\) 的 \(dp_j\) 均有贡献，合法的 \(j\) 是离散的，这并不好办到，因此我们考虑从值域入手。

设 \(dp_i\) 表示以 \(i\) 结尾的栈并且栈不弹出 \(i\) 的最大长度，从 \(1 \sim n\) 枚举考虑能否对答案进行贡献，由上面的定义可知，对 \(i\) 的合法转移是删除 \(i\) 后比 \(i\) 小区间段，即 \(dp_j = \max(dp_j, dp_i + 1), j \in [ne_i, ne_{ne_i})\)，我们用线段树对区间段进行赋值即可。

时间复杂度 \(O(n\log{n})\)。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n;
int a[N], p[N], ne[N], dp[N];
struct Node
{
    int l, r, sum;
}tr[N << 2];

void build(int u, int l, int r)
{
    tr[u] = {l, r, -100000};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum = max(tr[u].sum, d), void();
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, r, d);
    if (r > mid) modify(u << 1 | 1, l, r, d);
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    int res = tr[u].sum;
    if (l <= mid) res = max(res, query(u << 1, l, r));
    if (r > mid) res = max(res, query(u << 1 | 1, l, r));
    return res;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i], p[a[i]] = i;
    ne[n + 1] = a[n + 1] = n + 1;
    for (int i = n; i >= 0; i -- )
    {
        ne[i] = i + 1;
        while (a[ne[i]] < a[i]) ne[i] = ne[ne[i]];
    }
    build(1, 1, n);
    int ans = 0;
    for (int i = 0; i <= n; i ++ )
    {
        int u = p[i];
        int l = ne[u], r = ne[l] - 1;
        if (u) dp[u] = query(1, u, u) + 1;
        if (l <= r) modify(1, l, r, dp[u]);
        ans = max(ans, dp[u]);
    }
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int T = 1;
    while (T -- ) solve();
    return 0;
}