题目描述

Description

我早已习惯你不在身边，
人间四月天 寂寞断了弦。
回望身后蓝天，
跟再见说再见……
某天,蒟蒻Autumn发现了从 Gty的妹子树(bzoj3720) 上掉落下来了许多妹子,他发现她们排成了一个序列,每个妹子有一个美丽度。
Bakser神犇与他打算研究一下这个妹子序列,于是Bakser神犇问道:"你知道区间[l,r]中妹子们美丽度的逆序对数吗?"
蒟蒻Autumn只会离线乱搞啊……但是Bakser神犇说道:"强制在线。"
请你帮助一下Autumn吧。
给定一个正整数序列a,对于每次询问,输出al...ar中的逆序对数,强制在线。

Input

第一行包括一个整数n(1<=n<=50000),表示数列a中的元素数。
第二行包括n个整数a1...an(ai>0,保证ai在int内)。
接下来一行包括一个整数m(1<=m<=50000),表示询问的个数。
接下来m行,每行包括2个整数l、r(1<=l<=r<=n),表示询问al...ar中的逆序对数(若ai > aj且i < j,则为一个逆序对)。
l,r要分别异或上一次询问的答案(lastans),最开始时lastans=0。
保证涉及的所有数在int内。

Output

对每个询问,单独输出一行,表示al...ar中的逆序对数。

Sample Input

4
1 4 2 3
1
2 4

Sample Output

2

题目分析

分块 离散化后处理出块与块之间的逆序对数 前缀块比一个数大/小的数的个数
然后就按照整块和零碎的方式套路一下计算答案即可

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,siz,ans,tot;
int num[260][260],sum[260][50200],sum2[260][50200],c[50200],f[50200],number[50200];
struct your { int val,id; } a[50200];
int cmp(your j,your k) { return j.val<k.val;  }
void update(int x) { for(;x;x-=x&-x) f[x]++; }
int ask(int x) { int sum=0; for(;x<=tot;x+=x&-x) sum+=f[x]; return sum; }
void init()
{
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++) 
        tot=tot+(a[i].val!=a[i-1].val),c[a[i].id-1]=tot;
    for(int i=0;i*siz<n;i++)
    {
        for(int tmp=0,j=i*siz;j<n;j++)
            tmp+=ask(c[j]+1),update(c[j]),num[i][j/siz]=tmp;
        memset(f,0,sizeof f);
    }
    for(int i=0;i*siz<n;i++)
    {
        for(int j=i*siz;j<i*siz+siz&&j<n;j++) number[c[j]]++;
        for(int j=1;j<=tot;j++) sum[i][j]=sum[i][j-1]+number[j-1];
        for(int j=tot;j>=1;j--) sum2[i][j]=sum2[i][j+1]+number[j+1];
    }
}
void getans(int x,int y)
{
    if(x>y) swap(x,y);
    ans=0;
    if(x/siz==y/siz)
    {
        for(int i=x;i<=y;i++)
            ans+=ask(c[i]+1),update(c[i]);
        memset(f,0,sizeof f);
        return ;
    }
    ans=num[x/siz+1][y/siz-1];
    for(int i=x;i<x/siz*siz+siz;i++)
        ans=ans+ask(c[i]+1)+(sum[y/siz-1][c[i]]-sum[x/siz][c[i]]),update(c[i]);
    for(int i=y/siz*siz;i<=y;i++)
        ans=ans+ask(c[i]+1)+(sum2[y/siz-1][c[i]]-sum2[x/siz][c[i]]),update(c[i]);
    memset(f,0,sizeof f);
}
int main()
{
    scanf("%d",&n),siz=sqrt(1.0*n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].id=i;   
    init(),scanf("%d",&m);
    for(int l,r,i=1;i<=m;i++)
    {   
        scanf("%d%d",&l,&r);
        l^=ans,r^=ans,getans(--l,--r),printf("%d\n",ans);
    }
    return 0;
}