You've got an array a, consisting of n integers a1, a2, ..., an. You are allowed to perform two operations on this array:
- Calculate the sum of current array elements on the segment [l, r], that is, count value al + al + 1 + ... + ar.
- Apply the xor operation with a given number x to each array element on the segment [l, r], that is, execute . This operation changes exactly r - l + 1 array elements.
Expression means applying bitwise xor operation to numbers x and y. The given operation exists in all modern programming languages, for example in language C++ and Java it is marked as "^", in Pascal — as "xor".
You've got a list of m operations of the indicated type. Your task is to perform all given operations, for each sum query you should print the result you get.
The first line contains integer n (1 ≤ n ≤ 105) — the size of the array. The second line contains space-separated integers a1, a2, ..., an(0 ≤ ai ≤ 106) — the original array.
The third line contains integer m (1 ≤ m ≤ 5·104) — the number of operations with the array. The i-th of the following m lines first contains an integer ti (1 ≤ ti ≤ 2) — the type of the i-th query. If ti = 1, then this is the query of the sum, if ti = 2, then this is the query to change array elements. If the i-th operation is of type 1, then next follow two integers li, ri (1 ≤ li ≤ ri ≤ n). If the i-th operation is of type 2, then next follow three integers li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106). The numbers on the lines are separated by single spaces.
For each query of type 1 print in a single line the sum of numbers on the given segment. Print the answers to the queries in the order in which the queries go in the input.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams, or the %I64dspecifier.
5 4 10 3 13 7 8 1 2 4 2 1 3 3 1 2 4 1 3 3 2 2 5 5 1 1 5 2 1 2 10 1 2 3
26 22 0 34 11
6 4 7 4 0 7 3 5 2 2 3 8 1 1 5 2 3 5 1 2 4 5 6 1 2 3
38 28
题意:
给出 N(1 ~ 10 ^ 5),代表有 N 个数,后给出这 N 个数 ai (0 ~ 10 ^ 6)。有两个操作,1 操作是求出 a 到 b 的区间和,2 操作是对 a 到 b 区间的数 异或 ans。每次 1 操作的时候输出结果。
思路:
线段树 + 延迟标记。将每个数都拆成 20 位二进制来统计,建成 20 颗线段树,异或的时候对区间操作所以要用延迟标记。
1 求和操作就是将每位数都拆成 20 位二进制数,后统计每位有多少个 1,然后乘以 2 ^ i,再求和得出的这个数就是求和操作的结果;
2 异或操作,当异或 0 的时候不改变状态,若异或 1 则对区间内的 0 和 1 个数倒转,因为 0 xor 1 = 1,1 xor 1 = 0。
注意改变状态的时候要 flag = 1 - flag,当 flag 是 1 的时候说明要改变儿子的值,当是 0 的时候说明不用改变,若直接 flag = 1 的话,则一直为改变状态;而 flag = 1 - flag,说明当前为 1 的话,flag 会变成 0 说明不用改变,当前为 0 的话,flag 会变成 1,说明需要改变。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int MAX = 100005; int n, dim, s, e, cha; int num[MAX]; int tree[25][MAX * 5], flag[25][MAX * 5]; ll res; void Build(int k, int fro, int to) { int mid = (fro + to) / 2; flag[dim][k] = 0; if (fro == to) { tree[dim][k] = (num[fro] >> dim) & 1; return; } Build(k * 2, fro, mid); Build(k * 2 + 1, mid + 1, to); tree[dim][k] = tree[dim][2 * k] + tree[dim][2 * k + 1]; } void Sum(int k, int fro, int to) { int mid = (fro + to) / 2; if (to < s || fro > e) return; if (fro >= s && to <= e) { res += tree[dim][k]; return; } if (flag[dim][k]) { flag[dim][k] = 0; flag[dim][k * 2] = 1 - flag[dim][k * 2]; flag[dim][k * 2 + 1] = 1 - flag[dim][k * 2 + 1]; tree[dim][k * 2] = mid - fro + 1 - tree[dim][k * 2]; tree[dim][k * 2 + 1] = to - mid - tree[dim][k * 2 + 1]; } Sum(k * 2, fro, mid); Sum(k * 2 + 1, mid + 1, to); } void Xor(int k, int fro, int to) { int mid = (fro + to) / 2; if (s > to || e < fro) return; if (s <= fro && e >= to) { flag[dim][k] = 1 - flag[dim][k]; tree[dim][k] = to - fro + 1 - tree[dim][k]; return; } if (flag[dim][k]) { flag[dim][k] = 0; flag[dim][k * 2] = 1 - flag[dim][k * 2]; flag[dim][k * 2 + 1] = 1 - flag[dim][k * 2 + 1]; tree[dim][k * 2] = mid - fro + 1 - tree[dim][k * 2]; tree[dim][k * 2 + 1] = to - mid - tree[dim][k * 2 + 1]; } Xor(k * 2, fro, mid); Xor(k * 2 + 1, mid + 1, to); tree[dim][k] = tree[dim][k * 2] + tree[dim][k * 2 + 1]; } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &num[i]); for (dim = 0; dim <= 20; ++dim) Build(1, 1, n); int m; scanf("%d", &m); while (m--) { int way; scanf("%d", &way); if (way == 1) { scanf("%d%d", &s, &e); ll sum = 0; for (dim = 0; dim < 20; ++dim) { res = 0; Sum(1, 1, n); sum += res * (1 << dim); } printf("%I64d\n", sum); } else { scanf("%d%d%d", &s, &e, &cha); for (dim = 0; dim < 20; ++dim) if (cha & (1 << dim)) Xor(1, 1, n); } } return 0; }
相关推荐
VHDL例程源码 xor2VHDL例程源码 xor2VHDL例程源码 xor2VHDL例程源码 xor2VHDL例程源码 xor2VHDL例程源码 xor2VHDL例程源码 xor2VHDL例程源码 xor2VHDL例程源码 xor2VHDL例程源码 xor2VHDL例程源码 xor2VHDL例程源码 ...
XOR算法,可用检查自己的计算结果是否正确
Kademlia 原理论文,还没仔细看过
%%使用fisher判别给XOR问题分类 使用fisher判别给XOR问题分类
xor加密.exe
XOR加密解密 里面有一个模块和一个窗体文件
xor(异或分类)问题的c++算法,很经典的
bp解决xor问题 BP网络是目前前馈式神经网络中应用最广泛的网络之一,实现BP算法训练神经网络完成XOR的分类问题。 设计要求: (1) 能够设置网络的输入节点数、隐节点数、网络层数、学习常数等各项参数; (2) 能够...
Me.Caption = "Xor 1.0" '加密完成标题 MsgBox Ret, vbInformation, "Xor 1.0" End Sub Private Sub Command2_Click() Dim Ret As String If Trim(Text3.Text) = "" Then Text3.Text = 0 End If Ret = ...
三种(AES,DES.,XOR)加解密方式的实现 环境win7+vs2013
XOR 效验 算KEY程序 非常好用的
xor文件.zip
开源工具exor的编译包,exor是一个封装对poi的使用的github开源项目。 exor用于分析excle内容并存储成一个二维结构,调用分析方法前可以设置要分析的列名和要分析的起止行数等 exor依赖于commons-collections4-4.2、...
c++解决xor问题(bp网络)
数据恢复,异或,二次异或,add xor
neural networs XOR 代码
XOR2源码数据文件,数据库参数资源。.....
ExOR算法 的 matlab 实现 自己写的 能运行 没问题
自己写的一个最新2022年1月17日17:02:41封包解密工具,...里面功能描述:xor异或位计算,根据密文和明文计算出xor的密匙key,同时支持,加密解密,加密通过xor密匙和明文加密成密文。发送到服务器。达到该封包目的。
机会路由协议 ppt 对机会路由的改进