Shopee code League 2022 - qualification round p3.connecting the numbers (segment tree / bipartite graph determination, to be discussed)

subject

t(t<=50) Group example , Each time a length of 2*n(n<=1e5) Sequence , And each 1 To n The number of occurs exactly twice ,

Evenly spaced on the ring 1 To 2*n this 2*n A little bit , Points with the same value either have edges in the ring , Or connect the edge outside the ring ,

Ask whether a given sequence can be connected , Make the two sides not intersect , If it can output yes, Otherwise output no

A little idea of yourself

Official solution , A counterexample has been found

1 
4 
1 2 3 2 4 3 1 4

Teammates asked for advice @ Brother pan Bai , Come up with a chairman tree approach

  I thought carefully again , I feel like this chairman tree , It doesn't seem necessary

therefore , According to this chairman tree , The practice of rolling up a line segment tree

Ideas

The interval corresponding to each value is processed into [li,ri] In the form of , Press l Sequence of elimination and increase ,

If the intersecting line segment is regarded as two adjacent points , You might as well blacken it and think it's connected from the outside , Tu Bai believes that from the inside ,

Then the problem is equivalent to if two intersecting segments are connected , The last graph is a bipartite graph , violence check yes O(n^2) Of

therefore , Consider if [li,ri] and [lj,rj] The intersection (i<j), namely li<lj<ri<rj The situation of , Only make j->i One side

That is, each line segment i, Just think about it , And i Intersect and the right endpoint is ri The line segment on the left j

Just scan it first , Insert all positions into the segment tree ,

Line segment i Our contribution lies in ri The location of , This only includes ri The line segment of can and i The intersection

Delete it backwards again , Color each line segment ,

1. If the line segment has no color or is already white , Check whether all adjacent points have no color or have been black ,

" , Then dye all adjacent points black , Dye the current dot white

2. If the line segment has no color or is already black , Check whether all adjacent points have no color or have been white ,

" , Then dye all adjacent points white , Dye the current Dot BLACK

3. If the above two situations are not satisfied , unsolvable

4. Delete the current node , Prevent the subsequent impact caused by the inclusion of line segments ,

Because the follow-up is to check the whole interval , Such as interval [2,3]、[1,4],

check [1,4] You may find [2,3], But the two are inclusive , There is no limit to the relationship of edges

At the end

At present, it just runs against the dichotomy , The data is random , Will be weaker

Some students found a weak version of the original question poj3207, I changed the input and output. I handed it in once

But I'm still a little uncertain about its correctness , So if a netizen finds that the code has bug Or the direct practice is false , Welcome to leave comments directly

