题目链接：
题意描写叙述：对一个长度为2<=n<=3000000的数组，求数组中有序对(i<j而且F[i]<F[j]）的数量？其中数组元素F[i]范围(0<F[i]<=10000)。现有m<10000个操作
操作一：R x y（当中y-x<=1000）将数组x～y之间的元素旋转
操作二：Q查询当前数组中含有的有序对的数量
解题思路：
1、先求的原始数组中有序对的总数量(假设直接求，则时间复杂度为O（n*10000）。假设使用树状数组时间复杂度为O(nlgn))即O（n*14）
2、对于每次操作一，循环遍历F[x+1]~F[y]中元素与F[x]的关系，对总数量进行加减就可以O(1000*m)
3、对于操作二，直接输出总数量就可以(O(1))
代码：
#include <cstdio>
#include <cstring>
#define MAXN 3000010
using namespace std;
int d[MAXN];
int C[10010];
int n,m;
int lowbit(int x)
{
return x&(-x);
}
int sum(int pos)
{
int res=0;
while(pos>0)
{
res+=C[pos];
pos-=lowbit(pos);
}
return res;
}
void add(int pos,int v)
{
while(pos<=10000)
{
C[pos]+=v;
pos+=lowbit(pos);
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(C,0,sizeof(C));
long long ans=0;
for(int i=0; i<n; i++)
{
scanf("%d",&d[i]);
add(d[i],1);
ans+=sum(d[i]-1);
}
scanf("%d",&m);
char st[10];
for(int i=1; i<=m; ++i)
{
scanf("%s",st);
switch(st[0])
{
case 'Q':
printf("%I64d\n",ans);
break;
case 'R':
int l,r;
scanf("%d%d",&l,&r);
int v=d[l];
for(int j=l+1; j<=r; j++)
{
if(d[j]>v) ans--;
else if(d[j]<v) ans++;
d[j-1]=d[j];
}
d[r]=v;
break;
}
}
}
return 0;
}