POJ 1436 Horizontally Visible Segments

线段树成段替换+暴力枚举

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn=8000+10;
int S,T,n,ans,tot;
bool flag[maxn][maxn];
struct Line
{
    int y1,y2,x;
} line[maxn];
int segTree[16000*4+10];

bool cmp(const Line&a,const Line&b)
{
    return a.x<b.x;
}

void pushdown(int rt)
{
    if(segTree[rt])
    {
        segTree[rt*2]=segTree[rt];
        segTree[rt*2+1]=segTree[rt];
        segTree[rt]=0;
    }
}

void update(int L,int R,int sign,int l,int r,int rt)
{
    if(l>=L&&r<=R)
    {
        segTree[rt]=sign;
        return;
    }
    pushdown(rt);
    int m=(l+r)/2;
    if(L<=m) update(L,R,sign,l,m,2*rt);
    if(R>m) update(L,R,sign,m+1,r,2*rt+1);

}

void get(int L,int R,int l,int r,int rt)
{
    if(segTree[rt]!=0)
    {
        if(!flag[S][segTree[rt]])
            flag[S][segTree[rt]]=1;
        return;
    }
    if(l==r) return;
    int m=(l+r)/2;
    if(L<=m) get(L,R,l,m,rt*2);
    if(R>m)  get(L,R,m+1,r,rt*2+1);
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        memset(segTree,0,sizeof segTree);
        memset(flag,0,sizeof flag);
        for(int i=0; i<n; i++)
        {
            scanf("%d%d%d",&line[i].y1,&line[i].y2,&line[i].x);
            line[i].y1++;
            line[i].y1=line[i].y1*2;
            line[i].y2++;
            line[i].y2=line[i].y2*2;
        }

        sort(line,line+n,cmp);

        for(int i=0; i<n; i++)

        {
            S=i+1;
            get(line[i].y1,line[i].y2,1,16000+10,1);
            update(line[i].y1, line[i].y2, i+1,1,16000+10,1);
        }

        ans=0;
        for(int i=1; i<=n; ++i)
        {
            for(int j=1; j<=n; ++j)
            {
                if(flag[i][j])
                    for(int k=1; k<=n; ++k)
                    {
                        if(flag[i][k] && flag[j][k])++ans;
                    }
            }
        }
        printf("%d
",ans);
    }
    return 0;
}