http://acm.hdu.edu.cn/showproblem.php?pid=4638
问题其实就是求[L,R]中有多少个连续的段
若每一个人都是一个段 那么[L,R]中每一个朋友关系就会减少一个段(因为它将两个段合并了)
我们把每个朋友关系变成一个边 要求[L,R]有多少个边 可以用到 离散化+树状数组
把每个朋友关系形成的边以左端点为key从大到小排序 遍历时将右端点不断的插入
当左端点为key的边全部插入的时候 那么所有[L,R]中L等于key的询问都可求了
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<set>
#include<vector>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef pair<int,int> pp;
typedef long long ll;
const int N=100005;
int place[N];
int a[N];
struct node
{
int index;
int l,r;
}q[N];
vector<int>vt[N];
int ans[N];
int c[N];
int lowbit(int x)
{
return x&(-x);
}
void add(int i)
{
while(i<N)
{
c[i]+=1;
i+=lowbit(i);
}
}
int get(int i)
{
int tmp=0;
while(i>=1)
{
tmp+=c[i];
i-=lowbit(i);
}
return tmp;
}
bool cmp(node x,node y)
{
return x.l>y.l;
}
int main()
{
//freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
memset(c,0,sizeof(c));
for(int i=0;i<N;++i)
vt[i].clear();
memset(place,-1,sizeof(place));
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
place[a[i]]=i;
}
for(int i=1;i<=n;++i)
{
int k=a[i];
int l,r;
if(place[k+1]!=-1)
{l=min(place[k+1],i);r=max(place[k+1],i);vt[l].push_back(r);}
}
for(int i=0;i<m;++i)
{
scanf("%d %d",&q[i].l,&q[i].r);
q[i].index=i;
}
sort(q,q+m,cmp);
int I=0;
for(int i=n;i>=1;--i)
{
for(unsigned int j=0;j<vt[i].size();++j)
{
add(vt[i][j]);
}
while(I<m&&q[I].l==i)
{
ans[q[I].index]=q[I].r-q[I].l+1-get(q[I].r);
++I;
}
}
for(int i=0;i<m;++i)
printf("%d\n",ans[i]);
}
return 0;
}
