专栏文章

MX Day 17

OOIer_ACMer
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minbqmad
此快照首次捕获于
2025/12/01 23:48
3 个月前
此快照最后确认于
2025/12/01 23:48
3 个月前
查看原文

T1：

1762591211529.png

思路：

这道题肥肠EASY，首先，我们可以将操作倒着做，当然你正着做用线段树乱搞也挺牛逼。
之后，我们就可将这个问题转化为并查集维护了，因为连续段最大值可以用并查集维护，肥肠简单，只用在每次添加时将数的大小进行匹配，父节点为权值大的那一头，否则就成儿子。
如果两边都没数，就将这个数当成一个并查集，自己算自己的答案，直接加然后异或就可以了。
至于将一个数合并到另外一个集合中去，也差不多，首先我们要确保它存在，之后我们先将集合最大值减去，如果合并后发现还是集合的最大值大一些，那么再加回来，否则就是加上新增的这个数了。
最后，如果是两个并查集夹着新增的数合并，就有点麻烦，首先，我们要将两个大集合的答案减去，之后再是合并，先合并左边，同时别忘了更新新的集合每一个点的fa数组，这个很容易错，之后重复一次，算出最终的答案，加上然后异或，就OK了。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n, m;
int fa[2000009];
int a[2000009];
int del[2000009];
bool exi[2000009];
void init()
{
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
}
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
signed main()
{
    freopen("spring.in", "r", stdin);
    freopen("spring.out", "w", stdout);
    int _ = read();
    n = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        exi[i] = 1;
    }
    for (int i = 1; i < n; i++)
    {
        del[i] = read();
        exi[del[i]] = 0;
    }
    init();
    int ans = 0, sum = 0, lstsum = 0;
    for (int i = 1; i <= n; i++)
    {
        if (exi[i])
        {
            lstsum = a[i];
            break;
        }
    }
    ans = lstsum;
    // cout << "start ans=" << ans << endl;
    for (int i = n - 1; i >= 2; i--)
    {
        sum = lstsum;
        exi[del[i]] = 1;
        int u = del[i];
        if (exi[u - 1] == 0 && exi[u + 1] == 0)
        {
            sum += a[u];
            lstsum = sum;
            ans ^= sum;
            // for (int i = 1; i <= n; i++)
            // {
            //     cout << find(i) << " ";
            // }
            // cout << "   sum=" << sum << endl;
            continue;
        }
        if (exi[u - 1] && exi[u + 1])
        {
            int f1 = find(u - 1);
            int f2 = find(u);
            int f3 = find(u + 1);
            sum -= (a[f1] + a[f3]);
            // cout << "sum=" << sum << " f1=" << f1 << " f2=" << f2 << " f3=" << f3 << endl;
            if (a[f1] >= a[f2])
            {
                fa[f2] = f1;
            }
            else
            {
                fa[f1] = f2;
            }
            int g2 = find(u), g3 = find(u + 1);
            if (a[g2] >= a[g3])
            {
                fa[g3] = g2;
            }
            else
            {
                fa[g2] = g3;
            }
            sum += a[find(u)];
            lstsum = sum;
            ans ^= sum;
            // for (int i = 1; i <= n; i++)
            // {
            //     cout << find(i) << " ";
            // }
            // cout << "   sum=" << sum << endl;
            continue;
        }
        if (exi[u - 1])
        {
            // cout << "1\n";
            int fu = find(u);
            int fv = find(u - 1);
            if (a[fu] >= a[fv])
            {
                sum -= a[fv];
                sum += a[u];
                fa[fv] = fu;
            }
            else
            {
                fa[fu] = fv;
            }
        }
        if (exi[u + 1])
        {
            // cout << "2\n";
            int fu = find(u);
            int fv = find(u + 1);
            if (a[fu] >= a[fv])
            {
                sum -= a[fv];
                sum += a[fu];
                fa[fv] = fu;
            }
            else
            {
                fa[fu] = fv;
            }
        }
        // cout << sum << endl;
        lstsum = sum;
        ans ^= sum;
        // for (int i = 1; i <= n; i++)
        // {
        //     cout << find(i) << " ";
        // }
        // cout << "   sum=" << sum << endl;
    }
    cout << ans << endl;
    return 0;
}
/*
0
7 
7 1 4 5 1 4 1 
6 3 7 5 4 2
*/

T2:

1762593172505.png

思路：

