Znzryb's Blog

P11643 【MX-X8-T2】「TAOI-3」终有一天，飞向水平线的彼方（区间操作化简）

Posted on 2025-06-25 Edited on 2026-04-06

思路讲解

那么容易发现，其实这种区间操作的题目一般来说最短的操作是最灵活的，一个长操作也可以化为多个短操作的结果。

比如说这道题目长度为4的操作可以变为对中间两个元素执行一次，再对两侧两个元素分别执行一次。

所以我们不用考虑长度>2的操作。

那么不难注意到，就是说这个开头和结尾往往是这个破局的地方，那么开头那如果不同，必须要操作后面一个，然后不断传递，最后传递到A_[N]，就结束了。

FOR(i,1,N){
	cin>>A[i];
	A_[i]=A[i];
}
FOR(i,1,N){
	cin>>B[i];
}
FOR(i,1,N-1){
	ll diff=B[i]-A_[i];
	A_[i+1]+=diff;
}
if(A_[N]==B[N]){
	cout<<"Yes\n";
}else{
	cout<<"No\n";
}

AC代码

https://www.luogu.com.cn/record/221383853

源代码

// Problem: P11643 【MX-X8-T2】「TAOI-3」终有一天，飞向水平线的彼方
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11643
// Memory Limit: 512 MB
// Time Limit: 2000 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;

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

ll N,M,Q,X,K,lT,A[MAXN],B[MAXN];
ll A_[MAXN];
/*

*/
inline void init(){
	
}
inline void solve(){
	cin>>N;
	init();
	FOR(i,1,N){
		cin>>A[i];
		A_[i]=A[i];
	}
	FOR(i,1,N){
		cin>>B[i];
	}
	FOR(i,1,N-1){
		ll diff=B[i]-A_[i];
		A_[i+1]+=diff;
	}
	if(A_[N]==B[N]){
		cout<<"Yes\n";
	}else{
		cout<<"No\n";
	}
	
}

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

*/

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

Starter 190-1-2 Reorder

Posted on 2025-06-25 Edited on 2026-04-06

思路讲解

AC代码

源代码

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

P11644 【MX-X8-T3】「TAOI-3」地地爱打卡（注意特判奇数环和独立点）

Posted on 2025-06-24 Edited on 2026-04-06

思路讲解

由于奇数环既有一条偶数路径，又有一条奇数路径，可以直接特判。

重要程序解析

auto dfs=[&](auto &&dfs,ll u,ll col,ll fa)->void{
	vis[u]=true;
	color[u]=col;
	FOR(i,0,SZ(g[u])-1){
		ll v=g[u][i];
		if(v==fa) continue;
		if(vis[v]){
			ll diff=col-color[v];   // 判奇数环可以使用这种方式
			if(diff%2==0){
				isji[dsu.find(v)]=true;
			}
			continue;
		}
		dfs(dfs,v,1+col,u);
	}
};
FOR(i,1,N){
	if(vis[i]){
		continue;
	}
	dfs(dfs,i,1,0);
}
FOR(i,1,Q){
	ll s,t,x;
	cin>>s>>t>>x;
	if(dsu.same(s,t)==false){
		cout<<"expand\n";
		continue;
	}
	if(dsu.size(s)==1 && x!=0){   // 对独立点的特判
		cout<<"expand\n";
		continue;
	}
	if(isji[dsu.find(s)]){
		cout<<"tribool\n";
		continue;
	}
	ll diff=abs(color[s]-color[t]);
	if(diff%2==1 && x%2==1){
		cout<<"tribool\n";
		continue;
	}
	if(diff%2==0 && x%2==0){
		cout<<"tribool\n";
		continue;
	}
	cout<<"expand\n";
}

AC代码

https://www.luogu.com.cn/record/221314756

源代码

// Problem: D - 「TAOI-3」地地爱打卡
// Contest: Virtual Judge - 20250624暑假训练
// URL: https://vjudge.net/contest/724839#problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 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;

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

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

