Group

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

1
2

题意：给你一个1-n的排列，问区间[L, R] 之间有多少段连续的数。

思路：离线处理,每个查询按照r从小到大排序.从1-n开始,考虑每个点,首先每个位置都设为1.

表示先不管其他的,i这个位置上的数可以成为一个组,然后在看 c[i]-1 和 c[i+1]的位置,如果c[i]-1

或c[i]+1的位置在i的前方,那么可以与c[i]合并了,即就在对应的位置上减1最后的答案就是区间的和。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=100010;

struct tree
{
    int l,r,num;
}a[maxn*4];
struct node
{
    int l,r,index;
    void fun(int ll,int rr,int inde)
    {
        l=ll,r=rr;
        index=inde;
    }
}b[maxn];
int pre[maxn],c[maxn],ans[maxn],n,m;
bool visited[maxn];

bool cmp(node p,node q)
{
    if(p.r==q.r)  return p.l<q.l;
    return p.r<q.r;
}

void initial()
{
    memset(pre,-1,sizeof(pre));
    memset(visited,0,sizeof(visited));
}

void input()
{
    int x,y;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&c[i]);
        pre[c[i]]=i;
    }
    for(int i=0;i<m;i++)
    {
         scanf("%d %d",&x,&y);
         b[i].fun(x-1,y-1,i);
    }
    sort(b,b+m,cmp);
}

void build(int l,int r,int k)
{
    a[k].l=l,a[k].r=r;
    a[k].num=0;
    if(l==r)   return ;
    int mid=(l+r)>>1;
    build(l,mid,2*k);
    build(mid+1,r,2*k+1);
}

void update(int l,int r,int add,int k)
{
    if(a[k].l==l && a[k].r==r) a[k].num+=add;
    else
    {
        int mid=(a[k].l+a[k].r)>>1;
        if(r<=mid)  update(l,r,add,2*k);
        else update(l,r,add,2*k+1);
        a[k].num=a[2*k].num+a[2*k+1].num;
    }
}

int query(int l,int r,int k)
{
    if(a[k].l==l && a[k].r==r) return a[k].num;
    else
    {
        int mid=(a[k].l+a[k].r)>>1;
        if(r<=mid)      return query(l,r,2*k);
        else if(l>mid)  return query(l,r,2*k+1);
        else  return query(l,mid,2*k)+query(mid+1,r,2*k+1);
    }
}

void solve()
{
    build(0,n-1,1);
    int t=0;
    for(int i=0;i<n;i++)
    {
        int tmp=c[i],Min=c[i]-1,Max=c[i]+1;
        if(Max<=n && visited[Max])  update(pre[Max],pre[Max],-1,1);
        if(Min>=1 && visited[Min])  update(pre[Min],pre[Min],-1,1);
        update(i,i,1,1);
        visited[tmp]=1;
        while(b[t].r==i)
        {
            ans[b[t].index]=query(b[t].l,b[t].r,1);
            t++;
        }
    }
    for(int i=0;i<m;i++)   printf("%d\n",ans[i]);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        initial();
        input();
        solve();
    }
    return 0;
}

hdu 4638 Group (线段树+离线处理)

原文：http://blog.csdn.net/u012596172/article/details/44562619