Abc229 summary (connected component count of the longest continuous character graph in the interval)

D - Longest X The prefix and + Double pointer

Carelessness ： A string consists of "X" and "." form , Given n It's an opportunity , One at a time "." become "X".

Find the longest continuous "X" The number of

Ideas ：
Prefixes and statistics "." The number of , Then run with two hands , When the number of operations is greater than or equal to "." Update the interval length as much as possible , Then take the best value .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const ll N=2e5+10;
inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
ll dir[][4]={
   {1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
ll n,m;
ll cnt[N];
char s[N];
ll a,b;
void solve()
{
    cin>>(s);
    cin>>n;
    ll ans=0;
    ll len=strlen(s);
    //cnt[0]=(s[0]=='.');
    for(int i=0;i<len;++i)
    {
    	if(s[i]=='.') cnt[i+1]=cnt[i]+1;
    	else cnt[i+1]=cnt[i];
	}
	//for(int i=0;i<len;++i) cout<<cnt[i]<<' ';
	for(int l=0,r=0;l<len;++l)
	{
		while(r<len&&cnt[r+1]-cnt[l]<=n)
		{
			r++;
		}
		ans=max(ans,(ll)r-l);
	}
	cout<<ans<<endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

G - Longest Y

G Follow D Are two very similar questions , So I want to talk about G

Carelessness ：
It is also a string , The problem follows D It's the same thing , however G The operation of the question becomes that only characters in two adjacent positions can be exchanged , This is the only difference between the two questions .

Ideas ：

The official solution is ingenious ：

If s[i]=='Y',b[++cnt]=i-cnt;
Order array b The element value of is equal to each Y The position of an element minus its bit order （ It's the number one Y）.

If it is two consecutive Y, Their positions are continuously increased 1, The bit order is also added continuously 1, So the two b[i] The values will be equal

Then the problem turns into ：

There's a number b, Each operation can make b The elements inside +1 perhaps -1, Then ask what can make b How many elements are equal in .

Observe carefully b Construction process of , You can find b The elements in are not reduced , That is, they are monotonous , Then we can consider and divide .

The binary object is naturally the interval length of the equivalent element that can be obtained at the maximum , that judge(x) The content of the function is whether it can be in k A length of x The interval of is unified into a value .

To do this , The best strategy must be to move the elements on both sides closer to the elements in the middle , that judge Our judgment is

among mid Is the midpoint of the interval  .

The formula on the left can be optimized , Use prefix and preprocessing , Then calculate the contribution of the left and right parts of the formula respectively

The contribution of the left ：sum1=(mid-l+1)*b[mid]-(sum[mid]-sum[l-1])

The contribution on the right ：sum2=sum[r]-sum[mid-1]-b[mid]*(r-mid+1)

A very simple elementary school mathematics

Then we can be happy ac La

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const ll N=2e5+10;
inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
string s;
ll n;
ll b[N];
ll cnt=0;
ll sum[N];//b And  
bool judge(ll x)
{
	for(int l=1;l+x-1<=cnt;++l)
	{
		ll r=l+x-1;// Left and right boundary 
		ll mid=l+r>>1;// Extreme points 
		ll s1=(mid-l+1)*b[mid]-(sum[mid]-sum[l-1]);
		ll s2=(sum[r]-sum[mid-1])-(r-mid+1)*b[mid];
		if(s1+s2<=n) return 1;
	}
	return 0;
}
void solve()
{
    cin>>(s);
    cin>>n;
    for(int i=0;i<s.size();++i)
    {
    	if(s[i]=='Y')
		{
			b[++cnt]=i+1-cnt; 
		 } 
	}
	for(int i=1;i<=cnt;++i)
	{
		sum[i]=sum[i-1]+b[i];
	}
	ll l=0,r=cnt;
	while(l<=r)
	{
		ll mid=l+r>>1;
		if(judge(mid)) l=mid+1;
		else r=mid-1;
	}
	cout<<l-1<<endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
	return 0;
}

E - Graph Destruction

Carelessness ：
There is a picture , from 1 To n Start deleting vertices , Remove all edges connected to the vertex each time , And output the number of connected blocks in the figure below .

Ideas ：
To calculate the number of connected blocks , You will think of and search the collection , However, the only operation that can be realized by merging sets is adding , And the topic is minus , So we should consider reverse thinking .

Inverted statistical set . Traverse from big to small to i a.m. , First update the number of connected blocks +1, Its edges must be connected to larger points , If the two are in a set , Then the number of connecting blocks will be reduced 1, Otherwise, put them into a set .

code：
 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const ll N=2e5+10;
inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}
ll dir[][4]={
   {1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
ll n,m;
ll a,b;
ll fa[N];
vector<ll> vt[N];
ll vis[N];
ll ans[N];
ll find(ll x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void solve()
{
    cin>>n>>m;
    ll cnt=0;
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=m;++i)
    {
    	cin>>a>>b;
    	vt[a].push_back(b);
	}
	ll sd=0;
	for(int i=n;i;--i)
	{
		sd++;
		for(ll k:vt[i])
		{
			ll fx=find(i);ll fy=find(k);
			if(fx!=fy)
			{
				sd--;
				fa[fx]=fy;
			}
		}
		ans[i]=sd;
	}
	for(int i=2;i<=n;++i) cout<<ans[i]<<endl;
	cout<<0;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
	return 0;
}