http://acm.hdu.edu.cn/showproblem.php?pid=4638
問題其實就是求[L,R]中有多少個連續(xù)的段
若每一個人都是一個段 那么[L,R]中每一個朋友關系就會減少一個段(因為它將兩個段合并了)
我們把每個朋友關系變成一個邊 要求[L,R]有多少個邊 可以用到 離散化+樹狀數(shù)組
把每個朋友關系形成的邊以左端點為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; }
?
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
