b844 - 一堆按鈕

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個長度為 N 的數列，初始值皆為 0。接著進行 N 次操作，每次操作會指定一個按鈕編號 K，將從 K 位置開始到數列末尾的所有數字進行翻轉（0 變 1，1 變 0）。最後，進行 Q 次詢問，每次詢問指定一個位置 P，要求輸出 P 位置的數字值。

解題思路

這題的核心在於模擬按鈕操作，並有效地處理大量的翻轉操作。由於每次翻轉操作會影響從 K 位置到數列末尾的所有數字，我們可以利用排序和二分搜尋來優化查詢過程。

首先，將每次按鈕操作的按鈕編號 K 儲存到一個陣列 a 中，然後對這個陣列進行排序。對於每次詢問，我們使用二分搜尋找到小於或等於詢問位置 P 的最大按鈕編號 K。如果 P 小於等於 K，則表示 P 位置的數字被翻轉了奇數次，因此輸出 1。否則，P 位置的數字被翻轉了偶數次，因此輸出 0。

更具體地，如果 upper_bound(a, a+n, t) - a 的結果是偶數，表示位置 t 被翻轉了偶數次，因此數值為 0。反之，如果結果是奇數，表示位置 t 被翻轉了奇數次，數值為 1。

複雜度分析

• 時間複雜度: O(N log N + Q log N)
  • 排序陣列 a 需要 O(N log N) 的時間。
  • 對於每個詢問，二分搜尋需要 O(log N) 的時間，總共 Q 個詢問，因此需要 O(Q log N) 的時間。
• 空間複雜度: O(N)
  • 需要一個大小為 N 的陣列 a 來儲存按鈕編號。

程式碼

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <algorithm>
using namespace std;
int a[500001];
inline int read(){
	int a(0);
	char c('0');
	while(c>='0'){
		a=(a<<3)+(a<<1)+c-'0';
		c=getchar_unlocked();
	}
	return a;
}
int main(){
	int n,q,t;
	while(n=read()){
		q=read();
		for(int i=0;i<n;++i)
			a[i]=read();
		sort(a,a+n);
		while(q--){
			t=read();
			putchar_unlocked(((upper_bound(a,a+n,t)-a)&1)+48);
			putchar_unlocked('\n');
		}
	}
}