```cpp
lower_bound(a+1,a+n+1,k)
查a[1]~a[n]第一个>=k的位置地址
由地址得下标:lower_bound(a+1,a+n+1,k)-a
·查第一个<=:lower_bound(a+1,a+n+1,k,greater<int>())
upper_bound(a+1,a+n+1,k)
查a[1]~a[n]第一个>k的位置地址
由地址得下标:upper_bound(a+1,a+n+1,k)-a
·查第一个<:upper_bound(a+1,a+n+1,k,greater<int>())
```
by _Haoomff_ @ 2024-02-06 16:19:05
@[ACPC](/user/540363) 改好了
by C20252323tzy @ 2024-02-06 16:28:25
@[ACPC](/user/540363) 修改之后要重构
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mpr make_pair
#define fr first
#define sc second
#define rc(x) min(n,x*val)
#define lc(x) (x*val-val+1)
inline int read(){
int res=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();}
return res*f;
}
const int N=2e4+5,SN=1e3+5;
int n,m,a[N],b[N],c[N],aa[N],bb[N],cnt;
int merge(int l,int r,int mid){
int ans=0,b1=0,c1=0,b2=1,c2=1;
for (int i=l;i<=mid;i++) b[++b1]=a[i];
for (int i=mid+1;i<=r;i++) c[++c1]=a[i];
for (int i=l;i<=r;i++){
if (b1>=b2&&(c1+1==c2||b[b2]<=c[c2])) a[i]=b[b2++];
else {a[i]=c[c2++];ans+=b1-b2+1;}
}
return ans;
}
int solve(int l,int r){
if (l==r) return 0;
int mid=(l+r)>>1,ans=0;
ans+=solve(l,mid)+solve(mid+1,r)+merge(l,r,mid);
return ans;
}
struct block_array{
int val,block[N],mx[SN],mn[SN];
vector<int>vec[SN];
void rsort(int b){
vec[b].clear();
for (int i=lc(b);i<=rc(b);i++) vec[b].push_back(a[i]);
sort(vec[b].begin(),vec[b].end());
mx[b]=vec[b][vec[b].size()-1],mn[b]=vec[b][0];
}
void build(int siz){
val=sqrt(siz);
for (int i=1;i<=siz;i++) block[i]=(i-1)/val+1;
for (int i=1;i<=(n+val-1)/val;i++) rsort(i);
}
void change(int l,int r){
if (a[l]==a[r]) return;
if (a[l]>a[r]) cnt--;
if (a[l]<a[r]) cnt++;
int lessl=queryless(l+1,r-1,a[l]),lessr=queryless(l+1,r-1,a[r]),morel=querymore(l+1,r-1,a[l]),morer=querymore(l+1,r-1,a[r]);
// cout<<lessl<<' '<<lessr<<' '<<morel<<' '<<morer<<' '<<l<<' '<<r<<' '<<a[l]<<' '<<a[r]<<'\n';
cnt+=morel+lessr-lessl-morer;
swap(a[l],a[r]);
rsort(block[l]),rsort(block[r]);//这里
}
int queryless(int l,int r,int c){
if (l>r) return 0;
int bl=block[l],br=block[r],ans=0;
if (bl==br){
for (int i=l;i<=r;i++) if (a[i]<c) ans++;
return ans;
}
for (int i=l;i<=rc(bl);i++) if (a[i]<c) ans++;
for (int i=r;i>=lc(br);i--) if (a[i]<c) ans++;
for (int i=bl+1;i<=br-1;i++){
ans+=lower_bound(vec[i].begin(),vec[i].end(),c)-vec[i].begin();
}
return ans;
}
int querymore(int l,int r,int c){
if (l>r) return 0;
int bl=block[l],br=block[r],ans=0;
if (bl==br){
for (int i=l;i<=r;i++) if (a[i]>c) ans++;
return ans;
}
for (int i=l;i<=rc(bl);i++) if (a[i]>c) ans++;
for (int i=r;i>=lc(br);i--) if (a[i]>c) ans++;
for (int i=bl+1;i<=br-1;i++){
ans+=vec[i].end()-upper_bound(vec[i].begin(),vec[i].end(),c);
}
return ans;
}
}book;
signed main(){
n=read();
for (int i=1;i<=n;i++) a[i]=aa[i]=bb[i]=read();
cnt=solve(1,n),cout<<cnt<<'\n';
for (int i=1;i<=n;i++) a[i]=aa[i];
sort(bb+1,bb+n+1);
int len=unique(bb+1,bb+n+1)-bb-1;
for (int i=1;i<=n;i++) a[i]=lower_bound(bb+1,bb+1+len,a[i])-bb;
book.build(n);
m=read();
while (m--){
int l=read(),r=read();
if (l>r) swap(l,r);
book.change(l,r);
cout<<cnt<<'\n';
}
return 0;
}
```
by C20252323tzy @ 2024-02-06 16:29:01
@[_Haoomff_](/user/368111) 我要你调题呢哥(
by ACPC @ 2024-02-06 17:42:48
@[C20252323tzy](/user/770611) 感谢!~~我降智了~~
八关在给了
by ACPC @ 2024-02-06 17:44:35
@[C20252323tzy](/user/770611) 给完了,Thanks♪(・ω・)ノ
by ACPC @ 2024-02-06 17:50:06
@[ACPC](/user/540363) 成功暴露您是临时邮箱巨佬
by wxzzzz @ 2024-02-06 21:40:19
@[ACPC](/user/540363) 但是你标题不是写“lower_bound和upper_bound到底怎么用”吗?
by _Haoomff_ @ 2024-02-07 08:02:43
@[_Haoomff_](/user/368111) 那你猜我放一个代码是干嘛的()
by ACPC @ 2024-02-07 09:39:27