HDU 2688 Rotate
英雄哪里出来发表于 2011-04-11 04:19:00
题目链接：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;
}
/**//*题意： 给定一串长度为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 10001int ans[3000001];int n, m;#define ll __int64ll 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;}