首页 > ACM题库 > HDU-杭电 > hdu 2688 Rotate-线段树-[解题报告]C++
2014
02-13

hdu 2688 Rotate-线段树-[解题报告]C++

Rotate

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

5
1 2 3 4 5
3
Q
R 1 3
Q

样例输出:

10
8

题目链接

开始学习树状数组和线段树

题意:R表示k1–k2依次向左循环1位 Q:查询多少升序序列

#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 3000005
int arr[10005],a[maxn];
int lowbit(int x)  //判断最右边1的位置
{
    return x&(-x);
}
void update(int x,int val) //更新c[i]的值
{
    while(x<10001)
    {
        arr[x]+=val;
        x+=lowbit(x);
    }
}
int getsum(int x)  //求和c[1]+...+c[x]
{
    int ans=0;
    while(x>0)
    {
        ans+=arr[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    __int64 ans;
    int i,j,n,m,x,y;
    char c;
    while(scanf("%d",&n)!=EOF)
    {
        ans=0;
        memset(arr,0,sizeof(arr));
        memset(a,0,sizeof(a));
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            update(a[i],1);
            ans+=getsum(a[i]-1);
        }
        scanf("%d",&m);
        while(m--)
        {
            getchar();
            scanf("%c",&c);
            if(c=='Q') printf("%I64d\n",ans);
            if(c=='R')
            {
                scanf("%d%d",&x,&y);
                x++;y++;  //下标从1开始
                int temp=a[x];
                for(i=x;i<y;i++)
                {
                    a[i]=a[i+1];
                    if(a[i]>temp) ans--;  //注意
                    if(a[i]<temp) ans++;
                }
                a[y]=temp;
            }
        }
    }
    return 0;
}

解题转自:http://blog.csdn.net/littlefool5201314/article/details/10018565


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。