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;
}
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
