Rotate
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2287 Accepted Submission(s): 546
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.
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.
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
/*
HDOJ 2688 树状数组
C++过 G++超时
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define N 10001
#define M 3000010
int f[M];
__int64 a[N];
void add(int x)
{
while(x<=N)
{
a[x]+=1;
x+=x&-x;
}
}
__int64 sum(int x)
{
__int64 sum=0;
while(x>0)
{
sum+=a[x];
x-=x&-x;
}
return sum;
}
int main()
{
int n,m,x,y,i,t,temp;
char str[2];
__int64 ans;
//freopen("test.txt","r",stdin);
while(scanf("%d",&n)!=EOF)
{
memset(a,0,sizeof(a));
ans=0;
for(i=0;i<n;i++)
{
scanf("%d",&f[i]);
ans+=sum(f[i]-1);//查找比当前数小的
add(f[i]);
}
scanf("%d",&t);
while(t--)
{
scanf("%s",str);
if(str[0]=='Q')
printf("%I64d\n",ans);
else
{
scanf("%d%d",&x,&y);
if(x>y)
{
temp=x;
x=y;
y=temp;
}
temp=f[x];//每个向前移动一个，第一个数会被移动最后
//因为第一个数到最后了，所以要更新，比最后个数小的
for(i=x;i<y;i++)
{
f[i]=f[i+1];
if(f[i]<temp)
ans++;
else if(f[i]>temp)
ans--;
}
f[y]=temp;
}
}
}
return 0;
}