首页 > ACM题库 > HDU-杭电 > HDU 4638-Group-线段树-[解题报告]HOJ
2015
09-17

HDU 4638-Group-线段树-[解题报告]HOJ

Group

问题描述 :

There are n men ,every man has an ID(1..n).their ID is unique. Whose ID is i and i-1 are friends, Whose ID is i and i+1 are friends. These n men stand in line. Now we select an interval of men to make some group. K men in a group can create K*K value. The value of an interval is sum of these value of groups. The people of same group’s id must be continuous. Now we chose an interval of men and want to know there should be how many groups so the value of interval is max.

输入:

First line is T indicate the case number.
For each case first line is n, m(1<=n ,m<=100000) indicate there are n men and m query.
Then a line have n number indicate the ID of men from left to right.
Next m line each line has two number L,R(1<=L<=R<=n),mean we want to know the answer of [L,R].

输出:

First line is T indicate the case number.
For each case first line is n, m(1<=n ,m<=100000) indicate there are n men and m query.
Then a line have n number indicate the ID of men from left to right.
Next m line each line has two number L,R(1<=L<=R<=n),mean we want to know the answer of [L,R].

样例输入:

1
5 2
3 1 2 5 4
1 5
2 4

样例输出:

1
2

题意:给你一个1~N的排列,问区间[L, R] 之间有多少段连续的数。比如区间里有3、1、2、5、6,这五个数,那么就有3、1、2和5、6这两段。

        离线处理每个查询,遍历每个点,设当前处理的区间终点为R,处理每个查询的时候,首先假设所有的数a[i]都是自己独立成段,如果有a[i]+1,或者a[i]-1的数在区间[L,R]内,那么它肯定不是独立成段的,也就是我们要减去在[L,R]内不独立成段的数的个数。问题就转化为查询[L,R]之前不独立成段的数的个数。可以这样处理,对于a[i],如果发现a[i]-1,或者a[i]+1的位置,在[1,R]之间,那么我们在相应位置加上1,直接查询区间[L,R]内有多少1就可以了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <algorithm>
#include <queue>
#define INF (1<<30)
#define clearAll(a)  memset(a,0,sizeof(a))
#define sq(a) ((a)*(a))

#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(a,b) (a+((b-a)>>1))

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int N=100005;

struct node
{
    int cnt[N*4];
    void PushDown(int ind)
    {
        if(cnt[ind])
        {
            cnt[LL(ind)]+=cnt[ind];
            cnt[RR(ind)]+=cnt[ind];
            cnt[ind]=0;
        }
    }
    void build(int lft,int rht,int ind)
    {
        cnt[ind]=0;
        if(lft!=rht)
        {
            int mid=MID(lft,rht);
            build(lft,mid,LL(ind));
            build(mid+1,rht,RR(ind));
        }
    }
    void updata(int st,int ed,int lft,int rht,int ind)
    {
        if(st<=lft&&rht<=ed) cnt[ind]++;
        else
        {
            PushDown(ind);
            int mid=MID(lft,rht);
            if(st<=mid) updata(st,ed,lft,mid,LL(ind));
            if(ed> mid) updata(st,ed,mid+1,rht,RR(ind));

        }
    }
    int query(int pos,int lft,int rht,int ind)
    {
        if(lft==rht) return cnt[ind];
        else
        {
            PushDown(ind);
            int mid=MID(lft,rht);
            if(pos<=mid) return query(pos,lft,mid,LL(ind));
            else return query(pos,mid+1,rht,RR(ind));
        }
    }
}seg;

struct OP
{
    int st,ed,id;
    OP(){}
    OP(int st,int ed,int id) : st(st),ed(ed),id(id) {}
    bool operator<(const OP &B)const
    {
        return ed<B.ed;
    }
}op[N];

int pos[N],res[N],a[N];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(pos,-1,sizeof(pos));

        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            pos[a[i]]=i;
        }
        for(int i=0;i<m;i++)
        {
            int st,ed; scanf("%d%d",&st,&ed);
            op[i]=OP(st,ed,i);
        }

        seg.build(1,n,1);

        sort(op,op+m);

        int ind=0;
        for(int i=1;i<=n;i++)
        {
            int tmp=a[i];
            if(pos[tmp-1]>=1&&pos[tmp-1]<=i)
            {
                //cout<<"updata="<<1<<" "<<pos[tmp-1]<<endl;
                seg.updata(1,pos[tmp-1],1,n,1);
            }
            if(pos[tmp+1]>=1&&pos[tmp+1]<=i)
            {
                //cout<<"updata="<<1<<" "<<pos[tmp+1]<<endl;
                seg.updata(1,pos[tmp+1],1,n,1);
            }

            while(ind<m&&op[ind].ed==i)
            {
                int tmp=op[ind].ed-op[ind].st+1;
                //cout<<"query="<<op[ind].st<<" "<<op[ind].ed<<" "<<seg.query(op[ind].st,1,n,1)<<endl;
                res[op[ind].id]=tmp-seg.query(op[ind].st,1,n,1);
                ind++;
            }
        }
        for(int i=0;i<m;i++) printf("%d\n",res[i]);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/shiqi_614/article/details/9939365