f339(ver2.0) - Error
題目描述
題目要求找出數組中所有滿足條件的配對。條件是，對於數組中的每個元素 a[i]，如果 a[i] 不等於 i，則找到一個 a[i] 到 a[a[i]] 的區間，並將這個區間的最大值賦給 a[i]。然後，遍歷數組，找出所有 s 和 k 的配對，其中 s 和 k 滿足 a[s] == a[k] 且 s < k。
解題思路
程式碼首先初始化一個數組 a，其中 a[i] = i。然後，它讀取 m 個查詢，對於每個查詢 x 和 y，它將 a[x] 更新為 max(a[x], y)。接下來，程式碼遍歷數組 a，如果 a[i] 不等於 i，則找到從 a[i] 到 a[a[i]] 的區間的最大值，並將其賦給 a[i]。最後，程式碼遍歷數組 a，找出所有滿足條件的配對 s 和 k，並將它們輸出。
複雜度分析
- 時間複雜度: O(n + m + n) = O(n + m)，其中 n 是數組的大小，m 是查詢的數量。初始化數組需要 O(n)，處理查詢需要 O(m)，更新數組需要 O(n)，查找配對需要 O(n)。
- 空間複雜度: O(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")
#define max( x, y ) ( ((x)>(y)) ? (x):(y) )
#include <stdio.h>
int a[100001];
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[7],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
int main(){
int n,m,x,y,s=0,k;
n=read();
m=read();
for(int i=0;i<=n;++i)
a[i]=i;
while(m--){
x=read();
y=read();
a[x]=max(a[x],y);
}
for(int i=0,l;i<=n;++i){
if(a[i]!=i){
l=a[i];
for(int j=i+1;j<=l;++j)
if(a[j]>l)
l=a[j];
a[i]=l;
i=l-1;
}
}
while(s<n){
while(s<a[s])
s=a[s];
k=s;
while(k==a[k]&&k<n)++k;
if(k!=s&&k<=n){
write(s);
putchar_unlocked(' ');
write(k);
putchar_unlocked('\n');
s=k-1;
}
++s;
}
}