A. Telephone Number

找到第一个 8

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;

#define mp make_pair

void solve() {
    int n, p = -1;
    string s;
    cin >> n >> s;
    for (int i = 0; p == -1 && i < n; i++)
        if (s[i] == '8') p = i;
    if( p!= -1 && p + 10 < n ) cout << "YES\n";
    else cout << "NO\n";
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    for (; t; t--)
        solve();
    return 0;
}

B. Lost Numbers

问? 1 2、? 1 3，暴力枚举计算\(a_1,a_2,a_3\)

问? 4 5、? 4 6，暴力枚举计算\(a_4,a_5,a_6\)

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;

#define mp make_pair

int32_t main() {
    vector<int> a = {4, 8, 15, 16, 23, 42};
    vector<int> res;
    int x, y;
    cout << "? 1 2" << endl;
    fflush(stdout);
    cin >> x;
    cout << "? 1 3" << endl;
    cin >> y;
    fflush(stdout);
    int f = 0;
    for (auto i: a) {
        for (auto j: a) {
            for (auto k: a) {
                if ( i != j && i != k && j != k && i * j == x && i * k == y ){
                    res.push_back(i);
                    res.push_back(j);
                    res.push_back(k);
                    f = 1;
                    break;
                }
            }
            if( f == 1 ) break;
        }
        if( f == 1 ) break;
    }

    cout << "? 4 5" << endl;
    fflush(stdout);
    cin >> x;
    cout << "? 4 6" << endl;
    cin >> y;
    fflush(stdout);
    f = 0;
    for (auto i: a) {
        for (auto j: a) {
            for (auto k: a) {
                if ( i != j && i != k && j != k && i * j == x && i * k == y ){
                    res.push_back(i);
                    res.push_back(j);
                    res.push_back(k);
                    f = 1;
                    break;
                }
            }
            if( f == 1 ) break;
        }
        if( f == 1 ) break;
    }
    cout << "!";
    for( auto i : res )
        cout << " " << i;
    cout << endl;
    fflush(stdout);

    return 0;
}

C. News Distribution

并查集按秩合并

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;

#define mp make_pair

class dsu{
private:
    vector<int>fa;
public:
    dsu(int n){
        fa = vector<int>( n + 1 , -1);
    }
    int getfa( int x ){
        if( fa[x] < 0 ) return x;
        return fa[x] = getfa( fa[x] );
    }
    void merge( int x , int y ){
        x = getfa(x) , y = getfa(y);
        if( x == y ) return ;
        if( x > y ) swap( x , y );
        fa[x] += fa[y] , fa[y] = x;
    }
    int size( int x ){
        x = getfa(x);
        return -1 * fa[x];
    }
};

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n , m;
    cin >> n >> m;
    dsu d(n);
    for( int k , x , y ; m ; m -- ){
        cin >> k;
        if( k == 0 ) continue;
        cin >> x;
        for( int i = 2 ; i <= k ; i ++ )
            cin >> y , d.merge( x , y );
    }
    for( int i = 1 ; i <= n ; i ++ )
        cout << d.size(i) << " ";
    return 0;
}

D. Bicolored RBS

同时维护两个队列，然后贪心就好了

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;

#define mp make_pair

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n , r = 0 , b = 0;
    string s;
    cin >> n >> s;
    for( auto i : s ){
        if( i == '(' ){
            if( r <= b ) r ++ , cout << "0";
            else b ++ , cout << "1";
        }else{
            if( r >= b ) r -- , cout << "0";
            else b -- , cout << "1";
        }
    }
    return 0;
}

E. Range Deleting

首先可以很轻松的得到\(f(l,r)\)满足，\(f(l,r+1)\)也满足。

用pos数组统计每个数出现的位置，即\(pos[i].front(),pos[i].back()\)就是数字\(i\)最早最晚出现位置。

统计出前缀的最大值\(prefMax\)。

计算出\(p\)，表示保留\([p,x]\)中的数的情况下，序列满足有序的最小值。

我们来枚举\(l\)，计算出最小\(r\)是的\(f(l,r)\)满足，则对于\(l\)的贡献就是\(x-r+1\)。

假设可以保证保留\([1,l-1]\)中的数，序列有序的情况下，\(last\)是\([1,l-1]\)中的数最后出现的位置。则\(r\)应满足以下三个条件：

