BZOJ3289 Mato的文件管理（莫队+树状数组）

　　这个做法非常显然。

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
#define N 50010
int n,a[N],b[N],tree[N],m,block;
long long ans[N];
struct data
{
    int i,k,l,r;
    bool operator <(const data&a) const
    {
        return k<a.k||k==a.k&&((k&1)?r<a.r:r>a.r);
    }
}q[N];
void add(int k,int x){while (k<=n) tree[k]+=x,k+=k&-k;}
int query(int k){int s=0;while (k) s+=tree[k],k-=k&-k;return s;}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("bzoj3289.in","r",stdin);
    freopen("bzoj3289.out","w",stdout);
    const char LL[]="%I64d
";
#else
    const char LL[]="%lld
";
#endif
    n=read();
    for (int i=1;i<=n;i++) b[i]=a[i]=read();
    sort(b+1,b+n+1);
    int t=unique(b+1,b+n+1)-b;
    for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+t,a[i])-b;
    m=read();
    block=sqrt(n);
    for (int i=1;i<=m;i++) q[i].i=i,q[i].l=read(),q[i].r=read(),q[i].k=q[i].l/block;
    sort(q+1,q+m+1);
    q[0].l=1;
    for (int i=1;i<=m;i++)
    {
        ans[q[i].i]=ans[q[i-1].i];
        while (q[i-1].r<q[i].r) ans[q[i].i]+=query(n)-query(a[++q[i-1].r]),add(a[q[i-1].r],1);
        while (q[i-1].r>q[i].r) add(a[q[i-1].r],-1),ans[q[i].i]-=query(n)-query(a[q[i-1].r--]);
        while (q[i-1].l>q[i].l) ans[q[i].i]+=query(a[--q[i-1].l]-1),add(a[q[i-1].l],1);
        while (q[i-1].l<q[i].l) add(a[q[i-1].l],-1),ans[q[i].i]-=query(a[q[i-1].l++]-1);
    }
    for (int i=1;i<=m;i++) printf(LL,ans[i]);
    return 0;
}

　　当然也可以分块。预处理出块内答案和两块间答案，块外主席树查询。