Starters 191-Grid Path (Easy/HARD)

思路讲解

hard版，这个题解中的每句话都值得细细品味。至少每个段落都得看，都得学。

https://www.codechef.com/problems/GRIDPATHHD?tab=solution

AC代码

https://www.codechef.com/viewsolution/1167145951

源代码

// Problem: Grid Path (Easy)
// Contest: CodeChef - START191D
// URL: https://www.codechef.com/START191D/problems/GRIDPATHEZ
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT;
char A[3][MAXN];
ll dp[3][MAXN];
/*

*/
inline void init(){
	FOR(i,1,N){
		dp[1][i]=INF;
		dp[2][i]=INF;
	}
	dp[2][N+1]=0;
}
inline void solve(){
	cin>>N>>Q;
	init();
	FOR(i,1,N){
		cin>>A[1][i];
	}
	FOR(i,1,N){
		cin>>A[2][i];
	}
	ll idx=1;
	FOR(i,1,N){
		if(A[1][i]=='1'){
			dp[1][idx]=dp[1][idx-1]+i-idx;
			++idx;
		}
	}
	idx=N;
	ROF(i,N,1){
		if(A[2][i]=='1'){
			dp[2][idx]=dp[2][idx+1]+idx-i;
			--idx;
		}
	}
#ifdef LOCAL
    FOR(i,1,N){
    	cerr<<dp[1][i]<<" ";
    }
    cerr<<"\n";
    FOR(i,1,N){
    	cerr<<dp[2][i]<<" ";
    }
    cerr<<"\n";
#endif
	ll ans=INF;
	FOR(i,1,N){
		ans=min(ans,dp[1][i]+dp[2][i]);
	}
	if(ans>=INF) cout<<-1<<"\n";
	else cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*

*/

https://www.codechef.com/viewsolution/1167615239

源代码

// Problem: Grid Path (Hard)
// Contest: CodeChef - START191
// URL: https://www.codechef.com/problems/GRIDPATHHD
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e18)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT;
char A[3][MAXN];
/*

*/
class SEG{		// 最简单的区间加减，区间和查询，单点修改线段树  
// AC https://www.luogu.com.cn/record/221021710 线段树模版
private:
	vector<ll> L,R,Add,Sum;
	void build(ll node,ll l,ll r){
		L[node]=l;R[node]=r;Add[node]=0;Sum[node]=0;
		if(l==r){
			return;
		}
		ll mid=l+r>>1;
		build(lson(node),l,mid);
		build(rson(node),mid+1,r);
	}
	void pushup(ll node){
		while(node){
			node>>=1;
			Sum[node]=Sum[lson(node)]+Sum[rson(node)];
		}
	}
	void pushdown(ll node){
		if(L[node]==R[node]) return;
		if(Add[node]==0) return;	// 非必须
		Add[lson(node)]+=Add[node];
		Sum[lson(node)]+=(R[lson(node)]-L[lson(node)]+1)*Add[node];
		Add[rson(node)]+=Add[node];
		Sum[rson(node)]+=(R[rson(node)]-L[rson(node)]+1)*Add[node];
		Add[node]=0;
	}
	bool isin(ll a,ll b,ll c,ll d){
		if(b<c || a>d) return false;
		return true;
	}
	void add(ll node,ll l,ll r,ll x){
		if(R[node]<l || L[node]>r) return;
		pushdown(node);
		if(L[node]>=l && R[node]<=r){
			Sum[node]+=(R[node]-L[node]+1)*x;
			Add[node]+=x;
			pushup(node);
			return;			// 这里一定要return，否则就重复加了
		}
		if(isin(L[lson(node)],R[lson(node)],l,r)) add(lson(node),l,r,x);
		if(isin(L[rson(node)],R[rson(node)],l,r)) add(rson(node),l,r,x);
	}
	ll query(ll node,ll l,ll r){
		// if(R[node]<l || L[node]>r) return 0;		// 这个无所谓
		pushdown(node);
		if(L[node]>=l && R[node]<=r){
			return Sum[node];
		}
		ll ret=0;
		if(isin(L[lson(node)],R[lson(node)],l,r)) ret+=query(lson(node),l,r);
		if(isin(L[rson(node)],R[rson(node)],l,r)) ret+=query(rson(node),l,r);
		return ret;		// 不要忘记return
	}
	void modify(ll node,ll p,ll x){
		pushdown(node);
		if(L[node]==p && R[node]==p){
			Sum[node]=x;
			pushup(node);
			return;
		}
		if(isin(L[lson(node)],R[lson(node)],p,p)) modify(lson(node),p,x);
		if(isin(L[rson(node)],R[rson(node)],p,p)) modify(rson(node),p,x);
	}
	ll findk(ll node,ll k){  // 返回第k个有值的下标，当然，要求线段树叶节点值是0或1
		pushdown(node);
        if(L[node]==R[node]) return L[node];
		if(Sum[lson(node)]>=k){
			return findk(lson(node),k);
		}else{
			return findk(rson(node),k-Sum[lson(node)]);
		}
	}
public:
	SEG(int n){
		if(n<=0) n=1; //  防止传入0作为大小导致RE
		L.resize(4*n);R.resize(4*n);Add.resize(4*n);Sum.resize(4*n);
		build(1,1,n);
	}
	// c++函数重载，只要参数数量不同不用担心重名
	void add(ll l,ll r,ll x){add(1,l,r,x);}	// 这样调用的时候就不需要填node了
	ll query(ll l,ll r){return query(1,l,r);}
	ll findk(ll k){return findk(1,k);}
	void modify(ll p,ll x){modify(1,p,x);}
#ifdef LOCAL		// 用来帮助debug的
    void segDe(ll node){
    	pushdown(node);
    	cerr<<L[node]<<" "<<R[node]<<" "<<Sum[node]<<"\n";
    	if(L[node]==R[node]) return;
    	segDe(lson(node));
    	segDe(rson(node));
    }
#endif
};
inline void init(){
	
}
inline void solve(){
	cin>>N>>Q;
	init();
	vector<SEG> tr;
	tr.pb(SEG(1));
	tr.pb(SEG(N));	// 维护所有
	tr.pb(SEG(N));
	tr.pb(SEG(N));	// 维护所有下标及其和
	tr.pb(SEG(N));
	vector<ll> cnt(4,0);
	FOR(i,1,N){
		cin>>A[1][i];
		tr[1].add(i,i,A[1][i]-'0');
		if(A[1][i]=='1') cnt[1]++,tr[3].modify(i,i);
	}
	FOR(i,1,N){
		cin>>A[2][i];
	}
	reverse(A[2]+1,A[2]+1+N);
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<A[2][i]<<" ";
    // }
    // cerr<<"\n";
// #endif
	FOR(i,1,N){
		tr[2].add(i,i,A[2][i]-'0');
		if(A[2][i]=='1') cnt[2]++,tr[4].modify(i,i);
	}
// #ifdef LOCAL
	// cerr<<"C3:\n";
    // tr[3].segDe(1);
    // cerr<<"D4\n";
    // tr[4].segDe(1);
// #endif
	auto bs=[&]()->void{
		if(cnt[1]+cnt[2]<N+1){
			cout<<-1<<"\n";
			return;
		}
		ll l=N+1-cnt[2],r=cnt[1];
// #ifdef LOCAL
    // cerr << "originlr:"<<l<<" "<<r << "-------------\n";
// #endif
		while(l<r){
			ll mid=l+r+1>>1;
			//      下标 - 第mid个
			ll res=0;
// #ifdef LOCAL
    // debug(tr[1].findk(mid)-mid);
// #endif
			if(mid!=N+1-cnt[2])res=tr[1].findk(mid)-mid-tr[2].findk(N+2-mid)+(N+2-mid);
			if(res<=0){
				l=mid;
			}else{
				r=mid-1;
			}
// #ifdef LOCAL
	// debug(mid);
    // debug(res);
// #endif
		}
// #ifdef LOCAL
    // debug(l);debug(r);
// #endif
		if(l>r) l=r;
		//                        因为下面一行是被反转过的，所以说是
		// C[1]+C[2]+D[1]+D[2]+...+D[N-1]   D[N] 不需要是因为D[N]是反转之前最靠前的
		ll sumc=tr[3].query(1,tr[1].findk(l));
		ll sumd=tr[4].query(1,tr[2].findk(N+1-l));
		// (1+l)*l/2 是从1加到l的
		ll sum=sumc-(1+l)*l/2+sumd-(N+1-l+1)*(N+1-l)/2;		// sumc和sumd是下标之和
// #ifdef LOCAL
    // debug(sumc-(1+l)*l/2);
    // debug(sumd-(N+1-l+1)*(N+1-l)/2);
    // debug(l);
    // debug(cnt[1]);
    // debug(sum);
    // debug(tr[2].findk(N+1-l));
// #endif
		cout<<sum<<"\n";
	};
	bs();
	FOR(_,1,Q){
		ll x,y;
		cin>>x>>y;
		if(x==2) y=N-y+1;	// A[2] 已经被反转了
		if(A[x][y]=='1'){
			tr[x].modify(y,0);
			tr[x+2].modify(y,0);
			cnt[x]--;
			bs();
			A[x][y]='0';
		}else{
			tr[x].modify(y,1);
			tr[x+2].modify(y,y);
// #ifdef LOCAL
    // debug(y);
// #endif
			cnt[x]++;
			bs();
			A[x][y]='1';
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC
https://www.codechef.com/viewsolution/1167615239
*/

心路历程（WA，TLE，MLE……）

EZ不小心错了一次，实际上是INF开小了。

第186行这里容易符号写反。

https://www.codechef.com/viewsolution/1167612305

if(mid!=N+1-cnt[2])res=tr[1].findk(mid)-mid-tr[2].findk(N+2-mid)+(N+2-mid);