B

可以把一个区间的数字都变成出现次数较多的元素，问把整个数组变成相同元素，最少操作几次。

首先可以注意到只有01两种元素，那么长度为奇数的数组，01个数一定不等，也就是01一定有一个比另一个更多，可以执行操作变成同一个，因此长度为奇数答案至多为1

长度为偶数时，如果01个数不同，也是一次操作。如果01个数相同，我们可以取长度为n-1的子数组，它的长度是奇数，一定能通过一次操作变成一样的。这样的子数组一共有四个，我们看这四个情况，变完之后剩下的那一个元素和变完的元素是否相同，如果相同就是一次操作。如果不同还需要一次把剩下的拿一个元素变了，就是两次操作

当然需要注意初始全都相同就不用操作

void solve(){
	string s;
	cin>>n>>s;
	if(n==1){
		cout<<0;
	}
	else if(n==2){
		if(s[0]!=s[1]){
			cout<<-1;
		}
		else{
			cout<<0;
		}
	}
	else{
		if(n%2){
			int cnt=0;
			for(char c:s){
				if(c=='0'){
					cnt++;
				}
			}
			if(cnt==n||cnt==0){
				cout<<0;
			}
			else{
				cout<<1;
			}
		}
		else{
			int cnt0=0,cnt1=0;
			rep(i,0,n-1){
				if(s[i]=='0')cnt0++;
				else cnt1++;
			}
            if(cnt0==0||cnt0==n){
                cout<<0;
                return;
            }
            if(cnt0!=cnt1){
                cout<<1;
                return;
            }
            if(s[n-1]=='1')cnt1--;
            else cnt0--;
			if(cnt1>cnt0&&s[n-1]=='1')cout<<1;
			else if(cnt0>cnt1&&s[n-1]=='0')cout<<1;
			else{
				int cnt0=0,cnt1=0;
				rep(i,1,n-1){
					if(s[i]=='0')cnt0++;
					else cnt1++;
				}
				if(cnt1>cnt0&&s[0]=='1')cout<<1;
				else if(cnt0>cnt1&&s[0]=='0')cout<<1;
				else cout<<2;
			}
		}
	}
}	

C

滑窗

把数组分成三个子数组，要求中间的子数组元素和比另外两个都大，问有多少种划分。

划分成三段，其实等价于找一个子数组，只是要求剩下的前缀和后缀不能为空。这种统计合法子数组个数可以考虑滑窗。滑窗内时中间子数组，滑窗左右分别是另外两个子数组。由于元素是正的，我们可以对于每个r，找到最靠右的l，这个l左边的位置也都可以作为l，因为往左移动的话中间子数组会变大，左侧子数组会变小，如果原本可以的话，l往肯定也可以

需要注意的是可能l滑到头了也不合法，所以在加答案的时候，要判断一下l是否合法

void solve(){
	cin>>n;
	vi a(n+1);
	rep(i,1,n)cin>>a[i];
	int b1=a[1],b2=a[2],b3=0;
	rep(i,3,n)b3+=a[i];
	
	int j=2,ans=0;
	rep(i,3,n-1){
		b2+=a[i];
		b3-=a[i];
		while(j<i&&b2>b3&&b2>b1){
			b1+=a[j];
			b2-=a[j];
			j++;
		}
		if(b2+a[j-1]>b3&&b2+a[j-1]>b1-a[j-1])ans+=j-2;
	}
	cout<<ans<<'\n';
}

D

奇数和奇数，偶数和偶数相连代价a，奇数和偶数相连代价b。问所有点联通的最小代价。

这题比较坑人的点在于ab可以是负的，所以联通之后为了代价更小，还可以加边。

如果ab都负，把能加的边都加上，也就是任意一个奇数和任意一个偶数奇数/偶数内部任意两点，都可以连线

如果a正b负。把奇数偶数之间连满，此时一定就联通了不用连别的。注意可能所有数都是奇数/偶数，那么只能用a尽可能少连，也就是连n-1条

如果a负b正，奇数内部，偶数内部练满，如果奇数和偶数都至少有一个，需要一个b联通奇数和偶数

如果ab都正，首先肯定需要一个b连接一个奇数和一个偶数，接下来每个数都可以任意选连接到奇数还是偶数，那么根据ab大小来选择

void solve(){
    int a,b,n;
	cin>>n>>a>>b;
	int cnt0=0,cnt1=0;
	rep(i,1,n){
        int t;
        cin>>t;
		if(t%2)cnt1++;
		else cnt0++;
	}
	int ans=0;
	if(a<=0&&b<=0){
        ans+=cnt0*cnt1*b;
        ans+=cnt0*(cnt0-1)/2*a+cnt1*(cnt1-1)/2*a;
    }
    else if(a<=0){
        ans+=cnt0*(cnt0-1)/2*a+cnt1*(cnt1-1)/2*a;
        if(cnt1&&cnt0)ans+=b;
    }
    else if(b<=0){
        if(cnt0==0||cnt0==n)ans+=(n-1)*a;
        else ans+=cnt0*cnt1*b;
    }
    else{
        if(cnt0==0||cnt0==n)ans+=(n-1)*a;
        else{
            ans+=b;
            if(a<=b)ans+=(n-2)*a;
            else ans+=(n-2)*b;
        }
    }
    cout<<ans<<'\n';
}	

