题解：P11619 [PumpkinOI Round 1] 种南瓜

· · 题解

转化成每次可以增删一条线段，判断是否满足每条线段都包含或不包含或不相交。

每条线段会出现和消失，想到线段树分治。现在只需要判断每次加入的线段是否满足要求即可。先处理被此线段完全包含的线段。建一颗用于查区间异或值的线段树，每次加入一条线段时将这条线段左右端点的位置都异或上一个随机值。如果 l,r 内的所有线段都被 l,r 包含，那么区间 [l,r] 内数的异或值为 0。

发现这样无法处理到与此线段共用一个端点且完全包含此线段的线段。那么在每个点处开一棵线段树，那么合法的条件就是 [l,r] 中异或值异或 l 处线段树 [r+1,n] 内的异或值再异或 r 处线段树 [1,l-1] 内的异或值为 0。复杂度 O(n\log n\log q)。

代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+100;
int n,m;
mt19937 rd(time(0));
struct seg
{
    int l,r,val;
}u[N];
vector<seg> s[N*4];
#define ll (x<<1)
#define rr (x<<1|1)
#define mid ((l+r)>>1)
namespace sg
{
    int t[N*4];
    inline void insert(int pos,int l,int r,int x,int val)
    {
        t[x]^=val;
        if(l==r)return;
        if(pos<=mid)insert(pos,l,mid,ll,val);
        else insert(pos,mid+1,r,rr,val);
    }
    inline int get(int l1,int r1,int l,int r,int x)
    {
        if(l>=l1&&r<=r1)return t[x];
        int res=0;
        if(l1<=mid)res^=get(l1,r1,l,mid,ll);
        if(r1>mid)res^=get(l1,r1,mid+1,r,rr);
        return res;
    }
}
using namespace sg;
inline void add(int l1,int r1,int l,int r,int x,seg v)
{
    if(l>=l1&&r<=r1){s[x].push_back(v);return;}
    if(l1<=mid)add(l1,r1,l,mid,ll,v);
    if(r1>mid)add(l1,r1,mid+1,r,rr,v);
}
map<pair<int,int>,int> mp;
struct node
{
    int x;
    node *ls,*rs;
    node(){x=0;ls=rs=0;}
    inline void insert(int pos,int l,int r,int val)
    {
        x^=val;
        if(l==r)return;
        if(pos<=mid)(ls?ls:ls=new node)->insert(pos,l,mid,val);
        else (rs?rs:rs=new node)->insert(pos,mid+1,r,val);
    }
    inline int get(int l1,int r1,int l,int r)
    {
        if(l1>r1)return 0;
        if(l>=l1&&r<=r1)return x;
        int res=0;
        if(ls&&l1<=mid)res^=ls->get(l1,r1,l,mid);
        if(rs&&r1>mid)res^=rs->get(l1,r1,mid+1,r);
        return res;
    }
}tl[N],tr[N];
inline void work(int l,int r,int x,bool ok)
{
    bool tmp=ok;
    if(tmp)
    for(auto i:s[x])
    {
        if(get(i.l,i.r,1,n,1)^tl[i.l].get(i.r+1,n,1,n)^tr[i.r].get(1,i.l-1,1,n))ok=0;
        insert(i.l,1,n,1,i.val);
        insert(i.r,1,n,1,i.val);
        tl[i.l].insert(i.r,1,n,i.val);
        tr[i.r].insert(i.l,1,n,i.val);
    }
    if(l==r)
        cout<<(ok?"Yes\n":"No\n");
    else work(l,mid,ll,ok),work(mid+1,r,rr,ok);
    if(tmp)
    for(auto i:s[x])
    {
        insert(i.l,1,n,1,i.val);
        insert(i.r,1,n,1,i.val);
        tl[i.l].insert(i.r,1,n,i.val);
        tr[i.r].insert(i.l,1,n,i.val);
    }
}
#undef ll
#undef rr
#undef mid
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int op,x,y;
    set<int> tmp;
    for(int i=1;i<=m;i++)
    {
        cin>>op;
        if(op==1)cin>>x>>y,tmp.insert(i),u[i]={x,y,rd()};
        else cin>>x,tmp.erase(x),add(x,i-1,1,m,1,u[x]);
    }
    for(auto i:tmp)add(i,m,1,m,1,u[i]);
    work(1,m,1,1);
}