*/
inline void init(){
	
}
vector<ll> g[MAXN];		// 记得要清空
struct DSU { // 并查集
    vector < int > fa, siz;
    int ln;
    DSU(int n) {
        ln = n;
        fa.resize(ln + 5, 0), siz.resize(ln + 5, 0);
        FOR(i, 1, n) {
            fa[i] = i;
            siz[i] = 1;
        }
    }
    int find(int x) {
        while (fa[x] != x) {
            x = fa[x];
            fa[x] = fa[fa[x]];
        }
        return x;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        fa[y] = x;
        return true;
    }
    int size(int x) {
        return siz[find(x)];
    }
    int countFa() {
        int res = 0;
        FOR(i, 1, ln) {
            if (fa[i] == i) ++res;
        }
        return res;
    }
};
inline void solve(){
	cin>>N>>M>>Q;
	init();
	DSU dsu(N);
	FOR(i,1,M){
		ll u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
		dsu.merge(u,v);
	}
	vector<bool> vis(N+5,false);
	vector<ll> color(N+5,0);
	vector<bool> isji(N+5,false);
	auto dfs=[&](auto &&dfs,ll u,ll col,ll fa)->void{
		vis[u]=true;
		color[u]=col;
		FOR(i,0,SZ(g[u])-1){
			ll v=g[u][i];
			if(v==fa) continue;
			if(vis[v]){
				ll diff=col-color[v];
				if(diff%2==0){
					isji[dsu.find(v)]=true;
				}
				continue;
			}
			dfs(dfs,v,1+col,u);
		}
	};
#ifdef LOCAL
    cerr << "OK" << '\n';
#endif
	FOR(i,1,N){
		if(vis[i]){
			continue;
		}
		dfs(dfs,i,1,0);
#ifdef LOCAL
    debug(i);
#endif
	}
#ifdef LOCAL
    cerr << "OK" << '\n';
    FOR(i,1,N){
    	cerr<<color[i]<<" ";
    }
    cerr<<"\n";
    FOR(i,1,N){
    	cerr<<isji[dsu.find(i)]<<" ";
    }
#endif
	FOR(i,1,Q){
		ll s,t,x;
		cin>>s>>t>>x;
		if(dsu.same(s,t)==false){
			cout<<"expand\n";
			continue;
		}
		if(dsu.size(s)==1 && x!=0){
			cout<<"expand\n";
			continue;
		}
		if(isji[dsu.find(s)]){
			cout<<"tribool\n";
			continue;
		}
		ll diff=abs(color[s]-color[t]);
		if(diff%2==1 && x%2==1){
			cout<<"tribool\n";
			continue;
		}
		if(diff%2==0 && x%2==0){
			cout<<"tribool\n";
			continue;
		}
		cout<<"expand\n";
	}
}

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

*/

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

Starter 189-Blocks in a String（减少块的数量）

Posted on 2025-06-24 Edited on 2026-04-06

思路讲解

使用分块以及分块思想，考虑一个未定义元素块。

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

那么我们这个为什么可以ans-=2？

1	....01????10.....

这种情况自然不必多说，那么确实是实打实的减少了2个块。

1	.....11??????11?????11......

那么我们的疑惑是这种情况下-2，-2可以吗？答案当然是可以的，这里的“？”全部变为1了以后总块数就是1了

sort(all(cnts[0]));
sort(all(cnts[1]),greater<ll>());
sort(all(cnts[2]),greater<ll>());
ll ans=oans;
vector<bool> alde(N+5,false);
FOR(i,0,N){
	if(i<cnt1){
		cout<<-1<<" ";
		continue;
	}
	if(i>N-cnt0){
		cout<<-1<<" ";
		continue;
	}
	if(i==cnt1){
		cout<<ans<<" ";
		continue;
	}
	if(!cnts[2].empty()){		// 1 1
		ll id=SZ(cnts[2])-1;
		cnts[2][id]--;
		if(cnts[2][id]<=0){
			cnts[2].pop_back();
			ans-=2;
		}
		cout<<ans<<" ";
		continue;
	}
	if(!cnts[1].empty()){
		ll id=SZ(cnts[1])-1;
		cnts[1][id]--;
		if(cnts[1][id]<=0){
			cnts[1].pop_back();
		}
		cout<<ans<<" ";
		continue;
	}
	if(!cnts[0].empty()){
		ll id=SZ(cnts[0])-1;
		if(!alde[id]) ans+=2;
		cnts[0][id]--;
		alde[id]=true;
		if(cnts[0][id]<=0){
			cnts[0].pop_back();
		}
		cout<<ans<<" ";
		continue;
	}
}

AC代码

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

源代码

// Problem: Blocks in a String
// Contest: CodeChef - START189
// URL: https://www.codechef.com/problems/BLOCKSTR?tab=statement
// Memory Limit: 256 MB
// Time Limit: 1000 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;

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

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

