题目：点击此处

给你n个数，q个询问，每次询问一个区间内的逆序对的对数

莫队套上树状数组即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#define ll long long
using namespace std;
const int maxn=1e6+5;
map<int,int> mp;
int n,t=0,k;
struct node
{
    int a,i;
}pos[maxn];

struct node1
{
    int l,r,i;
}pos1[maxn];
int block;
bool cmp(node1 a,node1 b)
{
    if(a.l/block!=b.l/block)return a.l/block<b.l/block;
    return a.r<b.r;
}
bool cmp1(node a,node b)
{
    return a.a<b.a;
}
bool cmp2(node a,node b)
{
    return a.i<b.i;
}
int c[maxn],a,answer[maxn],q,ans,INDEX;
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int y){
    for(int i=x;i<=INDEX;i+=lowbit(i))
        c[i] += y;
}
int getsum(int x){
    int ans1 = 0;
    for(int i=x;i;i-=lowbit(i))
        ans1 += c[i];
    return ans1;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        pos[i].a=a;
        pos[i].i=i;
    }
    sort(pos+1,pos+n+1,cmp1);
    INDEX=0;
    for(int i=1;i<=n;i++)
    {
        if(mp[pos[i].a]==0)
        {
            INDEX++;
            mp[pos[i].a]=INDEX;
        }
    }
    block=sqrt(1.0*n);
    sort(pos+1,pos+n+1,cmp2);
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&pos1[i].l,&pos1[i].r);
        pos1[i].i=i;
    }
    sort(pos1+1,pos1+q+1,cmp);
    int cl=1,cr=0;
    for(int i=1;i<=q;i++)
    {
        int l=pos1[i].l,r=pos1[i].r,j;
        if(l==r)
        {
            answer[pos1[i].i]=0;
            continue;
        }
        while(cr<r)
        {
             int re=getsum(mp[pos[cr+1].a]);
             ans+=(cr+1-cl-re);
             add(mp[pos[cr+1].a],1);
             cr++;
        }
        while(cr>r)
        {
             int re=getsum(mp[pos[cr].a])-1;
             ans-=(cr-cl-re);
             add(mp[pos[cr].a],-1);
             cr--;
        }
        while(cl<l) {
            add(mp[pos[cl].a],-1);
            int re=getsum(mp[pos[cl].a] - 1);
            ans-=re;
            cl++;
        }
        while(cl>l)
        {
            ans+=getsum(mp[pos[cl-1].a] - 1);
            add(mp[pos[cl-1].a], 1);
            cl--;
        }
        answer[pos1[i].i]=ans;
    }
    for(int i=1;i<=q;i++)
        printf("%d\n",answer[i]);
    return 0;
}