ABC442 D - Swap and Range Sum
Atcoder Beginner Contest 442 - D
D - Swap and Range Sum
题目传送门 - Luogu
题目传送门 - Atcoder
题目大意
给出一个数组 a a a 长度为 n n n
有 q q q 次操作，每次操作有两种情况：
-
1 x：交换 a x a_x ax 和 a x + 1 a_{x+1} ax+1 的值 -
2 l r：计算下标 l l l 到 r r r 的值
思路
暴力
其实暴力模拟即可，但是会超时，这里就不详细写思路了
时间复杂度： O ( q n ) O(qn) O(qn)
正解
这道题其实可以用树状数组来优化查询过程
先定义树状数组的相关函数：
int lowbit(int x){
return x&(-x);
}
void add(vector<int>&tr,int x,int y){
int n=tr.size()-1;
while(x<=n){
tr[x]+=y;
x+=lowbit(x);
}
}
int sum(vector<int>&tr,int x){
int ans=0;
while(x>0){
ans+=tr[x];
x-=lowbit(x);
}
return ans;
}
关于树状数组的详细知识在ABC441 E - A > B中提到过，可以查看
构建树状数组：
vector<int>tr(n+1,0);
for(int i=1;i<=n;i++){
cin>>a[i];
add(tr,i,a[i]);
}
然后处理查询：
int op;
cin>>op;
if(op==1){
int x;
cin>>x;
int ad1=a[x+1]-a[x];
int ad2=a[x]-a[x+1];
add(tr,x,ad1);
add(tr,x+1,ad2);
swap(a[x],a[x+1]);
}
else{
int l,r;
cin>>l>>r;
cout<<sum(tr,r)-sum(tr,l-1)<<"
";
}
时间复杂度： O ( ( n + q ) l o g n ) O((n+q) log n) O((n+q) log n)
AC代码：
#includeAC记录
注意
千万不要忘记初始化，要不然会 WA 掉的！
再见
大家再见啦！点个关注，下期继续！👋👋👋
