CF1599I Desert / Original question link

meaning of the title

Cactus is an undirected connected graph. On a cactus, any edge will only appear on one ring at most.

Desert is an undirected graph. Each maximal connected component of a desert is a cactus.

Given an undirected graph with \ (n \) points \ (m \) edges, find how many pairs \ (l,r\in [1,m] \) there are, so that after only the edges numbered in \ ([l,r] \) are retained, the graph becomes a desert.

Data range: \ (n\le 2.5\times 10^5,m\le 5\times 10^5 \)

solution

Change the topic and use the two pointer method to maintain two pointers \ (l,r \), which means that \ ([l,r] \) is a legal interval. Then when \ (r \) moves to the right, we add an edge\ (L \) when moving right, we delete the edge.

Then you can use Link Cut Cactus to maintain the addition and deletion of edges. But I can't LCC, so I use LCT to maintain it.

LCT does not support the maintenance of edge information. Just remove the edge point and set it as \ (E \) point.

Two values \ (val=0/1,tot \) are maintained on the LCT, which in turn represent whether the \ (E \) point is in a ring and whether the subtree of this point has a \ (E \) point in the ring.

Edging

Add the \ (r \) side \ ((x,y) \). If \ (x,y \) is not connected, just join directly. If Unicom is connected, query whether there are \ (E \) points in the ring between \ (x,y \) (that is, query \ (tot \) of the Splay root node of \ (x \ SIM, y \).

• *If not, these \ (E \) points become edges in the ring after adding edges. Set their \ (val \) to 1 and maintain them with lazytag. At the same time, maintain a value \ (id \) to represent which side \ (val=1 \) comes from. The \ (id:=r \) of \ (x\sim y \) will also be maintained with lazytag. The specific reasons will be described below.
• If yes, adding an edge will cause the edge corresponding to the \ (E \) point to be in two rings at the same time (one is the edge added now and the other is the edge of \ (val=1 \) previously). It is not a desert. Delete the edges continuously \ (l:=l+1 \) until it is found that this situation does not occur.

Delete edge

Set and delete the \ (l \) side \ ((x,y) \). If \ (x,y \) is connected, cut it directly.

But there will be mistakes in doing so. If \ (x,y \) is in a ring before, but LCT is not added to the ring edge (in the case with * above), information will be lost. We can add the edge corresponding to \ (id \) of the root into the LCT and clear \ (id \).

If it is not connected, then the edge plus edge is the case with *. Let's put the Splay of \ (x \ SIM, y \), \ (val:=0,id:=0 \). Maintenance with lazytag.

Time complexity \ (O(nlogn) \). (\ (n \) is the total number of points after disassembly)

code

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define lsn(o) tre[o].son[0]
#define rsn(o) tre[o].son[1]
using namespace std;
const int n7=1012345,m7=n7;
struct dino{int x,y;}e[m7];
struct mist{int fa,son[2];int laz,id,lazid;bool val,tot,fp;}tre[n7];
int n,m;long long ans;

int rd(){
	int shu=0;bool fu=0;char ch=getchar();
	while( !isdigit(ch) ){if(ch=='-')fu=1;ch=getchar();}
	while( isdigit(ch) )shu=(shu<<1)+(shu<<3)+ch-'0',ch=getchar();
	return fu?-shu:shu;
}

void updat(int o){
	tre[o].tot=(tre[lsn(o)].tot|tre[rsn(o)].tot);
	if(o>n)tre[o].tot|=tre[o].val;
}

void pudown(int o){
	if(tre[o].laz==1){
		tre[lsn(o)].val=tre[rsn(o)].val=1;
		tre[lsn(o)].tot=tre[rsn(o)].tot=1;
		tre[lsn(o)].laz=tre[rsn(o)].laz=1;
	}
	if(tre[o].laz==-1){
		tre[lsn(o)].val=tre[rsn(o)].val=0;
		tre[lsn(o)].tot=tre[rsn(o)].tot=0;
		tre[lsn(o)].laz=tre[rsn(o)].laz=-1;
	}
	tre[o].laz=0;
	
	if(tre[o].lazid>0){
		tre[lsn(o)].id=tre[rsn(o)].id=tre[o].lazid;
		tre[lsn(o)].lazid=tre[rsn(o)].lazid=tre[o].lazid;
	}
	if(tre[o].lazid==-1){
		tre[lsn(o)].id=tre[rsn(o)].id=0;
		tre[lsn(o)].lazid=tre[rsn(o)].lazid=-1;
	}
	tre[o].lazid=0;

	if(tre[o].fp){
		tre[lsn(o)].fp^=1,tre[rsn(o)].fp^=1;
		swap( lsn(o),rsn(o) );
		tre[o].fp=0;
	}
	
	tre[0]=(mist){0,{0,0},0,0,0,0,0,0};
}

bool Dwhi(int o){return rsn(tre[o].fa)==o;}

bool izrot(int o){return lsn(tre[o].fa)==o||rsn(tre[o].fa)==o;}

void rota(int o){
	int y=tre[o].fa,z=tre[y].fa,whi=Dwhi(o);
	int fawhi=(izrot(y)?Dwhi(y):-1),v=tre[o].son[!whi];
	tre[v].fa=y,tre[y].son[whi]=v;
	tre[y].fa=o,tre[o].son[!whi]=y;
	tre[o].fa=z;if(~fawhi)tre[z].son[fawhi]=o;
	updat(y),updat(o);
}

void puall(int o){
	if( izrot(o) )puall(tre[o].fa);
	pudown(o);
}

void splay(int o){
	puall(o);
	while( izrot(o) ){
		int y=tre[o].fa;
		if( izrot(y) ){
			Dwhi(o)==Dwhi(y)?rota(y):rota(o);
		}
		rota(o);
	}
}

void aces(int o){
	int las=0;
	while(o){
		splay(o),rsn(o)=las,updat(o);
		las=o,o=tre[o].fa;
	}
}

void Mroot(int o){
	aces(o),splay(o),tre[o].fp^=1;
}

int Froot(int o){
	aces(o),splay(o);
	while( lsn(o) )pudown(o),o=lsn(o);
	splay(o);
	return o;
}

void split(int o1,int o2){
	Mroot(o1),aces(o2),splay(o2);
}

void link(int o1,int o2){
	if( Froot(o1)==Froot(o2) )return;
	Mroot(o1),tre[o1].fa=o2;
}

bool cancut(int o1,int o2){
	if( Froot(o1)^Froot(o2) )return 0;
	split(o1,o2);
	if( tre[o1].fa^o2 || lsn(o1) || rsn(o1) )return 0;
	return 1;	
}

void cut(int o1,int o2){
	if( cancut(o1,o2) )tre[o1].fa=lsn(o2)=0,updat(o2);
}

int Gdot(int now){
	pudown(now);
	int o=lsn(now);
	while(o){
		if(o>n)return o;
		else pudown(o),o=rsn(o);
	}	
	o=rsn(now);
	while(o){
		if(o>n)return o;
		else pudown(o),o=lsn(o);
	}
	return 0;
}

bool check(int o1,int o2){
	if( Froot(o1)^Froot(o2) )return 1;
	split(o1,o2);int o=Gdot(o2);splay(o);
	if(!tre[o].tot)return 1;
	return 0;
}

int main(){
	n=rd(),m=rd();
	rep(i,1,m)e[i]=(dino){rd(),rd()};
	for(int l=1,r=0;r<=m;++r){
		ans=ans+r-l+1;
	//	printf("!%d %d\n",l,r);
		if(r==m)break; 
		while( !check(e[r+1].x,e[r+1].y) ){
			if( !cancut(e[l].x,l+n)  ){
				split(e[l].x,e[l].y);
				int o=Gdot(e[l].y);
				if(o){
					splay(o);
					tre[o].val=tre[o].tot=0,tre[o].laz=-1;
					tre[o].id=0,tre[o].lazid=-1;
				}
			}
			else{
				int z=tre[l+n].id;
				cut(e[l].x,l+n),cut(l+n,e[l].y);
				if(z){					
					link(e[z].x,z+n),link(z+n,e[z].y);
					split(e[l].x,e[l].y);
					int o=Gdot(e[l].y);
					if(o){
						splay(o);
						tre[o].val=tre[o].tot=0,tre[o].laz=-1;
					}
				}
			}
			l++;
		}
		if( Froot(e[r+1].x)==Froot(e[r+1].y) ){
			split(e[r+1].x,e[r+1].y);
			int o=Gdot(e[r+1].y);
			if(o){
				splay(o);			
				tre[o].val=tre[o].tot=1,tre[o].laz=1;
				tre[o].id=tre[o].lazid=r+1;
			}
		}
		else{
			link(e[r+1].x,r+1+n),link(r+1+n,e[r+1].y);		
		}
	}
	printf("%lld",ans);
	return 0;
}