本文主要是介绍hdu 4638——Group，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线段树
题解：
题意为询问一段区间里的数能组成多少段连续的数。先考虑从左往右一个数一个数添加，考虑当前添加了i - 1个数的答案是x，那么添加完i个数后的答案是多少？可以看出，是根据a[i]-1和a[i]+1是否已经添加而定的，如果a[i]-1或者a[i]+1已经添加一个，则段数不变，如果都没添加则段数加1，如果都添加了则段数减1。设v[i]为加入第i个数后的改变量，那么加到第x数时的段数就是sum{v[i]} (1<=i<=x}。仔细想想，若删除某个数，那么这个数两端的数的改变量也会跟着改变，这样一段区间的数构成的段数就还是他们的v值的和。将询问离线处理，按左端点排序后扫描一遍，左边删除，右边插入，查询就是求区间和。
//1109MS 7296K
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((t[rt].l+t[rt].r)>>1)
#define maxn 200010
int num[maxn];
int vis[maxn];
int pla[maxn];
int n,m;
struct que
{
int l,r;
int id;
int ans;
}q[maxn];
struct tree
{
int l,r;
int sum;
}t[maxn<<2];
bool cmp(que &a,que &b)
{
return a.l<b.l;
}
bool cmp1(que &a,que &b)
{
return a.id<b.id;
}
void pushup(int rt)
{
t[rt].sum=t[ls].sum+t[rs].sum;
}
int query(int rt,int l,int r)
{
if(t[rt].l==l&&t[rt].r==r)
return t[rt].sum;
if(r<=mid)
return query(ls,l,r);
else if(l>mid)
return query(rs,l,r);
else
return query(ls,l,mid)+query(rs,mid+1,r);
}
void change(int rt,int l,int r,int val)
{
if(t[rt].l==l&&t[rt].r==r)
{
t[rt].sum=val;
return;
}
if(r<=mid)
change(ls,l,r,val);
else if(l>mid)
change(rs,l,r,val);
else
{
change(ls,l,mid,val);
change(rs,mid+1,r,val);
}
pushup(rt);
}
void build(int rt,int l,int r)
{
t[rt].l=l,t[rt].r=r;
t[rt].sum=0;
if(l==r)
return ;
build(ls,l,mid);
build(rs,mid+1,r);
}
int main()
{
int T;
int i,j;
int a,b,k;
cin>>T;
while(T--)
{
scanf("%d%d",&n,&m);
memset(vis,0,sizeof(vis));
memset(pla,0,sizeof(pla));
memset(num,0,sizeof(num));
build(1,1,n);
for(i=1;i<=n;i++)
{
scanf("%d",&num[i]);
if(!vis[num[i]-1]&&!vis[num[i]+1])
change(1,i,i,1);
else if(vis[num[i]-1]&&vis[num[i]+1])
change(1,i,i,-1);
pla[num[i]]=i;
vis[num[i]]=1;
}
for(i=1;i<=m;i++)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
q[0].l=1;
for(i=1;i<=m;i++)
{
for(j=q[i-1].l;j<=q[i].l-1;j++)
{
vis[num[j]]=0;
a=pla[num[j]+1];
if(num[j]+1<=n&&a>=q[i].l)
{
k=query(1,a,a);
if(k==-1)
change(1,a,a,0);
else if(k==0)
change(1,a,a,1);
}
b=pla[num[j]-1];
if(num[j]-1>=1&&b>=q[i].l)
{
k=query(1,b,b);
if(k==-1)
change(1,b,b,0);
else if(k==0)
change(1,b,b,1);
}
}
q[i].ans=query(1,q[i].l,q[i].r);
}
sort(q+1,q+m+1,cmp1);
for(int i=1;i<=m;i++)
printf("%d\n",q[i].ans);
}
return 0;
}
这篇关于hdu 4638——Group的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
