|
|
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2688
  /**//*
 题意：
给定一串长度为N的序列(N <= 3000000)，然后是M(M<=10000)个操作，
每个操作有两种形式：
1. Q 询问当前序列的顺序数
2. R S E (abs(E-S) <= 1000)将下标S到E的数列向左循环旋转一次
题解：
树状数组
思路：
经典问题，首先将N个数的顺序数用树状数组求出来，这个操作是nlogn
的，然后对于每次R操作，统计在[S+1，E]区间中比v[S]大的数和小的数的个数，
将之前的顺序数 - 比它大的数 + 比它小的数，更新这个值。然后顺序赋值即可。
Q操作只需要直接输出当前顺序数的值即可。
 */
#include <iostream>
using namespace std;
#define maxn 10001
int ans[3000001];
int n, m;
#define ll __int64
ll c[maxn];
int lowbit(int x)  {
return x & (-x);
}
void add(int pos) {
  while(pos < maxn) {
c[pos] ++;
pos += lowbit(pos);
 }
}
ll sum(int pos) {
ll s = 0;
while(pos > 0) {
s += c[pos];
pos -= lowbit(pos);
}
return s;
}
int main() {
int i;
while(scanf("%d", &n) != EOF) {
for(i = 1; i <= 10000; i++)
c[i] = 0;
ll val = 0;
for(i = 0; i < n; i++) {
scanf("%d", &ans[i]);
val += sum(ans[i] - 1);
add(ans[i]);
}
scanf("%d", &m);
while(m--) {
char str[10];
scanf("%s", str);
if(str[0] == 'Q') {
printf("%I64d\n", val);
}else {
int s, e;
scanf("%d %d", &s, &e);
if(s > e) {
int tmp = s;
s = e;
e = tmp;
}
if(s != e) {
int v = ans[s];
int lt = 0, bt = 0;
for(i = s; i < e; i++) {
ans[i] = ans[i+1];
if(v < ans[i+1]) {
lt ++;
}
if(v > ans[i+1]) {
bt ++;
}
}
ans[e] = v;
val = val - lt + bt;
}
}
}
}
return 0;
}
|