*/
inline void init(){
	
}
inline void solve(){
	cin>>N;
	init();
	ll cnt1=0,cnt0=0;
	FOR(i,1,N){
		cin>>S[i];
		if(S[i]=='1') ++cnt1;
		else if(S[i]=='0') ++cnt0;
	}
	S[N+1]='\0',S[0]='\0';
	ll idx=1;
	vector<vector<ll> > g(N+5);
	FOR(i,1,N){
		if(S[i]!='?') continue;
		if(g[idx].empty() || i-g[idx].back()==1 ){
			g[idx].pb(i);
		}else{
			++idx;
			g[idx].pb(i);
		}
	}
	ll oans=1;char up=S[1];
	FOR(i,2,N){
		char ch=S[i];
		if(ch=='?') ch='0';
		if(ch!=up){
			++oans;
			up=ch;
		}
	}
	vector<vector<ll> > cnts(N+5);
	FOR(i,1,idx){
		if(g[i].empty()) continue;
		ll l=g[i].front(),r=g[i].back();
		ll id=S[l-1]-'0'+S[r+1]-'0';
		cnts[id].pb(r-l+1);
	}
	sort(all(cnts[0]));
	sort(all(cnts[1]),greater<ll>());
	sort(all(cnts[2]),greater<ll>());
	ll ans=oans;
#ifdef LOCAL
    debug(ans);debug(oans);
#endif
	vector<bool> alde(N+5,false);
	FOR(i,0,N){
		if(i<cnt1){
			cout<<-1<<" ";
			continue;
		}
		if(i>N-cnt0){
			cout<<-1<<" ";
			continue;
		}
		if(i==cnt1){
			cout<<ans<<" ";
			continue;
		}
		if(!cnts[2].empty()){		// 1 1
			ll id=SZ(cnts[2])-1;
			cnts[2][id]--;
			if(cnts[2][id]<=0){
				cnts[2].pop_back();
				ans-=2;
			}
			cout<<ans<<" ";
			continue;
		}
		if(!cnts[1].empty()){
			ll id=SZ(cnts[1])-1;
			cnts[1][id]--;
			if(cnts[1][id]<=0){
				cnts[1].pop_back();
			}
			cout<<ans<<" ";
			continue;
		}
		if(!cnts[0].empty()){
			ll id=SZ(cnts[0])-1;
			if(!alde[id]) ans+=2;
			cnts[0][id]--;
			alde[id]=true;
			if(cnts[0][id]<=0){
				cnts[0].pop_back();
			}
			cout<<ans<<" ";
			continue;
		}
	}
	cout<<"\n";
}

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/1168370649
*/

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

这个0？？？0的这个块的排序要反过来，因为我们需要他更持久一点，因为他毕竟是要ans+=2的。

1	sort(all(cnts[0]));

Starter 188-Inversion Queries

Posted on 2025-06-24 Edited on 2026-04-06

思路讲解

two number <=L || >=R delete

FOR(i,1,Q){
	// two number <=L || >=R  delete
	cin>>L[i]>>R[i];
	if(L[i]==R[i]){
		cout<<0<<"\n";
		continue;
	}
	ll lans=ans;
	lans-=ansp.query(R[i],N);
	lans-=anss.query(1,L[i]);
	if(lans<0) cout<<"0\n";
	else cout<<lans<<"\n";
}

AC代码

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

源代码

// Problem: Inversion Queries
// Contest: CodeChef - START188
// URL: https://www.codechef.com/problems/INVQUER
// Memory Limit: 256 MB
// Time Limit: 1000 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;

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

ll N,M,Q,X,K,lT,A[MAXN],L[MAXN],R[MAXN];
/*

*/
inline void init(){
	
}
struct BIT {  // 普通的单点修改区间查询树状数组，含有查找第K个空位的功能
  vector<ll> tr;
  int n;
  inline int lowbit(int x) { return x & (-x); }
  BIT(int ln) {  // 构造+初始化函数
    n = ln;
    tr.resize(n+5,0);
  }
  inline void add(int p, int x) {
  	if(p==0) return;
    while (p <= n) {
      tr[p] += x;
      p += lowbit(p);
    }
  }
  inline ll query(int l, int r) {
    ll lres = 0, rres = 0;
    l -= 1;
    while (l > 0) {
      lres += tr[l];
      l -= lowbit(l);
    }
    while (r > 0) {
      rres += tr[r];
      r -= lowbit(r);
    }
    return rres - lres;
  }
  inline int findKth(int k) {  // 找到第k个空位，当然应当是要求只能出现0和1
    int cx = 0;
    for (int i = 1 << 20; i > 0; i >>= 1) {  // 这个你可以理解为不断缩小步长的搜索
      if (cx + i <= n && lowbit(cx + i) - tr[cx + i] < k) {
        // lowbit(cx)-tr[cx+i] 表示cx+i这个树状数组区间有多少空位
        k -= lowbit(cx + i) - tr[cx + i];
        cx += i;
      }
    }
    return cx + 1;  // 我们始终让cx < k，所以返回的就是最大的比k小的，+1就是新空位出现的地方
  }
};
inline void solve(){
	cin>>N>>Q;
	init();
	FOR(i,1,N){
		cin>>A[i];
	}
	BIT trp(N),ansp(N),trs(N),anss(N);
	// 找编号比自己小但是更大的
	ll ans=0;
	FOR(i,1,N){
		ll res=trp.query(A[i],N);
		ansp.add(A[i],res);
		ans+=res;
		trp.add(A[i],1);
	}
	// index big but value small
	ROF(i,N,1){
		ll res=trs.query(1,A[i]);
		anss.add(A[i],res);
		trs.add(A[i],1);
	}
	FOR(i,1,Q){
		// two number <=L || >=R  delete
		cin>>L[i]>>R[i];
		if(L[i]==R[i]){
			cout<<0<<"\n";
			continue;
		}
		ll lans=ans;
		lans-=ansp.query(R[i],N);
		lans-=anss.query(1,L[i]);
		if(lans<0) cout<<"0\n";
		else cout<<lans<<"\n";
#ifdef LOCAL
    debug(lans);
#endif
	}
	
}

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/1168087702
*/

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

那么就是要注意这个特判

if(L[i]==R[i]){
	cout<<0<<"\n";
	continue;
}