当前位置: 代码迷 >> 综合 >> 【线段树】「CodePlus 2018 3 月赛」白金元首与克劳德斯
  详细解决方案

【线段树】「CodePlus 2018 3 月赛」白金元首与克劳德斯

热度:104   发布时间:2023-09-27 04:33:30.0

题意:

【线段树】「CodePlus 2018 3 月赛」白金元首与克劳德斯

分析:

题意好鬼扯。。。

非常傻逼的线段树动态开点题。

横向移动的矩形和纵向移动的矩形,看起来非常麻烦。

由于速度均相等,所以可以以所有纵向移动的矩形为参考系,那么所有纵向移动的矩形都是相对静止的。而此时横向移动的矩形就变成了沿主对角线移动(左上至右下),那么就可以旋转坐标系,变成简单的线段覆盖问题了。

即:把每个纵向移动的矩形视为(x+y,x+w+y+h)(x+y,x+w+y+h)(x+y,x+w+y+h)的线段,然后横向移动的视为(x′+y′,x′+w′+y′+h′)(x'+y',x'+w'+y'+h')(x+y,x+w+y+h)的询问,只要任意一个询问的区间中,有某个点被线段覆盖了,那么答案就是2,否则答案就是1。

顺便提供一下用于评测本题的网站:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 100010
#define INF 2000000000
using namespace std;
struct node{
    int pl,pr;bool flag;	
}tree[MAXN*40];
pair<int,int> line[MAXN];
int rt=1,ncnt=1;
void add_line(int id,int l,int r,int l1,int r1){
    if(l>=l1&&r<=r1){
    tree[id].flag=1;return ;}int mid=1ll*(l+r)>>1ll;if(l1<=mid){
    if(tree[id].pl==0){
    tree[id].pl=++ncnt;tree[ncnt].pl=tree[ncnt].pr=0;}add_line(tree[id].pl,l,mid,l1,r1);}if(r1>mid){
    if(tree[id].pr==0){
    tree[id].pr=++ncnt;tree[ncnt].pl=tree[ncnt].pr=0;}add_line(tree[id].pr,mid+1,r,l1,r1);	}tree[id].flag=(tree[tree[id].pl].flag)&(tree[tree[id].pr].flag);
}
bool query(int l1,int r1,int id=1,int l=-INF,int r=INF){
    if(tree[id].flag==1)return 1;if(l>=l1&&r<=r1)return 1;int mid=1ll*(l+r)>>1ll;if(l1<=mid&&tree[id].pl!=0){
    if(query(l1,r1,tree[id].pl,l,mid))return 1;}if(r1>mid&&tree[id].pr!=0){
    if(query(l1,r1,tree[id].pr,mid+1,r))return 1;}return 0;
}
int main(){
    int t,n,cnt;SF("%d",&t);while(t--){
    SF("%d",&n);cnt=0;ncnt=1;tree[rt].pl=tree[rt].pr=0;int x,y,w,h,d;for(int i=1;i<=n;i++){
    SF("%d%d%d%d%d",&x,&y,&w,&h,&d);if(d==0)line[++cnt]=make_pair(x+y,x+y+w+h);	elseadd_line(rt,-INF,INF,x+y,x+y+w+h);}int ans=1;for(int i=1;i<=cnt;i++)if(query(line[i].first+1,line[i].second-1)){
    ans=2;break;}PF("%d\n",ans);}
}
  相关解决方案