求此题题解

学术版

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 ddlove2014 @ 2024-11-28 19:48:05

我前面写的是求异或和，对了int_4096,你这个是异或和吗？

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

@ddlove2014对，哥们你题面给错了吧

by AzusidNya @ 2024-11-28 19:48:58

@ddlove2014 你这个是异或和吗？建议先去了解异或的概念

by ddlove2014 @ 2024-11-28 19:50:49

@AzusidNya 看这个 https://zhuanlan.zhihu.com/p/604196415 难道不是这样的吗？本蒟蒻初学异或和，别骗我

by AzusidNya @ 2024-11-28 19:52:42

@ddlove2014 这个叫数列两两异或的和。异或和是指所有数异或起来。

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

草，文字游戏

by ddlove2014 @ 2024-11-28 19:57:40

那可能是那个库题面给错了，我 @ 下。应该就是两两异或的和了，那如果这样的话此题怎么解？

by AzusidNya @ 2024-11-28 19:57:56

@ddlove2014 如果题目是每次单点改，求两两异或的和，那直接拆位就做完了吧？

但是这是符合你的能力的题吗？

by ddlove2014 @ 2024-11-28 19:59:00

?什么意思？

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

@ddlove2014 帮你改了

#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=0;
            for(int j=0;j<=18;j++)if((a[x]>>j)&1)Count[j]--;
            a[x] = v;
            for(int j=0;j<=18;j++)if((a[x]>>j)&1)Count[j]++;
            for(int i = 0; i <= 18; i++)
            {
                val[i] = Count[i] * (n - Count[i]) * (1 << i);
                Sum += val[i];
            }
        }
    }
    return 0;
}