E

可以删一个子树，让支撑节点最大化。支撑结点的定义是，所有祖先的权值和大于等于自己，所有子孙的权值和小于等于自己。

显然可以先求出初始的支撑节点个数，然后dfs的过程中，遍历所有子树，也就是枚举删除子树。然后计算删除每个子树的情况下的支撑节点个数，取max

那么怎么计算删除一棵子树后支撑节点的变化？首先能影响到的肯定只有当前结点的祖先，然后再这些祖先节点中，满足a[i]>=sum[i]-sum[j],sum[i]表示i的子孙的权值和,j是当前枚举删除的子树根节点,a是点权的点，会成为新的支撑节点

变形一下，就是要找祖先节点中，满足sum[i]-a[i]<=sum[j]的点有多少个。这是个区间查询，并且我们dfs的过程中区间点数会变，也就是是一个动态区间查询，可以用平衡树/树状数组/线段树，后两个由于ai很大需要离线

int t[N];
int lowbit(int x){
    return x&(-x);
}
void add(int x,int k){
    while(x<=m){
        //cout<<x<<'\n'
        t[x]+=k;
        x+=lowbit(x);
    }
}
int ask(int x){
    int res=0;
    while(x>0){
        //cout<<x<<'\n';
        res+=t[x];
        x-=lowbit(x);
    }
    return res;
}
void solve(){
    cin>>n;
    vi a(n+1),s(n+1);
    vector<vi>g(n+1);
    rep(i,1,n)cin>>a[i];
    rep(i,1,n){
        int t;
        cin>>t;
        if(!t)continue;
        g[t].pb(i);
    }
    auto &&dfs=[&](auto &&dfs,int u)->void{
        s[u]=a[u];
        for(int v:g[u]){
            dfs(dfs,v);
            s[u]+=s[v];
        }
    };
    int tot=0;
    vi all,cnt(n+1);
    auto &&dfs0=[&](auto &&dfs0,int u,int up)->void{
        if(up>=a[u]&&a[u]>=s[u]-a[u])tot++,cnt[u]=1;
        for(int v:g[u]){
            dfs0(dfs0,v,up+a[u]);
            cnt[u]+=cnt[v];
        }
    };
    dfs(dfs,1);
    dfs0(dfs0,1,0);
    rep(i,1,n){
        all.pb(s[i]);
        all.pb(s[i]-2*a[i]);
    }
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end()),all.end());
     
    m=all.size();
    unordered_map<int,int>lisan;
    rep(i,0,m-1){
        lisan[all[i]]=i+1;
    }
    int ans=0;
    //cout<<tot<<'\n';
    auto &&dfs1=[&](auto &&dfs1,int u,int up)->void{
        ans=max(ans,ask(lisan[s[u]])-cnt[u]);
        //cout<<ask(lisan[s[u]])<<' '<<cnt[u]<<' '<<u<<'\n';
        if(up>=a[u])add(lisan[s[u]-2*a[u]],1);
        for(int v:g[u]){
            dfs1(dfs1,v,up+a[u]);
        }
        if(up>=a[u])add(lisan[s[u]-2*a[u]],-1);
    };
    dfs1(dfs1,1,0);
    cout<<ans+tot<<'\n';
} 

F

很妙的一道题，重点是优化思路

对于每个前缀，求他的所有圆排列中，逆序对个数最小值。一个显然的思路是，枚举前缀长度，对于每个前缀，枚举所有圆排列，枚举的过程实际上就是每次都把头部元素放到最后，这一步对逆序对的影响可以用ds维护，实际上就是求大于头部元素的元素个数，这样复杂度是

但是看数据，我们要实现。这就需要一些智慧了：实际上把头部元素移动到末尾，对逆序对的影响，我们不一定要用ds，这一步实际上就是要知道比a[1]大的元素有多少个（逆序对会增加多少），以及比a[1]小的元素有多少个（逆序对会减少多少），这个东西我们可以开个数组维护：w[i]表示，考虑当前前缀，比i大的元素个数-比i小的元素个数。这个东西很好维护，我们枚举前缀的时候，每加入一个元素，就可以把比它小的元素的w[i]++，比他大的元素的w[i]--

void solve(){
    cin>>n;
    vi a(n+1);
    rep(i,1,n)cin>>a[i];
     
    vi w(n+1);
    int ans=0;
    rep(i,1,n){
        rep(j,1,a[i])w[j]++;
        rep(j,a[i],n)w[j]--;
        rep(j,1,i)ans+=a[j]>a[i];
        int cur=0;
        int mn=0;
        rep(j,1,i){
            cur+=w[a[j]];
            mn=min(mn,cur);
        }
        cout<<ans+mn<<' ';
    }
}