题目：点击此处
给你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; }
