魔卡少女(cardcaptor)——线段树
题目
【题目描述】
君君是中山大学的四年级学生。有一天在家不小心开启了放置在爸爸书房中的一本古书。于是,君君把放在书中最上面的一张牌拿出来观摩了一下,突然掀起一阵大风把书中的其她所有牌吹散到各地。这时一只看上去四不像的可爱生物「封印之兽」可鲁贝洛斯从书中钻了出来,它告诉君君书中的牌叫「库洛牌」,现在散落各地已实体化,要君君将它们全部再次封印起来,以免危害世界,于是君君开始过上了收服「库洛牌」的旅程。
经过不懈努力,君君集齐了 $N$ 张库洛牌,最后的审判就要来临,为了战胜审判者月,君君开始研究起这 $N$ 张库洛牌的魔法效果。君君已经将 $N$ 张库洛牌从左到右依次排列好,这 $N$ 张库洛牌的魔法值从左到右依次为 $a_1, a_2, a_3,…,a_N$ 。她将告诉你这 $N$ 张库洛牌的魔法值。在最后的审判时,审判者月将会选择一个区间进行 PK,君君预测了可能进行 PK 的若干区间,她想请你帮助她计算这些区间的魔法效果,以便她更好地布置战术。一个区间内,所有连续子序列都会产生魔法效果。一个连续子序列 $p_1, p_2, p_3,…,p_k$ 的魔法效果定义为 $p_1⊕p_2⊕p_3⊕…⊕p_k$ ($⊕$ 表示异或)。一个区间的魔法效果定义为所有连续子序列的魔法效果的和。例如有 $5$ 张库洛牌,魔法值为 $1, 1, 2, 4, 5$,询问区间 $[2, 4]$ 的魔法效果。区间 $[2, 4]$ 包含的连续子序列为 $\{1\}, \{2\},\{4\}, \{1,2\}, \{2,4\}, \{1,2,4\}$, 它们的魔法值分别为 $1,2,4,3,6,7$,所以区间 $[2,4]$ 的魔法效果为 $1 + 2 + 4 + 3 + 6 + 7 = 23$。
库洛牌的魔法效果狂拽炫酷吊炸天,这个值可能很大,所以你只需要输出这个值模 $100000007$。另外,任性的君君可以在询问的过程中对库洛牌的魔法值进行修改。
现在,君君给出了 $M$ 个操作,操作格式如下:
1. `M p x` 表示将第 $p$ 张库洛牌的魔法值修改为 $x$。
2. `Q l r` 表示询问区间 $[l,r]$ 的魔法效果。
Pascal 语言中,异或操作符为 xor,C++ 语言中,异或操作符为^。
【输入格式】
第一行为一个整数 $N$,表示有 $N$ 张库洛牌。
第二行为 $N$ 个整数,表示一开始 $N$ 张库洛牌的值。
第三行为一个整数 $M$,表示有 $M$ 个操作。
接下来 $M$ 行,每行表示一个操作,格式如题目描述所示。
【输出格式】
对于每个操作 $2$,输出一行,每行一个数,表示询问的区间 $[l,r]$ 的魔法效果模 $100000007$。
【样例输入】
5
1 2 3 4 5
7
Q 1 3
M 2 7
Q 1 3
M 2 2
Q 1 3
M 4 2
Q 1 5
【样例输出】
10
26
10
47
【数据范围与提示】
$30\%$ 的数据,$N,M≤300$。
另外 $20\%$ 的数据,$N,M\le 30000$,操作 $1$ 的数量不超过 $50$。
$80\%$ 的数据,$N,M≤30000$。
$100\%$ 的数据,$N≤100000,M≤100000,0≤a_i,x≤1000$。
题解
看到 $ a_i \leq 1000 $,就感觉到有玄机
做前缀异或和 $ sum $,区间 $ [l_i,r_i] $ 的答案即为 $sum[r_i] \ xor \ sum[l_i-1] $,可以发现,每一位的异或值互不影响,并且第 $i$ 位要为 $ 1 $ 必须满足一个为 $ 0 $ 一个为 $ 1 $,所以这一段区间这个位贡献就是 区间内 $ 0 $ 的个数 $\times 1$ 的个数
维护区间信息,自然是线段树
开 $10$ 课线段树,模拟维护前缀异或和,存下每一位的 $ 0,1 $ 个数,直接查询即可
考虑维护,修改 $ x $ 为 $y$ 即为将 $ [x,n] \ xor \ (x_{las} \ xor \ y) $
然后忘记判断子节点的 $tag$ 调得心态爆炸
代码
#include<bits/stdc++.h>
#define LL long long
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
int R(){
int x;bool f=;char ch;_(!)if(ch=='-')f=;x=ch^;
_()x=(x<<)+(x<<)+(ch^);return f?x:-x;}
const int N=1e5+,P=1e8+;
int n,m,a[N],sum[N],tag[N<<];
char ch[];
struct seg{int num[][];}tr[N<<];
#define Ls rt<<1
#define Rs rt<<1|1
seg make(seg a,seg b){
seg c;
for(int i=;i<=;i++){
c.num[][i]=a.num[][i]+b.num[][i];
c.num[][i]=a.num[][i]+b.num[][i];
}
return c;
}
void build(int rt,int l,int r){
if(l==r){
for(int i=;i<=;i++)
tr[rt].num[(sum[l]>>i)&][i]=;
return;}
int mid=(l+r)>>;
build(Ls,l,mid),build(Rs,mid+,r);
tr[rt]=make(tr[Ls],tr[Rs]);
return;
}
void push(int rt){
int x=tag[rt];tag[rt]=;
for(int i=;i<=;i++)
if((x>>i)&)
swap(tr[rt].num[][i],tr[rt].num[][i]);
tag[Ls]^=x,tag[Rs]^=x;
return;
}
seg query(int rt,int l,int r,int ql,int qr){
if(tag[rt])push(rt);
if(ql<=l&&qr>=r)return tr[rt];
int mid=(l+r)>>;
if(mid>=qr)return query(Ls,l,mid,ql,qr);
if(mid<ql)return query(Rs,mid+,r,ql,qr);
return make(query(Ls,l,mid,ql,qr),query(Rs,mid+,r,ql,qr));
}
LL get(seg a){
LL res=;
for(int i=;i<=;i++)
res=(LL)(res+(1ll<<i)*a.num[][i]*a.num[][i]%P)%P;
return res;
}
void update(int rt,int l,int r,int k,int x){
if(k<=l){
tag[rt]^=x,push(rt);
return;}
int mid=(l+r)>>;
if(tag[Ls])push(Ls);
if(tag[Rs])push(Rs);
if(k<=mid)update(Ls,l,mid,k,x);
update(Rs,mid+,r,k,x);
tr[rt]=make(tr[Ls],tr[Rs]);
return;
}
int main(){
n=R();
for(int i=;i<=n;i++)
a[i]=R(),sum[i]=sum[i-]^a[i];
build(,,n);
m=R();
for(int i=,x,y;i<=m;i++){
scanf("%s",ch+),x=R(),y=R();
if(ch[]=='Q')printf("%lld\n",get(query(,,n,x-,y)));
else
update(,,n,x,a[x]^y),a[x]=y;
}
return ;
}
最新文章
- 用Maven部署war包到远程Tomcat服务器
- vue-validator(vue验证器)
- java入门笔记(1)
- 很不错的在线Office控件:IWebOffice与SOAOffice
- Qt 之 使用 https发送 HTTP请求(使用OPENSSL库)
- 并非然并卵的z-index
- JavaScript DOM高级程序设计 4.3控制事件流和注册事件侦听器--我要坚持到底!
- Qt经典出错信息之”Basic XLib functionality test failed!”
- 【转载】详细解读C#中的 .NET 弱事件模式
- 【dp】 poj 1953
- angular.js实现省市区三级联动指令
- poj_1679: The Unique MST【次小生成树】
- Linux - 简明Shell编程04 - 判断语句(If)
- c++给数组整体赋初值
- delphi中Bitmap位图与base64字符串相互转换
- 【Kibana】自定义contextPath
- Transport scheme NOT recognized: [stomp]
- WebFrom 小程序【条件查询与分页整合】
- 〖Android〗我的ADT Eclipse定制
- webpack开发小总结