求此题题解

学术版

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 19:29:37

@ddlove2014 这不是暴力即可？一个变量维护全局异或和

by ddlove2014 @ 2024-11-28 19:31:25

@AzusidNya 但是本蒟蒻还是不会，嘤嘤嘤，大佬可一帮我写下程序吗，最好能加上注释

by AzusidNya @ 2024-11-28 19:35:00

@ddlove2014 先求出初始时序列异或和记为 sum。单点改的时候设 a[u] = v，就令 sum 异或上 a[u] ^ v 然后让 a[u] = v，查询时输出 sum。

by ddlove2014 @ 2024-11-28 19:39:12

@AzusidNya 嘶…… 谢谢大佬的帮助，但是全WA 0分了，怎么回事？

by Noble_Wolf @ 2024-11-28 19:40:54

@ddlove2014发代码呀

by ddlove2014 @ 2024-11-28 19:41:39

#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;
            Sum ^= (a[x] ^ v);
            a[x] = v;
        }
    }
    return 0;
}
//呜呜呜

by Noble_Wolf @ 2024-11-28 19:44:26

@ddlove2014兄弟这个sum一开始是a_i的异或和吧，你前面写的啥没看懂

by int_4096 @ 2024-11-28 19:44:32

@ddlove2014 你这是什么神秘方法求异或和？
你可以

int sum = 0;
for(int i = 1; i <= n; i++)
  sum ^= a[i];

by AzusidNya @ 2024-11-28 19:45:44

@ddlove2014 你题目描述错了吧？你前面写的啥哦？

而且你的样例也完全不对的样子。

难道不是

for(int i = 1; i <= n; i ++)
  Sum ^= a[i];

这样吗？

by int_4096 @ 2024-11-28 19:46:26

@AzusidNya 有点神秘。

| 下一页