CodeCraft-22 and Codeforces Round ＃795 (Div. 2)D,E

D.Max GEQ Sum

The question ：
I'll give you a length of $n(1\le 2\ast 10^5)$ Array of $a$, Whether it is satisfied for any $i,j(1\le i\le j\le n)$, Guarantee
$$\max (a_i,a_{i+1},...,a_{j-1},a_j)\ge a_i+a_{i+1}+...+a_{j_1}+a_j$$ Ideas ：
adopt Monotonic stack , We can find a number left / The position of the first larger number on the right , So we can know that the maximum value is $a_i$ The value range of the left and right boundaries of time
In this range , as long as $\sum a$ The maximum value of is less than $\max a$ That is to meet the requirements , So record a prefix and , The segment tree is used to maintain the maximum and minimum values of the interval , The maximum value is calculated by subtracting the minimum value on the left from the maximum value on the right $\sum a$

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
int n,a[maxn],b[maxn],l[maxn],r[maxn];
struct tree
{
    
	int l,r,mx,mn;
	int mid()
	{
    
		return (l+r)/2;
	}
}tre[maxn<<2];
void pushup(int num)
{
    
    tre[num].mx=max(tre[2*num].mx,tre[2*num+1].mx);
    tre[num].mn=min(tre[2*num].mn,tre[2*num+1].mn);
}
void build(int num,int l,int r)
{
    
	tre[num].l=l,tre[num].r=r;
	if(l==r)
	{
    
		tre[num].mx=tre[num].mn=a[l];return;
	}
	int mid=tre[num].mid();
	build(2*num,l,mid);
	build(2*num+1,mid+1,r);
    pushup(num);
}
int query_max(int num,int l,int r)
{
    
	if(tre[num].l==l && tre[num].r==r)
	return tre[num].mx;
	int mid=tre[num].mid();
	if(l>mid)
	return query_max(2*num+1,l,r);
	else if(r<=mid)
	return query_max(2*num,l,r);
	else
	return max(query_max(2*num,l,mid),query_max(2*num+1,mid+1,r));
}
int query_min(int num,int l,int r)
{
    
	if(tre[num].l==l && tre[num].r==r)
	return tre[num].mn;
	int mid=tre[num].mid();
	if(l>mid)
	return query_min(2*num+1,l,r);
	else if(r<=mid)
	return query_min(2*num,l,r);
	else
	return min(query_min(2*num,l,mid),query_min(2*num+1,mid+1,r));
}
signed main()
{
    
	int T;scanf("%lld",&T);
	while(T--)
	{
    
		scanf("%lld",&n);
		for(int i=1;i<=n;i++)
		{
    
			scanf("%lld",&b[i]);
		}
		stack<int>s;
		for(int i=1;i<=n;i++)
		{
    
			while(!s.empty() && b[i]>=b[s.top()]) s.pop();
			if(s.size()==0) l[i]=0;
			else l[i]=s.top();
			s.push(i);
		}
		while(!s.empty()) s.pop();
		for(int i=n;i>=1;i--)
		{
    
			while(!s.empty() && b[s.top()]<=b[i]) s.pop();
			if(s.size()==0) r[i]=n+1;
			else r[i]=s.top();
			s.push(i);
		}
		for(int i=1;i<=n;i++) a[i]=a[i-1]+b[i];
		a[n+1]=a[n];
		build(1,0,n+1);
		
		int ok=1;
		for(int i=1;i<=n;i++)
		{
    
			int mn=query_min(1,l[i],i-1);
			int mx=query_max(1,i,r[i]-1);
			if(mx-mn>b[i])
			{
    
				ok=0;break;
			}
		}
		ok?puts("YES"):puts("NO");
	}
}

E. Number of Groups

The question ：
Here you are. $n$ Segment interval , Each interval has colors $0,1$, And length $l,r(0\le l_i\le r_i\le 10^9)$
If the color of two sections is different , And there are intersections that can be connected with chains , Ask this $n$ How many sets will be formed by each interval

Ideas ：
It is obvious that the title of the joint search set , The problem is how to optimize some time
One of my thoughts is ： Split all sections left and right to sort , use $set$ Storage , If it's the left endpoint , And put another color $set$ Connect to it , Put in $set$, Otherwise delete from .
The reason why the speed is too slow is that some edges that are already in the same set are repeatedly connected , So we delete the same color intervals that have been connected together , Only the farthest right endpoint

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int fa[maxn],n;
int find(int x){
    if(x==fa[x]) return fa[x]; return fa[x]=find(fa[x]);}
void lianjie(int x,int y){
    int px=find(x),py=find(y);fa[px]=py;}
struct node
{
    
    int l,r,id;
    bool operator < (const node& n1)const
    {
    
    	if(n1.r==r && n1.l==l) return n1.id>id;
    	if(n1.r==r) return n1.l>l;
    	return n1.r>r;
    }
}a[maxn];
int main()
{
    
    int T;scanf("%d",&T);
    while(T--)
    {
    
        int n;scanf("%d",&n);
        vector<tuple<int,int,int,int,int>>v;
        for(int i=1;i<=n;i++)
        {
    
            int col,l,r;
            fa[i]=i;scanf("%d%d%d",&col,&l,&r);
            v.push_back({
    l,1,r,col,i});v.push_back({
    r,2,l,col,i});
        }
        sort(v.begin(),v.end());
        multiset<node>s[2];
        for(int i=0;i<v.size();i++)
        {
    
            vector<tuple<int,int,int,int>>del;
            auto [x,y,z,col,id]=v[i];
            if(y==1)
            {
    
                for(auto [l,r,id2]:s[col^1])
                {
    
                    if(x<=r)
                    {
    
                        del.push_back({
    l,r,id2,col^1});
                        lianjie(id,id2);
                    }
                }
                if(del.size()) del.pop_back();
                s[col].insert({
    x,z,id});
            }
            else
            {
    
                del.push_back({
    z,x,id,col});
                // printf("---\n");
            }
            for(auto [x,y,z,c]:del)
            {
    
                s[c].erase({
    x,y,z});
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++) if(fa[i]==i) ans++;//printf("i=%d \n",i);
        printf(" %d\n",ans);
    }
}