牛客周赛 Round 51

D：题意：给定一个1e6长度的十进制数a和一个1e9范围的b,求解gcd

Solution：考虑用python直接做，发现TLE了，python确实比较慢。考虑本题的关键在于gcd算法的本质$gcd(a,b)=gcd(a-b,b)$，所以我们只需要模拟这个发现，我们只需要提前计算a%b即可，然后再用普通gcd就可以。

void solve(){
     string s;
    cin>>s;
     cin>>n;
     ll res=0;
     for(auto x:s){
     	res=res*10+x-'0';
     	res%=n;
     }
     cout<<gcd(res,n)<<endl;
}

E:https://ac.nowcoder.com/acm/contest/86034/E

从(1,1)走到(n,n)，定义路径权值为路径上经过的点权中最大值，求所有路径中的最小路径权值。

Solution：显然答案具有二分性，考虑check函数，转化为判定终点在当前限制条件下能不能到达。限制条件是：路径走过的点权值不超过x。

int n, m;
int a[N][N];
int dx[5]={1,0,-1,0};
int dy[5]={0,1,0,-1};
bool check(int x){
	queue<pii>q;
	vector<vector<bool>>st(n+1,vector<bool>(n+1,0));
	if(a[1][1]<=x){q.emplace(1,1);st[1][1]=true;}
	
	while(q.size()){
		auto [ux,uy]=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int vx=ux+dx[i],vy=uy+dy[i];
			if(vx<1||vx>n||vy<1||vy>n)continue;
			if(st[vx][vy]||a[vx][vy]>x)continue;
			st[vx][vy]=true;
			q.emplace(vx,vy);
		}
	}
	return st[n][n];
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++){
    		cin>>a[i][j];
    	}
    }
    int l=1,r=1e9;
    while(l<r){
    	int mid=(l+r)>>1;
    	if(check(mid))r=mid;
    	else l=mid+1;
    }
    cout<<l<<endl;
}

F:链接：https://ac.nowcoder.com/acm/contest/86034/F
给定一个数组，有 $q$ 次询问，每次询问给定一个区间 $[l,r]$，询问区间连续子段和的绝对值最大是多少，即区间存在 $x,y$使得 $l \leq x \leq y \leq r$，求最大的 $\mathrm{abs}(a[x]+a[x+1]+…..+a[y])$是多少。

Sol：题意为维护最大子段绝对值和，区间询问。

因此可以用线段树维护区间最大子段和区间最小子段和，维护区间最大子段和只需在每个节点出维护区间元素和，包含左端点的最大子段和，包含右端点的最大子段和以及整体的最大子段和（或者开两棵树，但是常数会大，实现不优秀的会T）。

上述做法可能有点卡常，注意到原问题等价于最大化$abs(pre[r]-pre[l-1])$，再考虑问题静态我们只需要预处理st表就可以快速查询了。

由于外层有绝对值，只需让y和x-1分别取到区间中前缀和的最大值和最小值处即可，y和x-1的位置关系不会影响答案。

因此只要查询前缀和数组中区间最大值和最小值，用线段树或者st表均可。

int fx[20LL][N];
int fn[20LL][N];
void init(int n){
	for(int i=1;i<=n;i++)fx[0][i]=a[i],fn[0][i]=a[i];
	for(int j=1;j<=19;j++){
		for(int i=1;i<=n;i++){
			fx[j][i]=max(fx[j-1][i],fx[j-1][i+(1<<(j-1))]);
			fn[j][i]=min(fn[j-1][i],fn[j-1][i+(1<<(j-1))]);
		}
	}
}
int querymin(int l,int r){
	int len=__lg(r-l+1);
	return min(fn[len][l],fn[len][r-(1<<len)+1]);
	}
int querymax(int l,int r){
	int len=__lg(r-l+1);
	return max(fx[len][l],fx[len][r-(1<<len)+1]);
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++)a[i]+=a[i-1];
		for(int i=1;i<=n;i++)cerr<<a[i]<<" ";
		cerr<<endl;
		init(n);
		cin>>m;
		for(int i=1;i<=m;i++){
			int l,r;
			cin>>l>>r;
			int ans=0;
			//对于abs下的最大值，最大值-最小值四种可能性
        for (auto x : vector{querymin(l-1, r), querymax(l-1, r)}) {  
            for (auto y : vector{querymin(l, r), querymax(l , r)}) {
                ans = max(ans, abs(y - x));
            }
        }
        cout<<ans<<endl;
		}
		
}

注意：对于减数的取值必须取到[L-1,R]，边界不能漏了，考虑可能相反数。被减数的范围[L,R],所有情况都覆盖了。max/min的正负决定了四种情况都要考虑。注意换一个ST板子，当前这个对于函数max/min不能自己决定。

代码2

template <typename T, class F = function<T(const T&, const T&)>>
struct SparseTable {
    int n;
    vector<vector<T>> st;
    F func;
 
    SparseTable(const vector<T>& a, const F& f) : func(f) {
        n=(int)a.size()-1;
        int max_log = __lg(n) +1;
        st.resize(max_log+1);
        st[0] = a;
        for (int j = 1; j <=max_log; j++) {
            st[j].resize(n+1);
            for (int i = 1; i+(1<<(j-1))<=n ; i++) {
                st[j][i] = func(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
    }
    T get(int l, int r) const {
       int len=__lg(r-l+1);
	return func(st[len][l],st[len][r-(1<<len)+1]);
    }
};

void solve(){
	int n,m;
	cin>>n;
	vector<int>a(n+1,0);
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)a[i]+=a[i-1];

	
	SparseTable<ll>qmin(a,[](int i,int j){return min(i,j);});
	SparseTable<ll>qmax(a,[](int i,int j){return max(i,j);});

		cin>>m;
		for(int i=1;i<=m;i++){
			int l,r;
			cin>>l>>r;
			int ans=0;
			//对于abs下的最大值，最大值-最小值四种可能性
        for (auto x : vector{qmin.get(l-1, r), qmax.get(l-1, r)}) {  
            for (auto y : vector{qmin.get(l, r), qmax.get(l , r)}) {
                ans = max(ans, abs(y - x));
            }
        }
        cout<<ans<<endl;
		}
		
}