程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Beta Round #12 D. Ball (線段樹)

Codeforces Beta Round #12 D. Ball (線段樹)

編輯:C++入門知識

Codeforces Beta Round #12 D. Ball (線段樹)


題目大意:

n個女性中,如果有一個女性的三維比這個女性的三維都大,這個女性就要自殺。問要自殺多少個。


思路分析:

先按照第一維排序。

然後離散化第二維,用第二維的下標建樹,樹上的值是第三維,更新的時候取最大值。

注意是按照第一維度從大到小進入線段樹。

而且還要嚴格遞增。

所以處理第一維度比較大小的時候要分開處理,要把相同的先判斷,再更新入樹。

那麼如何判斷這個女性是否自殺。

首先,你知道第一維度是從大到小的,所以先進樹了的節點的第一維度一定更大。

再次,我們考慮第二維度,我們去樹上第二維度下標大的節點區去尋找第三維度。

如果有一個比這個的第三維度大,那麼就滿足。


#include 
#include 
#include 
#include 
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define maxn 500005

using namespace std;

struct node
{
    int a,b,c;
    bool operator < (const node &cmp)const
    {
        if(a!=cmp.a)return a>1;
    build(lson);build(rson);
}
void update(int num,int s,int e,int pos,int val)
{
    if(s==e)
    {
        res[num]=max(res[num],val);
        return;
    }
    int mid=(s+e)>>1;
    if(pos<=mid)update(lson,pos,val);
    else update(rson,pos,val);
    pushup(num);
}
int query(int num,int s,int e,int l,int r)
{
    if(l<=s  && r>=e)return res[num];
    int mid=(s+e)>>1;
    if(r<=mid)return query(lson,l,r);
    else if(l>mid)return query(rson,l,r);
    else return max(query(lson,l,mid),query(rson,mid+1,r));
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&wm[i].a);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&wm[i].b);
        x[i]=wm[i].b;
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&wm[i].c);

    sort(wm+1,wm+1+n);

    sort(x+1,x+1+n);

    int m=unique(x+1,x+1+n)-x;
    m--;

    int last=wm[n].a;
    int r=n;
    int l=n;
    int ans=0;

    wm[0].a=0x3f3f3f3f;

    for(int i=n;i>=1;)
    {
        while(wm[l].a==last)
        {
            l--;
        }
        int c=r;
        while(c>l)
        {
            int pos=lower_bound(x+1,x+m+1,wm[c].b)-x;
            if(pos+1<=m && query(1,1,m,pos+1,m)>wm[c].c)ans++;
            c--;
        }
        c=r;
        while(c>l)
        {
            int pos=lower_bound(x+1,x+m+1,wm[c].b)-x;
            update(1,1,m,pos,wm[c].c);
            c--;
        }
        i=l;r=l;last=wm[i].a;
    }
    printf("%d\n",ans);
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved