F - Easy Fix
发现交换 l,r不会影响 1到l-1和r+1到 n
对l+1,r-1的影响只有正负一(用主席树计算一下改变的量,一共四种情况)
对l和r再算一下
//#pragma GCC optimize(2)
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int inf=8e18;
const int maxn=2e5+100;
int a[maxn],c[maxn],p[maxn],b[maxn],d[maxn],pre[maxn];
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int val)
{
while(x<maxn)
{
c[x]+=val;
x+=lowbit(x);
}
}
int ask(int x)
{
int ans=0;
while(x>0)
{
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
struct node
{
int l,r;
int sum;
int op[5];
} t[maxn*32];
int cnt,root[maxn];
void update(int l,int r,int &x,int y,int num,vector<int>v)
{
x=++cnt;
t[x]=t[y];
t[x].sum++;
for(auto it:v) t[x].op[it]++;
//t[x].op[type]++;
if(l==r)return ;
int mid=(l+r)>>1;
if(num<=mid) update(l,mid,t[x].l,t[y].l,num,v);
else update(mid+1,r,t[x].r,t[y].r,num,v);
}
int query(int l,int r,int x,int y,int num,int type)//查询<= num [type]的个数
{
if(r<=num)return t[y].op[type]-t[x].op[type];
int mid=(l+r)>>1;
int ans=0;
if(num>=l) ans+=query(l,mid,t[x].l,t[y].l,num,type);
if(num>mid) ans+=query(mid+1,r,t[x].r,t[y].r,num,type);
return ans;
}
int query(int l,int r,int x,int y,int num)//查询<= num的个数
{
if(r<=num)return t[y].sum-t[x].sum;
int mid=(l+r)>>1;
int ans=0;
if(num>=l) ans+=query(l,mid,t[x].l,t[y].l,num);
if(num>mid) ans+=query(mid+1,r,t[x].r,t[y].r,num);
return ans;
}
signed main()
{
IOS
int n,q;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>p[i];
}
//cout<<"A:";
for(int i=1; i<=n; i++)
{
a[i]=ask(p[i]);
update(p[i],1);
//cout<<a[i]<<" ";
}
//cout<<"\n";
//cout<<"B:";
for(int i=1; i<=n; i++) update(p[i],-1);
for(int i=n; i>=1; i--)
{
b[i]=ask(p[i]);
update(p[i],1);
d[i]=min(a[i],b[i]);
}
for(int i=1; i<=n; i++)
{
//cout<<b[i]<<" ";
pre[i]=pre[i-1]+d[i];
}
//cout<<"\n";
for(int i=1; i<=n; i++)
{
vector<int>v;
if(a[i]<=b[i]) v.pb(1);
if(a[i]-1>b[i]) v.pb(2);
if(a[i]>=b[i]) v.pb(3);
if(a[i]<b[i]-1) v.pb(4);
update(1,(int)1e6,root[i],root[i-1],p[i],v);
}
cin>>q;
while(q--)
{
int l,r;
cin>>l>>r;
if(l>r) swap(l,r);
if(l==r)
{
cout<<pre[n]<<"\n";
continue;
}
int ans=pre[n]-d[l]-d[r];
if(p[l]<p[r])
{
int s2=query(1,1e6,root[l],root[r-1],p[r],2)-query(1,1e6,root[l],root[r-1],p[l],2);
int s1=query(1,1e6,root[l],root[r-1],p[r],1)-query(1,1e6,root[l],root[r-1],p[l],1);
ans+=s2-s1;
}
else
{
int s4=query(1,1e6,root[l],root[r-1],p[l],4)-query(1,1e6,root[l],root[r-1],p[r],4);
int s3=query(1,1e6,root[l],root[r-1],p[l],3)-query(1,1e6,root[l],root[r-1],p[r],3);
ans+=s4-s3;
}
int low_l=query(1,1e6,root[l],root[r],p[l]);
int low_r=query(1,1e6,root[l-1],root[r-1],p[r]);
ans+=min(a[l]+low_l,b[l]-low_l);
ans+=min(a[r]-low_r,b[r]+low_r);
cout<<ans<<"\n";
}
}