亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

hdu 4638 Group

系統(tǒng) 1741 0

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;

}


    

?

hdu 4638 Group


更多文章、技術交流、商務合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯(lián)系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發(fā)表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 国产五月色综合 | 99久久免费国产精品热 | 国产一区福利 | 天天操天天摸天天射 | 在线欧洲成人免费视频 | 久久久久久久亚洲精品一区 | 免费观看国产精品 | 欧美日韩在线精品成人综合网 | 男女很黄很色床视频网站免 | 99热久久这里就有精品 | 日本老熟妇激情毛片 | 99久久精品国产一区二区成人 | 成人在线免费观看 | 国产视频久久久久 | 狠狠热精品免费观看 | 伊人久久一本大道 | 精品国产线拍大陆久久尤物 | 欧美亚洲一区二区三区在线 | 亚洲啪视频 | 不卡国产 | 青青草久热精品视频在线观看 | 久久久久国产精品免费免费 | 国产91精品福利在线观看 | 色欧美亚洲 | 手机在线看片福利 | 亚洲精品中文字幕久久久久久 | 欧美一区二区手机在线观看视频 | 91www成人久久 | 综合 欧美 国产 视频二区 | 久久久精品久久 | 亚洲欧美成人综合久久久 | 91香蕉国产亚洲一区二区三区 | 亚洲日本aⅴ片在线观看香蕉 | 欧美一区二区三区成人看不卡 | 综合视频网 | 久久影院朴妮唛 | 国产精品福利久久香蕉中文 | 可以免费观看一级毛片黄a 可以直接看的毛片 | 精品一区二区三区视频在线观看 | 福利影院在线 | 国内精品久久久久久 |