Line tree code O(nlogn)

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=1e5+10;
const int NOCOLOR=0,BLACK=1,WHITE=2;
// Segment tree judgement bipartite graph 
//segment biparpite grpah judge
struct segtree3{
	int n;
	struct node{int l,r,v,b,w,c;}e[N<<2];
	#define l(p) e[p].l
	#define r(p) e[p].r
	#define v(p) e[p].v // black+white
    #define b(p) e[p].b // black
    #define w(p) e[p].w // white
    #define c(p) e[p].c //  Overlay mark  1 According to black  2 Said the white  coverFlag while 1 means black and 2 means white 
	void up(int p){
        v(p)=v(p<<1)+v(p<<1|1);
        b(p)=b(p<<1)+b(p<<1|1);
        w(p)=w(p<<1)+w(p<<1|1);
    }
	void bld(int p,int l,int r){
		l(p)=l;r(p)=r;c(p)=NOCOLOR;
		if(l==r){v(p)=NOCOLOR;b(p)=w(p)=0;return;}
		int mid=l+r>>1;
		bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);
		up(p);
	}
	void init(int _n){n=_n;bld(1,1,n);}
    void psd(int p){
        if(!v(p))return;
        if(c(p)==BLACK){//black
            c(p<<1)=c(p);
            c(p<<1|1)=c(p);
            b(p<<1)=v(p<<1);
            b(p<<1|1)=v(p<<1|1);
            w(p<<1)=0;
            w(p<<1|1)=0;
            c(p)=0;
        }
        else if(c(p)==WHITE){//white
            c(p<<1)=c(p);
            c(p<<1|1)=c(p);
            w(p<<1)=v(p<<1);
            w(p<<1|1)=v(p<<1|1);
            b(p<<1)=0;
            b(p<<1|1)=0;
            c(p)=0;
        }
    }
    void addPoint(int p,int x){
        if(l(p)==r(p)){
            v(p)++;
            return;
        }
		int mid=l(p)+r(p)>>1;
        psd(p);
		addPoint(p<<1|(x>mid),x);
        up(p);
    }
    void deletePoint(int p,int x){
		if(l(p)==r(p)){
            if(b(p))b(p)--;
            else if(w(p))w(p)--;
            v(p)--;
            return;
        }
		int mid=l(p)+r(p)>>1;
        psd(p);
        deletePoint(p<<1|(x>mid),x);
        up(p);
	}
    int getColor(int p,int x){
        if(l(p)==r(p)){
            if(!b(p) && !w(p))return NOCOLOR;
            if(b(p))return BLACK;
            if(w(p))return WHITE;
        }
		int mid=l(p)+r(p)>>1;
        psd(p);
		return getColor(p<<1|(x>mid),x);
    }
    void covBlack(int p,int ql,int qr){
        //if(!v(p))return;
		if(ql<=l(p)&&r(p)<=qr){
            b(p)=v(p);
			c(p)=BLACK;
			return;
		}
		psd(p);
		int mid=l(p)+r(p)>>1;
		if(ql<=mid)covBlack(p<<1,ql,qr);
		if(qr>mid)covBlack(p<<1|1,ql,qr);
		up(p);
	} 
    void covWhite(int p,int ql,int qr){
        if(!v(p))return;
		if(ql<=l(p)&&r(p)<=qr){
            w(p)=v(p);
			c(p)=WHITE;
			return;
		}
		psd(p);
		int mid=l(p)+r(p)>>1;
		if(ql<=mid)covWhite(p<<1,ql,qr);
		if(qr>mid)covWhite(p<<1|1,ql,qr);
		up(p);
	}
	bool allBlack(int p,int ql,int qr){
		if(ql<=l(p)&&r(p)<=qr){
            return w(p)==0;
        }
		int mid=l(p)+r(p)>>1;
        psd(p);
		if(ql<=mid && !allBlack(p<<1,ql,qr))return 0;
		if(qr>mid && !allBlack(p<<1|1,ql,qr))return 0;
		return 1;
	}
    bool allWhite(int p,int ql,int qr){
		if(ql<=l(p)&&r(p)<=qr){
            return b(p)==0;
        }
		int mid=l(p)+r(p)>>1;
        psd(p);
		if(ql<=mid && !allWhite(p<<1,ql,qr))return 0;
		if(qr>mid && !allWhite(p<<1|1,ql,qr))return 0;
		return 1;
	}
}seg;
int T,n,v,pos[M];
struct node{
    int l,r;
    node(){}
    node(int a,int b){l=a;r=b;}
}e[M];
bool operator<(node a,node b){
    return a.l<b.l;
}
int main(){
    //freopen("data.txt","r",stdin);
    //freopen("segmentTree.txt","w",stdout);
    scanf("%d",&T);
    while(T--){
        memset(pos,0,sizeof pos);
        scanf("%d",&n);
        int c=0;
        for(int i=1;i<=2*n;++i){
            scanf("%d",&v);
            if(!pos[v])pos[v]=i;
            else e[++c]=node(pos[v],i);
        }
        sort(e+1,e+n+1);
        seg.init(2*n);
        for(int i=1;i<=n;++i){
            seg.addPoint(1,e[i].r);
        }
        bool ok=1;
        for(int i=n;i>=1;--i){
            int col=seg.getColor(1,e[i].r);
            if(col!=BLACK && seg.allBlack(1,e[i].l,e[i].r-1)){
                //  If the current point is not black , And the adjacent points are black or colorless , Dye the current spot white , All adjacent points are dyed black 
                // if current node is not black and adjacant node is black(or no color), color current white and adjacant black
                // seg.addWhite(1,e[i].r);  There is no need to actually dye , And i Adjacent edges are checked at this moment 
                // we needn't color current code actually cause after considering these edges, current node is isolated.
                seg.covBlack(1,e[i].l,e[i].r-1);
            }
            else if(col!=WHITE && seg.allWhite(1,e[i].l,e[i].r-1)){
                //  If the current point is not white , And the adjacent points are white or colorless , Dye the current Dot BLACK , All adjacent points are dyed white 
                // if current node is not white and adjacant node is white(or no color), color current black and adjacant white
                //seg.addBlack(1,e[i].r);  There is no need to actually dye , And i Adjacent edges are checked at this moment 
                // we needn't color current code actually cause after considering these edges, current node is isolated.
                seg.covWhite(1,e[i].l,e[i].r-1);
            }
            else{//  No solution  no solution
                ok=0;
                break;
            }
            //  And i The intersecting interval is checked at this moment , Prevent impact on the included situation （ Such as [2,3]、[1,4], At this time, it should be deleted [2,3]）
            // Prevent the influence on the situation where A segment is included in B segment. When [2,3] contains in [1,4], we should delete [2,3] here
            seg.deletePoint(1,e[i].r);
        }
        puts(ok?"yes":"no");
    }
    return 0;
}

