随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

HDU 2688 Rotate

题目链接: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;
}

posted on 2011-04-11 12:19 英雄哪里出来 阅读(2038) 评论(3)  编辑 收藏 引用 所属分类: 树状数组

评论

# re: HDU 2688 Rotate  回复  更多评论   

我想问问学长
树状数组在这题是不是只是在求N对数的顺序数时把时间复杂度
从n^2降到了nlogn

而在进行变换的时候似乎是完全模拟的
那么总的时间复杂度
还是有O(M*abs(E-R))
那么多
差不多1000W是不是?
2011-04-12 10:52 |

# re: HDU 2688 Rotate  回复  更多评论   

nlogn时间也有
6000多W啊?
怎么没超时呢?
2011-04-12 10:54 |

# re: HDU 2688 Rotate  回复  更多评论   

@略
还是有O(M*abs(E-R)) 1000W
nlogn时间也有 6000多W

但这都是针对最大数据的~~大数据的组数应该不多~~
2011-04-12 11:13 | 英雄哪里出来

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理