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)<<"\\n";
}
时间复杂度：
O
(
(
n
+
q
)
l
o
g
n
)
O((n+q)\\ log\\ n)
O((n+q) log n)
AC代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[200010];
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;
}
signed main(){
int n,q;
cin>>n>>q;
vector<int>tr(n+1,0);
for(int i=1;i<=n;i++){
cin>>a[i];
add(tr,i,a[i]);
}
while(q—){
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)<<"\\n";
}
}
return 0;
}
AC记录
注意
千万不要忘记初始化，要不然会 WA 掉的！
再见
大家再见啦！点个关注，下期继续！👋👋👋