\(r >= l\)
\(r >= p-1\)
\(r >= prefMax[last]\)

三个条件取最大值就可以得到最小的\(r\)

现在，考虑如何判断保留\([1,l-1]\)中的数，序列有序的情况下\(l\)能否扩展到\(l+1\)。条件就是判断\(pos[l].front()>last\)是否成立，成立的话就可以扩展，并且更新\(last\)。

这样从\(1\)开始枚举\(l\)即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), prefMax(n + 1);
    vector<vector<int>> pos(m + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i], pos[a[i]].push_back(i);
    prefMax[1] = a[1];
    for (int i = 2; i <= n; i++)
        prefMax[i] = max(prefMax[i - 1], a[i]);

    int p = 1, last = INT_MAX;
    for (int i = m; i >= 1; i--) {
        if (pos[i].empty()) {
            p = i;
            continue;
        }
        if (pos[i].back() > last) break;
        p = i, last = pos[i].front();
    }

    int res = 0;
    last = -1;
    for (int l = 1; l <= m; l++) {
        int r = max(l, p - 1);
        if (last != -1) r = max(r, prefMax[last]);
        res += m - r + 1;
        if (!pos[l].empty()) {
            if (pos[l].front() < last) break;
            last = pos[l].back();
        }
    }
    cout << res << "\n";
    return 0;
}

F. Scalar Queries

现在很常见的一种思路，计算区间就一定要枚举区间，所以我们考虑区间中每一个点的贡献。

首先区间\([l,r]\)的贡献可以转化为\(a_i\times (low+1)\)，\(low\)是区间中小于\(a_i\)的数量。

对于\(a_i\)本身包含他的区间有\(i\times(n-i+1)\)，那么\(a_i\)对于答案的贡献就是

\[\sum a_i\times(low+1)=a_i\times (i\times(n-i+1)+a_i+\sum low) \]

\(\sum low\)就是所有区间中小于\(a_i\)的数字出现的次数之和

如果\(a_j<a_i,j<i\)，数字\(a_j\)出现的次数就是\(j\times (n-i+1)\)

如果\(a_j<a_i,j>i\)，数字\(a_j\)出现的次数就是\(i\times(n-j+1)\)

把上面两个加起来就是\(low\)，求出\(low\)就可以\(O(1)\)的计算出\(a_i\)的贡献

\[\sum j\times(n-i+1)=(n-i+1)\times\sum j\\ \sum i\times (n-j+1) = i\times (cnt\times(n+1)-\sum j) \]

\(\sum j\) 是满足条件的\(j\)的和，\(cnt\)是满足条件\(j\)的数量。

记录\((a_i,i)\)按照\(a_i\)从小到大排序，然后枚举\(i\)，然后用两个树状数组维护下标之和、下标数量即可。

复杂度\(O(n\log n)\)

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9 + 7;

struct BinaryIndexedTree {
#define lowbit(x) ( x & -x )
    int n;
    vector<int> b;

    BinaryIndexedTree(int n) : n(n), b(n + 1, 0) {};

    void add(int i, int y) {
        for (; i <= n; i += lowbit(i)) b[i] = (b[i] + y + mod) % mod;
        return;
    }

    int calc(int i) {
        int sum = 0;
        for (; i; i -= lowbit(i)) sum = (sum + b[i] + mod) % mod;
        return sum;
    }

    int calc(int l, int r) {
        if (l > r) return 0ll;
        return (calc(r) - calc(l - 1) + mod) % mod;
    }
};

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i].first, a[i].second = i + 1;
    sort(a.begin(), a.end());
    BinaryIndexedTree indexCnt(n), indexSum(n);
    int res = 0;
    for (auto [x, index]: a) {
        int tmp = index * (n - index + 1) % mod;
        tmp = (tmp + (n - index + 1) * indexSum.calc(index - 1) % mod) % mod;
        tmp = (tmp + index * (indexCnt.calc(index + 1, n) * (n + 1) % mod - indexSum.calc(index + 1, n) + mod)) % mod;
        res = (res + tmp * x % mod) % mod;
        indexCnt.add(index, 1), indexSum.add(index, index);
    }
    cout << res << "\n";
    return 0;
}