|
|
題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2688
  /**//*
 題意：
給定一串長度為N的序列(N <= 3000000)，然后是M(M<=10000)個操作，
每個操作有兩種形式：
1. Q 詢問當前序列的順序數(shù)
2. R S E (abs(E-S) <= 1000)將下標S到E的數(shù)列向左循環(huán)旋轉一次
題解：
樹狀數(shù)組
思路：
經典問題，首先將N個數(shù)的順序數(shù)用樹狀數(shù)組求出來，這個操作是nlogn
的，然后對于每次R操作，統(tǒng)計在[S+1，E]區(qū)間中比v[S]大的數(shù)和小的數(shù)的個數(shù)，
將之前的順序數(shù) - 比它大的數(shù) + 比它小的數(shù)，更新這個值。然后順序賦值即可。
Q操作只需要直接輸出當前順序數(shù)的值即可。
 */
#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;
}
|