【悬 2 关】线段树 50pts 求调
查看原帖
【悬 2 关】线段树 50pts 求调
737242
linch吃瓜猫楼主2025/7/28 19:23

rt,50pts,根据第一篇题解思路写。

:::error[错误代码]{open}

#include<bits/stdc++.h>
using namespace std;
int n;
const int maxn=1e5+10;
bool vis[3][maxn],l[maxn<<2],r[maxn<<2],p[maxn<<2],q[maxn<<2],f[maxn<<2],g[maxn<<2];
//以下数组分别表示:左上--左下,右上--右下, 左上--右下, 左下--右上, 左上--右上,左下--右下。
struct node{
    int l,r,p,q,f,g;
};
void push_up(int id,int s,int t){
    int mid=s+t>>1;
    l[id]=l[id<<1]|(f[id<<1]&vis[1][mid]&l[id<<1|1]&vis[2][mid]&g[id<<1]);
    r[id]=r[id<<1|1]|(f[id<<1|1]&vis[1][mid]&r[id<<1]&vis[2][mid]&g[id<<1|1]);
    f[id]=(f[id<<1]&vis[1][mid]&f[id<<1|1])|(p[id<<1]&vis[2][mid]&q[id<<1|1]);
    g[id]=(g[id<<1]&vis[2][mid]&g[id<<1|1])|(q[id<<1]&vis[1][mid]&p[id<<1|1]);
    p[id]=(f[id<<1]&vis[1][mid]&p[id<<1|1])|(p[id<<1]&vis[2][mid]&g[id<<1|1]);
    q[id]=(g[id<<1]&vis[2][mid]&q[id<<1|1])|(q[id<<1]&vis[1][mid]&f[id<<1|1]);
}
void build(int id,int s,int t){
    if(s==t){
        f[id]=g[id]=1;
        return;
    }
    int mid=s+t>>1;
    build(id<<1,s,mid);
    build(id<<1|1,mid+1,t);
    push_up(id,s,t);
}
void update1(int x,int y,int s,int t,int id,int val){
    if(s==y && t==y){
        l[id]=r[id]=p[id]=q[id]=val;
        return;
    }
    int mid=s+t>>1;
    if(y<=mid) update1(x,y,s,mid,id<<1,val);
    else update1(x,y,mid+1,t,id<<1|1,val);
    push_up(id,s,t);
}
void update2(int x,int y,int s,int t,int id,int val){
    int mid=s+t>>1;
    if(y==mid){
        vis[x][y]=val;
        push_up(id,s,t);
        return;
    }
    if(y<=mid) update2(x,y,s,mid,id<<1,val);
    else update2(x,y,mid+1,t,id<<1|1,val);
    push_up(id,s,t);
}
node query(int id,int a,int b,int s,int t){
    if(s>=a && t<=b) return {l[id],r[id],p[id],q[id],f[id],g[id]};
    int mid=s+t>>1;
    if(b<=mid) return query(id<<1,a,b,s,mid);
    if(a>mid) return query(id<<1|1,a,b,mid+1,t);
    query(id<<1,a,b,s,mid);
    query(id<<1|1,a,b,mid+1,t);
    push_up(id,s,t);
    return {l[id],r[id],p[id],q[id],f[id],g[id]};
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    build(1,1,n);
    string op;
    cin>>op;
    while(op!="Exit"){
        int r1,c1,r2,c2;
        cin>>r1>>c1>>r2>>c2;
        if(op=="Close"){
            if(r1==r2) update2(r1,min(c1,c2),1,n,1,0);
            else update1(r1,min(c1,c2),1,n,1,0);
        }
        else if(op=="Open"){
            if(r1==r2) update2(r1,min(c1,c2),1,n,1,1);
            else update1(r1,min(c1,c2),1,n,1,1);
        }
        else{
            if(c1>c2) swap(c1,c2),swap(r1,r2);
            node ans1=query(1,c1,c2,1,n);
            node ans2=query(1,1,c1,1,n);
            node ans3=query(1,c2,n,1,n);
            bool flag=false;
            if(r1==1){
                if(r2==1) flag=ans1.f|(ans2.r&ans1.g&ans3.l);
                else flag=ans1.p|(ans2.r&ans1.g)|(ans3.l&ans1.f);
            }
            else{
                if(r2==2) flag=ans1.g|(ans2.r&ans1.f&ans3.l);
                else flag=ans1.q|(ans2.r&ans1.f)|(ans3.l&ans1.g);
            }
            cout<<(flag?"Y":"N")<<"\n";
        }
        cin>>op;
        
    }
    return 0;
}

:::

评测记录:https://www.luogu.com.cn/record/227428456

2025/7/28 19:23
加载中...