Rotate
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3709 Accepted Submission(s): 711
Problem Description
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.
Input
The 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.
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.
Output
Output just according to said.
Sample Input
5
1 2 3 4 5
3
Q
R 1 3
Q
Sample Output
10
8
Author
yifenfei
Source
题意：
共n个数，m次操作，Q表示询问n个数有多少顺序数，R a,b表示区间[a,b]中的数转动一下（a+1~b每个数向前移动，a位置的数到b位置）.
代码：
//如果每询问一次就求一次顺序数很费时间，先求出最初的顺序数ans，，每转动一次时
//如果a+1~b位置的数大于a位置的数,ans--,如果小于a，ans++。hduoj时而TLE时而AC.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long A[];
int f[];
int Lowbit(int id) {return id&(-id);}
void Add(int id,int c)
{
while(id<=){
A[id]+=c;
id+=Lowbit(id);
}
}
long long query(int id)
{
long long s=;
while(id>){
s+=A[id];
id-=Lowbit(id);
}
return s;
}
int main()
{
int n,m,a,b;
char ch[];
while(scanf("%d",&n)==){
memset(A,,sizeof(A));
long long ans=;
for(int i=;i<n;i++){
scanf("%d",&f[i]);
Add(f[i],);
ans+=query(f[i]-);
}
scanf("%d",&m);
while(m--){
scanf("%s",ch);
if(ch[]=='Q') printf("%I64d\n",ans);
else{
scanf("%d%d",&a,&b);
int v=f[a];
for(int i=a;i<b;i++){
f[i]=f[i+];
if(f[i]>v) ans--;
else if(f[i]<v) ans++;
}
f[b]=v;
}
}
}
return ;
}