2020牛客暑期多校训练营（第四场）E Eliminate++ —— 线段树优化

本文主要是介绍2020牛客暑期多校训练营（第四场）E Eliminate++ —— 线段树优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你一个长度为n的排列，你每次可以取一个长度为3的子串，然后消掉最大和最小的数，直到最终剩下一个数，问你每个数是否可能是那个数。

题解：

那么我们肯定是枚举每个数，然后查看有多少数大于他，有多少数小于它。如果这些是相同的，那么每次就可以找连续三个数使得有一个大于它，一个小于它，然后直到消到最后。
那么如果不相同，我们就可以消掉连续三个大于它或者连续三个小于它中的两个。接下来用1表示大于当前数，0表示小于。
但是不能每次只看连续的三个相同数，比如11011这个串，就可以先消掉一个01，然后再消掉两个1.
然后1和0数量的情况要分开做。
接下来讨论1大于0的情况
并且这是满足贪心的，从左到右做的时候，如果当前手上有大于等于三个1，那么必然可以消掉两个1，否则如果还有1的话，那么就要和这个0抵消掉。因此线段树维护的东西不满足交换律。
那么用两个数组维护我们需要的值：
num[i][j]表示在根为i的时候，如果从左边传进来j个1，可以消掉的连续3个1的次数
res[i][j]表示在根为i的时候，如果从左边传进来j个1，到最后剩下的1的个数。
很明显j的值是0~2
那么初始化按照上面的逻辑就是这个样子：

		for(int i=0;i<3;i++)num[root][i]=i>=2,res[root][i]=i%2+1;

将当前点置为0的时候：

		for(int i=0;i<3;i++)num[root][i]=0,res[root][i]=i-1;res[root][0]=0;

表示当前点不能消掉1，然后往右传的时候1的数量会减少1。
之后query的时候需要从左到右
在比赛的时候没有想到贪心，所以没做出来，感觉还是蛮可惜的，因为并不是一道非常难的题目
由于是参考别人的解法，这个时间复杂度还是比较可以的：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int num[N*4][3],res[N*4][3];
void push_up(int root){for(int i=0;i<3;i++){num[root][i]=num[root<<1][i]+num[root<<1|1][res[root<<1][i]];res[root][i]=res[root<<1|1][res[root<<1][i]];}
}
void build(int l,int r,int root,int p){if(l==r){for(int i=0;i<3;i++)num[root][i]=i>=2,res[root][i]=i%2+1;return ;}int mid=l+r>>1;build(l,mid,root<<1,p);build(mid+1,r,root<<1|1,p);push_up(root);
}
void update(int l,int r,int root,int p){if(l==r){for(int i=0;i<3;i++)num[root][i]=0,res[root][i]=i-1;res[root][0]=0;return ;}int mid=l+r>>1;if(mid>=p)update(l,mid,root<<1,p);elseupdate(mid+1,r,root<<1|1,p);push_up(root);
}
void query(int l,int r,int root,int ql,int qr,int &rs,int &ans){if(l>=ql&&r<=qr){ans+=num[root][rs];rs=res[root][rs];return ;}int mid=l+r>>1;if(mid>=ql)query(l,mid,root<<1,ql,qr,rs,ans);if(mid<qr)query(mid+1,r,root<<1|1,ql,qr,rs,ans);
}
int a[N],p[N],v[N];
int main(){int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),p[a[i]]=i;int mid=(n+1)/2;build(1,n,1,p[1]);int ans=0;for(int i=1;i<mid;i++){int rs=0,l=1,r=p[i]-1;ans=0;update(1,n,1,p[i]);if(l<=r)query(1,n,1,l,r,rs,ans);rs=0;l=p[i]+1,r=n;if(l<=r)query(1,n,1,l,r,rs,ans);if(ans*2+i-1>=n-i)v[p[i]]=1;else v[p[i]]=0;}v[p[mid]]=1;build(1,n,1,p[n]);for(int i=n;i>mid;i--){int rs=0,l=1,r=p[i]-1;ans=0;update(1,n,1,p[i]);if(l<=r)query(1,n,1,l,r,rs,ans);rs=0;l=p[i]+1,r=n;if(l<=r)query(1,n,1,l,r,rs,ans);if(ans*2+(n-i)>=i-1)v[p[i]]=1;else v[p[i]]=0;}for(int i=1;i<=n;i++)printf("%d",v[i]);printf("\n");}return 0;
}
/*
1
3
2 3 1
*/

这篇关于2020牛客暑期多校训练营（第四场）E Eliminate++ —— 线段树优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---