关于lower_bound&upper_bound

for(int i=block[l]+1;i<=block[r]-1;++i)
    temp+=atag[i].size()-(upper_bound(atag[i].begin(),atag[i].end(),x)-atag[i].begin());//查找块内大于x的数的个数
for(int i=block[l]+1;i<=block[r]-1;++i)
    temp+=lower_bound(atag[i].begin(),atag[i].end(),x)-atag[i].begin();//查找块内小于x的数的个数

#include<bits/stdc++.h>
#define N 20005
using namespace std;
vector<int> atag[200];
int block[N],v[N],blo,Ans,n;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline int greater_query(int x,int l,int r)
{
    int temp=0;
    for(int i=l;i<=min(r,block[l]*blo);i++)
    if(v[i]>x) temp++;
    if(block[l]==block[r]) return temp;
    for(int i=(block[r]-1)*blo+1;i<=r;++i)
    if(v[i]>x) temp++;
    for(int i=block[l]+1;i<=block[r]-1;++i)
    temp+=atag[i].size()-(upper_bound(atag[i].begin(),atag[i].end(),x)-atag[i].begin());
    return temp;
}
inline int less_query(int x,int l,int r)
{
    int temp=0;
    for(int i=l;i<=min(r,block[l]*blo);i++)
    if(v[i]<x) temp++;
    if(block[l]==block[r]) return temp;
    for(int i=(block[r]-1)*blo+1;i<=r;++i)
    if(v[i]<x) temp++;
    for(int i=block[l]+1;i<=block[r]-1;++i)
    temp+=lower_bound(atag[i].begin(),atag[i].end(),x)-atag[i].begin();
    return temp;
}
inline void modify_pos(int l,int r)
{
    if(block[l]==block[r]) {swap(v[l],v[r]);return;}
    
    int pl=lower_bound(atag[l].begin(),atag[l].end(),v[l])-atag[l].begin();
    atag[block[l]][pl]=v[r];
    while(pl&&atag[block[l]][pl]<atag[block[l]][pl-1]) 
    swap(atag[block[l]][pl],atag[block[l]][pl-1]),pl--;
    while(pl<atag[block[l]].size()-1&&atag[block[l]][pl]>atag[block[l]][pl+1]) 
    swap(atag[block[l]][pl],atag[block[l]][pl+1]),pl++;
    
    int pr=lower_bound(atag[r].begin(),atag[r].end(),v[r])-atag[r].begin();
    atag[block[r]][pr]=v[l];
    while(pr&&atag[block[r]][pr]<atag[block[r]][pr-1]) 
    swap(atag[block[r]][pr],atag[block[r]][pr-1]),pr--;
    while(pr<atag[block[r]].size()-1&&atag[block[r]][pr]>atag[block[r]][pr+1]) 
    swap(atag[block[r]][pr],atag[block[r]][pr+1]),pr++;
    
    swap(v[l],v[r]);
    return;
}
inline void update(int l,int r)
{
	if(l==r||v[l]==v[r]) {swap(v[l],v[r]);return;}
    int temp_l=less_query(v[l],l,r);
    int temp_r=greater_query(v[r],l,r);
    modify_pos(l,r);
    Ans-=(temp_l+temp_r);
    temp_l=less_query(v[l],l,r);
    temp_r=greater_query(v[r],l,r);
    Ans+=temp_l+temp_r;
    if(v[l]<v[r]) Ans++;
    if(v[l]>v[r]) Ans--;
}
int main()
{
    n=read();
    blo=sqrt(n);
    for(int i=1;i<=n;++i)
    {
        v[i]=read();
        block[i]=(i-1)/blo+1;
        atag[block[i]].push_back(v[i]);
    }
    for(int i=1;i<=block[n];++i) sort(atag[i].begin(),atag[i].end());
    for(int i=1;i<n;++i) Ans+=less_query(v[i],i+1,n);
    printf("%d\n",Ans);
    int m=read();
    for(int i=1;i<=m;++i)
    {
        int x=read(),y=read();
        if(x>y) swap(x,y);
        update(x,y);
        printf("%d\n",Ans);
    }
}