Bipartite graph code O(n^2)

#include <bits/stdc++.h>
using namespace std;
const int M=1e5+10;
int T,n,v,pos[M],col[M];
struct node{
    int l,r;
    node(){}
    node(int a,int b){l=a;r=b;}
}e[M];
vector<int>f[M];
bool dfs(int u,int c){
    col[u]=c;
    for(auto &v:f[u]){
        if(col[v]==c)return 0;
        if(!col[v] && !dfs(v,-c))return 0;
    }
    return 1;
}
int main(){
    //freopen("data.txt","r",stdin);
    //freopen("biPartiteGragh.txt","w",stdout);
    scanf("%d",&T);
    while(T--){
        memset(pos,0,sizeof pos);
        memset(col,0,sizeof col);
        scanf("%d",&n);
        int c=0;
        for(int i=1;i<=2*n;++i){
            scanf("%d",&v);
            if(!pos[v])pos[v]=i;
            else e[++c]=node(pos[v],i);
        }
        for(int i=1;i<=n;++i){
            f[i].clear();
        }
        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;++j){
                if(e[i].l<e[j].l && e[j].r<e[i].r)continue;// contain  contain
                if(e[j].l<e[i].l && e[i].r<e[j].r)continue;// contain  contain
                if(max(e[i].l,e[j].l)<min(e[i].r,e[j].r)){// The intersection  intersect
                    //printf("i:%d (%d,%d) j:%d (%d,%d)\n",i,e[i].l,e[i].r,j,e[j].l,e[j].r);
                    f[i].push_back(j);
                    f[j].push_back(i);
                }
            }
        }
        bool ok=1;
        for(int i=1;i<=n;++i){
            if(!col[i]){
                ok&=dfs(i,1);
                if(!ok)break;
            }
        }
        puts(ok?"yes":"no");
    }
    return 0;
}

Generate data code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define random(l,r) (rand()%(r-l)+l)
int t,n,a[N];
int main(){
    srand(time(0));
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    t=10;
    freopen("data.txt","w",stdout);
    printf("%d\n",t);
    while(t--){
        n=random(5,10);
        for(int i=1;i<=n;++i){
            a[2*i-1]=a[2*i]=i;
        }
        random_shuffle(a+1,a+2*n+1);
        printf("%d\n",n);
        for(int i=1;i<=2*n;++i){
            printf("%d%c",a[i]," \n"[i==2*n]);
        }
    }
	return 0;
}