Recently yifenfei face such a problem that give you millions of positive integers,tell how many pairs i and j that satisfy F[i] smaller than F[j] strictly when i is smaller than j strictly. i and j is the serial number in the interger sequence. Of course, the problem is not over, the initial interger sequence will change all the time. Changing format is like this [S E] (abs(E-S)<=1000) that mean between the S and E of the sequece will Rotate one times.
For example initial sequence is 1 2 3 4 5.
If changing format is [1 3], than the sequence will be 1 3 4 2 5 because the first sequence is base from 0.
For example initial sequence is 1 2 3 4 5.
If changing format is [1 3], than the sequence will be 1 3 4 2 5 because the first sequence is base from 0.
InputThe input contains multiple test cases.
Each case first given a integer n standing the length of integer sequence (2<=n<=3000000)
Second a line with n integers standing F[i](0<F[i]<=10000)
Third a line with one integer m (m < 10000)
Than m lines quiry, first give the type of quiry. A character C, if C is ‘R’ than give the changing format, if C equal to ‘Q’, just put the numbers of satisfy pairs.
OutputOutput just according to said.Sample Input
5
1 2 3 4 5
3
Q
R 1 3
Q
Sample Output
10
8
题解
这道题我们可以用树状数组求出原数组的答案
因为abs(E-S)<=1000，m<10000，所以我们可以枚举每次的区间，因为翻转每次是S+1~E往前移一位，第S个到E
所以我们先把第S位存下来，每次和后面的判断一下大小就可以了
当输入是Q的时候就直接输出就可以了
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
#define M 10005
#define N 3000005
using namespace std;
int n,m,x,y;
ll ans;
int a[N];
ll tr[M];
char s[];
int lowbit(int x){ return x&(-x); }
void add(int x){
while (x<=M){
tr[x]++;
x+=lowbit(x);
}
}
int query(int x){
int s=;
while (x>){
s+=tr[x];
x-=lowbit(x);
}
return s;
}
int main(){
while (~scanf("%d",&n)){
memset(tr,,sizeof(tr)); ans=;
for (int i=;i<n;i++){
scanf("%d",&a[i]);
add(a[i]);
ans+=query(a[i]-);
}
scanf("%d",&m);
for (int i=;i<=m;i++){
scanf("%s",s);
if (s[]=='Q') printf("%lld\n",ans);
else{
scanf("%d%d",&x,&y);
int s=a[x];
for (int i=x;i<y;i++){
a[i]=a[i+];
if (s<a[i]) ans--; else
if (s>a[i]) ans++;
}
a[y]=s;
}
}
}
return ;
}