BZOJ3744: Gty的妹子序列

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3744

Solution

先离散化，再预处理出f[i][j]表示第i个快到第j个块逆序对数量和num[i][j]表示前i个块小于等于j的数的个数。
然后配合树状数组分块搞一下就可以了。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll int
#define N 50500
#define M 250
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    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;
}
ll n,m,block,l,r,cnt1,cnt2,T,lastans;
ll c[N],num[M][N],f[M][M],a[N],b[N],pos[N],start[N];
void add(ll x){for (;x<=n;x+=x&-x) c[x]++;}
ll get(ll x){
    ll ans=0;
    for (;x;x-=x&-x) ans+=c[x];
    return ans;
}
ll work(ll x,ll y){
    ll l=pos[x],r=pos[y],ans=0,cnt;
    memset(c,0,sizeof c);
    if (l==r){
        for (ll i=y;i>=x;i--)
            ans+=get(a[i]-1),add(a[i]);
        return ans;
    }
    ans=f[l+1][r-1]; cnt=start[r]-start[l+1];
    for (ll i=start[l+1]-1;i>=x;i--){
        ans+=get(a[i]-1)+num[r-1][a[i]-1]-num[l][a[i]-1];
        add(a[i]); cnt++;
    }
    for (ll i=start[r];i<=y;i++){
        ans+=cnt-get(a[i])-num[r-1][a[i]]+num[l][a[i]];
        add(a[i]); cnt++;
    }
    return ans;
}
int main(){
    n=read();
    for (ll i=1;i<=n;i++)
        a[i]=b[i]=read();
    sort(b+1,b+1+n);
    for (ll i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+1+n,a[i])-b;
    ll block=sqrt(n);
    for (ll i=1;i<=n;i++)
        pos[i]=(i-1)/block+1;
    m=pos[n];
    for (ll i=1;i<=m;i++)
        start[i]=(i-1)*block+1;
    start[m+1]=n+1;
    for (ll i=1;i<=m;){
        for (ll j=i;j<=m;j++)
        for (ll k=start[j];k<start[j+1];k++){
            f[i][j]=cnt1+=cnt2-get(a[k]);
            add(a[k]); cnt2++; num[j][a[k]]++;
        }
        i++; cnt1=cnt2=0; memcpy(num[i],num[i-1],sizeof num[i]);
        memset(c,0,sizeof c);
    }
    for (ll i=1;i<=m;i++)
    for (ll j=2;j<=n;j++)
        num[i][j]+=num[i][j-1];
    T=read(); lastans=0;
    while (T--){
        l=read()^lastans; r=read()^lastans;
        printf("%d\n",lastans=work(l,r));
    }
}