求此题题解

学术版

ddlove2014 @ 2024-11-28 19:24:52

给定1个长最多为1e6的数列和操作个数两个操作第一个操作是将a[x]赋值成v 第二个操作是求a数组的异或和

输入格式： n, D A opt(opt = 'C'时执行操作1，在输入x和v) (opt = 'A'时执行操作2)

输出格式：对于每个操作2，输出1行答案

数据范围： n <= 1000000 D(操作个数）<= 2000 Ai <= 100000

输入输出样例：输入： 10 3 1 2 3 4 5 6 7 8 9 10 A C 1 3 A

输出: 339 337

可以帮忙写一下题解吗，本蒟蒻不会

by AzusidNya @ 2024-11-28 20:01:52

@ddlove2014 拆二进制位。对于每一位维护这一位的两两异或的和，这个靠 0 的数量和 1 的数量就能推出来。每次修改的时候暴力对每一位修改，然后再求和即可。时间复杂度 O(n \log V + q \log V)，V 是值域。

我的意思是，虽然这个题不难，但是如果你连异或的和和异或和的概念都分不清，那你似乎完全不具备有做这个题的能力。建议先练好基础算法。

by ddlove2014 @ 2024-11-28 20:02:44

@Noble_Wolf Yes!谢谢大佬，提交后一片绿，我自己看看代码啥意思，我是蒟蒻，多多指教

by AzusidNya @ 2024-11-28 20:03:19

@ddlove2014 就比如「求异或之和」这一点你都要去上网查题解的话，那你自然是做不出带修改的。

by Noble_Wolf @ 2024-11-28 20:03:52

@AzusidNya.兄弟别骂了，人家小孩子

by AzusidNya @ 2024-11-28 20:07:10

@Noble_Wolf 可能说话确实有点冲（）我感觉我主要还是在讲道理吧，至少你也看我没用骂人的话吧（

如果是在训练时索要题解然后自己不理解是没帮助的吧，而且训练远超过自己能力范围的题也没什么帮助吧。主要是想说明这个。

by ddlove2014 @ 2024-11-28 20:07:40

@AzusidNya 呜呜呜，大佬别骂了，别骂了，我只是感兴趣，想学一学，呜呜呜

by AzusidNya @ 2024-11-28 20:07:55

@Noble_Wolf 例如要完题解就直接交不太好吧，怎么都应该知道做法后自己写一份吧（）

by Noble_Wolf @ 2024-11-28 20:08:48

@AzusidNya你说得对

by ddlove2014 @ 2024-11-28 20:23:36

@AzusidNya

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[1000005];
int Count[35];
int val[35];
int n, d;
signed main()
{
    cin >> n >> d;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        for(int j = 0; j <= 18; j++)
            if((a[i] >> j) & 1) 
                Count[j]++;
    }
    int Sum = 0;
    for(int i = 0; i <= 18; i++)
    {
        val[i] = Count[i] * (n - Count[i]) * (1 << i);
        Sum += val[i];
    }
    while(d--)
    {
        char opt;
        cin >> opt;
        if(opt == 'A') cout << Sum << endl;
        else
        {
            int x, v;
            cin >> x >> v;
            for(int j = 0; j <= 18; j++)
            {
                if((a[x] >> j) & 1) Count[j]--;
                if((v >> j) & 1) Count[j]++;
                int tmp = val[j];
                val[j] = Count[j] * (n - Count[j]) * (1 << j);
                Sum = Sum - tmp + val[j];
            }
            a[x] = v;
        }
    }
    return 0;
}//写完了，呜呜呜

上一页 |