首先，我们要求的是每个时刻有多少个函数的结果是a的倍数，那么一开始我们先从暴力考虑。
我们有两种暴力方式：
  1. 一种很好想，就是枚举每一个函数和每一个时刻，进一步的，我们可以直接枚举斜率，因为斜率的大小对应着我们的时间最多只能到什么时候，因为对于斜率k，时间到了A/k + 1就会超过我们的A，之后我们再来对每一个ai加倍，寻找对应的B，因为ai随机分布，所以这个暴力还算可以。
  2. 还有一种，因为上面这一种对于ai很小的情况就炸了，所以我们另辟蹊径，我们再以“反动分子”ai为枚举上限，找出最大的ai，定义其为maxn，将其变为我们的上限，再来考虑一下；首先，我们可以枚举在1~maxn之间所有的除数p，因为我们可以用一个数组很方便记录那些对一个数取模等于一个余数的数的个数，所以我们每次统计那些对p取模余数等于(（-kt）%p)的b求个数，就可以了。

Code:

CPP
// #include <bits/stdc++.h>
// using namespace std;
// #define int long long
// inline int read() {
//     int x = 0, f = 1; char ch = getchar();
//     while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
//     while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
//     return x * f;
// }
// int T, n, A, _, w[3000009];
// int k[3000009], b[3000009], a[3000009];
// unordered_multiset<int> s[300009];
// bool vis[300009];
// int ans[300009];
// signed main()
// {
//     freopen("summer.in", "r", stdin);
//     freopen("summer.out", "w", stdout);
//     _ = read();
//     T = read();
//     n = read();
//     A = read();
//     vector<int> K;
//     for (int i = 1; i <= n; i++)
//     {
//         k[i] = read();
//         b[i] = read();
//         s[k[i]].insert(b[i]);
//         if (vis[k[i]])
//         {
//             continue;
//         }
//         vis[k[i]] = 1;
//         K.push_back(k[i]);
//     }
//     for (int i = 1; i <= T; i++)
//     {
//         a[i] = read();
//     }
//     // for (int i = 0; i < K.size(); i++)
//     // {
//     //     cout << "k=" << K[i] << "\n";
//     // }
//     // cout << endl;
//     for (int i = 0; i < K.size(); i++){
//         int k = K[i];
//         // cout << "k=" << k << "\n";
//         for (int t = 1; t <= A / k + 1 && t <= T; t++)
//         {
//             for (int l = 1; l <= A / a[t]; l++)
//             {
//                 // cout << "t=" << t << "  " << "l=" << l << "  need a=" << a[t] << "  k=" << k << "  check=" << l * a[t] - k * t << "\n";
//                 // cout << "l=" << l << "  " << s[k].count(l * a[t] - k * t) << "\n";
//                 ans[t] += s[k].count(l * a[t] - k * t);
//             }
//             // cout << endl;
//         }
//         // cout << "***\n" << "i=" << i << "  " << "k=" << k << "\n";
//     }
//     // cout << "***\n";
//     for (int i = 1; i <= T; i++)
//     {
//         printf("%lld\n", ans[i]);
//     }
//     return 0;
// } 56
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int _, n;
int cnt[6009][6009];
const int FZ = 1072;
int k[3000009], b[3000009];
vector<int> K[3000009];
int sumb[3000009];
void add(int x, int w)
{
    // cout << "now x=" << x << "  w=" << w << endl;
    for (int i =1; i < FZ; i++)
    {
        cnt[i][x % i] += w;
    }
    // cout << endl;
    sumb[x] += w;
}
int ans[3000009];
int a[3000009];
int T, A;
// vector<int >
signed main()
{
    freopen("summer.in", "r", stdin);
    freopen("summer.out", "w", stdout);
    _ = read();
    T = read();
    n = read();
    A = read();
    for (int i = 1; i <= n; i++)
    {
        k[i] = read();
        b[i] = read();
        K[k[i]].push_back(b[i]);
        // cout << "k=" << k[i] << "  b=" << b[i] << endl;
    }
    // cout << endl;
    for (int i = 1; i <= T; i++)
    {
        a[i] = read();
    }
    for (int k = 1; k <= A; k++)
    {
        if (K[k].empty())
        {
            continue;
        }
        sort(K[k].begin(), K[k].end());
        // cout << "k=" << k << endl << "siz=" << K[k].size() << endl;
        for (int i = 0; i < K[k].size(); i++)
        {
            add(K[k][i], 1);
            // cout << "b=" << K[k][i] << ' ';
        }
        // cout << endl;
        int mx = min(T, A / k);
        for (int t = 1; t <= mx; t++)
        {
            while (K[k].size() && K[k].back() + k * t > A)
            {
                add(K[k].back(), -1);
                K[k].pop_back();
            }
            if (a[t] < FZ)
            {
                int r = a[t] - k * t % a[t];
                if (r == a[t])
                {
                    r = 0;
                }
                ans[t] += cnt[a[t]][r];
            }
            else
            {
                for (int bs = a[t]; bs <= A; bs += a[t])
                {
                    if (bs >= k * t)
                    {
                        ans[t] += sumb[bs - k * t];
                    }
                }
            }
        }
        while (K[k].size())
        {
            add(K[k].back(), -1);
            K[k].pop_back();
        }
    }
    for (int i = 1; i <= T; i++)
    {
        printf("%lld\n", ans[i]);
    }
    return 0;
}

