VISEMALL - Editoriale

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Flame Storm
Tester: Harris Leung
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Graph Theory, Sets

PROBLEM:

You are given a binary string S of length N.

Let G be a complete directed graph of N vertices numbered from 1 to N. There is a directed edge going from vertex u to v if one of the following is true:

  • S_u = S_v and u \lt v
  • S_u \neq S_v and u \gt v

You will be given Q queries of two different types:

  • 1 L R - Flip all the bits in S in range [L, R] and update G accordingly.
  • 2 L R X - Find whether there is a path that starts from vertex X and visits each vertex in G[L, R] exactly once (a hamiltonian path in other words).

EXPLANATION:

According to the problem, if we are at index i, then all other indexes greater than i and have the bit same as that of the index i, there will be an edge from index i to all these indexes.

As well as all other indexes that are less than index i and have the bit opposite as that of the index i, there will be an edge from index i to all these indexes.

Hence we are at some index, say x, and wants to visit the indexes less than index x we need the opposite bit and hence it makes sense to keep track of those indexes where bits are opposite to each other i.e. index i and index i+1 have opposite bit. In this way, we can easily reach from index i+1 to index i.

Hence we can simply store such indexes i where consecutive bits at index i-1 and i are different, hence for type 1^{st} query, how can we store such indexes quickly, and then we will move to type 2 query:

  • For the 1^{st} type query, we are given a range [L, R] now let’s visualize what will happen at index L. If the index L-1 and L were having the same bits, then we can see that after flipping the bits we need to add index L in the set as this will lead to the different bits at index L and L+1. If they were opposite bits before flipping off the bit at index L, then we need to remove index L as this will lead to the same bits at both indexes.

  • Now let’s see what will happen at the index L+1 to index R-1, we can clearly see that since every bit will be flipped hence there won’t be any index where the patter (same or opposite) will change,

  • For index R, if index R and index R+1 have the same bit then simply add index R+1 to the set otherwise remove it. Why? You know right.

Now, let’s see how this is going to help for answering the second query:

  • Let’s say we start from the index X, then if there is only one type of bits from index L+1 to index R i.e there is no element in the set of this given range. Hence we can say that in this case, the path will only exist when your X is nothing but equal to L.

  • Now let’s say there are more than one indexes that have the opposite bits to that of its previous index in the range [L+1, R], then you easily traverse the graph as you can cover the same indexes and then you can go back as there are more than one indexes and then visit the remaining indexes.

  • Now let’s see if there is only one index that has opposite bits to that of its previous index in the range [L+1, R]. Then if X is equal to the index where this single bit has been flipped as well it shouldn’t be equal to L, then you can easily visit the whole graph, otherwise, you won’t be able to visit the graph.

TIME COMPLEXITY:

O(Q*log(N)

SOLUTIONS:

Setter 
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int n ,q;
    scanf("%d%d",&n,&q);
    string s(n ,'0');
    scanf("%s",s.c_str());
 
    set <int> c{n};
    for(int i = 1; i < n; i++)
        if(s[i] != s[i-1])
            c.insert(i);
 
    while(q--){
        int tp ,l ,r ,x;
        scanf("%d%d%d",&tp,&l,&r) ,l-- ,r--;
        if(tp == 2){
            scanf("%d",&x) ,x--;
 
            int b = 1;
            auto it = c.upper_bound(l);
            while(*it <= r && b < 3)
                it = next(it) ,b++;
 
            if((b >= 3) || (b == 2 && x != l && x == *prev(it)) || (b == 1 && x == l))
                printf("yeS\n");
            else
                printf("No\n");
        }else{
            for(int x : {l ,r+1}) if(0 < x && x < n){
                if(c.count(x)) c.erase(x);
                else c.insert(x);
            }
        }
    }
}
Tester 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=5e5+1;
int n,q;
int hv[1<<20][2];
int lz[1<<20];
char a[N];
void push(int id){
	if(lz[id]){
		swap(hv[id*2][0],hv[id*2][1]);
		swap(hv[id*2+1][0],hv[id*2+1][1]);
		lz[id*2]^=1;
		lz[id*2+1]^=1;
		lz[id]=0;
	}
}
void upd(int id,int l,int r,int ql,int qr){
	if(l>qr || r<ql) return;
	if(ql<=l && r<=qr){
		lz[id]^=1;
		swap(hv[id][0],hv[id][1]);
		return;
	}
	push(id);
	int mid=(l+r)/2;
	upd(id*2,l,mid,ql,qr);
	upd(id*2+1,mid+1,r,ql,qr);
	hv[id][0]=hv[id*2][0]|hv[id*2+1][0];
	hv[id][1]=hv[id*2][1]|hv[id*2+1][1];
}
pair<int,int>qry(int id,int l,int r,int ql,int qr){
	if(l>qr || r<ql) return {0,0};
	if(ql<=l && r<=qr) return {hv[id][0],hv[id][1]};
	push(id);
	int mid=(l+r)/2;
	auto res1=qry(id*2,l,mid,ql,qr);
	auto res2=qry(id*2+1,mid+1,r,ql,qr);
	return {res1.fi|res2.fi,res1.se|res2.se};
}
int qry2(int id,int l,int r,int ql,int qr,int fuck){
	if(l>qr || r<ql) return r+1;
	if(ql<=l && r<=qr && !hv[id][1-fuck]) return r+1;
	if(l==r){
		if(hv[id][fuck]) return l+1;
		else return l;
	}
	push(id);
	int mid=(l+r)/2;
	int diu=qry2(id*2,l,mid,ql,qr,fuck);
	if(diu!=mid+1) return diu;
	return qry2(id*2+1,mid+1,r,ql,qr,fuck);
}
void build(int id,int l,int r){
	if(l==r){
		hv[id][a[l]-48]=true;
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	hv[id][0]=hv[id*2][0]|hv[id*2+1][0];
	hv[id][1]=hv[id*2][1]|hv[id*2+1][1];
}
bool solve(int l,int r,int x){
	auto res=qry(1,1,n,l,r);
	//cout << res.fi << ' ' << res.se << endl;
	if(res.fi*res.se==0) return (l==x);
	int fuck=qry(1,1,n,l,l).se;
	int sp=qry2(1,1,n,l,r,fuck);
	//cout << "split " << sp << endl;
	res=qry(1,1,n,sp,r);
	if(res.fi*res.se) return true;
	else return (sp==x);
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> n >> q;
	for(int i=1; i<=n ;i++) cin >> a[i];
	build(1,1,n);
	for(int i=1; i<=q ;i++){
		int t;cin >> t;
		if(t==1){
			int l,r;cin >> l >> r;
			upd(1,1,n,l,r);
		}
		else{
			int l,r,x;cin >> l >> r >> x;
			auto ans=solve(l,r,x);
			if(ans) cout << "YES\n";
			else cout << "NO\n";
			//cout << endl;
		}
	}
}
2 Likes