T3：

1762599136000.png

思路：

首先，我们又遇到了统计不限左右端点区间贡献的题目，那么，OK，肯定要固定一端，这是肯定的，固定套路。
我们可以先固定右端点R（当然固定左端点L也可以），考虑以R为右端点，怎么快速计算贡献；我们分三个情况，一个是两次都出现在R左边，一种是只有一个出现在R左边，还有一种是左边一次都没有，OK，那好办，情况一肯定只能考虑两者靠右的那个，毕竟靠左的话已经出现两次了，就无法算贡献；至于情况二……有点复杂，我们肯定是将情况二中最靠右边的统计答案，毕竟再往外拓展到第二个肯定不会只有一个数出现一次了。
这时我们发现一个问题，就是情况一和情况二其实有重复的，情况一可以当成将左端点固定来找左端点右边出现一次的数中最靠L的那个位子（还有一点，我们在枚举），因此我们在一次枚举中只考虑一种情况，要么2，要么是翻转后的2。
寻找最靠右的用单调栈就可以实现，至于当其再次出现时，直接用数组记录出现次数再次排掉就可以了，至于怎么找有多少个L与目前的R组成一个完整的数段，那也好办，还记得集合哈希吗，对于这种情况我们可以发现满足要求的字段哈希，也叫异或值就等于那个唯一出现的数对应的哈希值，毕竟其它的都因为出现两次被削掉了，那好，我们每次只用利用前缀和的思想，用当前的哈希值异或上[1, R]的哈希值（因为异或的逆运算也是异或，就像A异或B等于C，那么C异或B等于A或者异或A等于B一样），快速找到那些相当于[1, L]区间哈希值与[1, R]哈希值异或的结果等于当前要求只出现一次的数的哈希值的[1, L]区间个数，就可以了。
简而言之，最后一句话，就是设[1, L]区间哈希值为B，[1, R]的哈希值为A，此时这个数的哈希值为C，相当于找到有多少个B和A异或等于C，寻找的方式就是利用逆运算会总共多少个B等于C异或A。

Code：

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
mt19937_64 rnd(time(0));
int n;
int _;
int a[2000099];
short cx[2000099];
int w[2000099];
void init()
{
    for (int i = 1; i <= n; i++)
    {
        w[i] = rnd();
    }
}
int ans[2000099], pre[2000099];
void solve()
{
    // vector<int> pre;
    stack<int> sta;
    unordered_map<int, int> cnt;
    pre[0] = 0;
    // cout << "?\n";
    for (int i = 1; i <= n + 2; i++)
    {
        cx[i] = 0;
    }
    // cout << "go\n";
    cnt[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        cx[a[i]]++;
        pre[i] = pre[i - 1] ^ w[a[i]];
        sta.push(i);
        while (sta.size() && cx[a[sta.top()]] == 2)
        {
            sta.pop();
        }
        if (sta.size())
        {
            int x = sta.top();
            ans[x] += cnt[w[a[x]] ^ pre[i]];
            // cout << "x=" << x << " add=" << cnt[w[a[x]] ^ pre[i]] << endl;
        }
        cnt[pre[i]]++;
    }
}
signed main()
{
    freopen("autumn.in", "r", stdin);
    freopen("autumn.out", "w", stdout);
    _ = read();
    n = read();
    for (int i = 1; i <= n * 2; i++)
    {
        a[i] = read();
    }
    n *= 2;
    init();
    solve();
    reverse(a + 1, a + n + 1);
    reverse(ans + 1, ans + n + 1);
    solve();
    reverse(ans + 1, ans + n + 1);
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i] << " ";
    }
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...