洛谷 P4135 作詩題解

2026-05-10 生活百科

題面。
之前做過一道很類似的題目洛谷P4168蒲公英，然后看到這題很快就想到了解法，做完這題可以對比一下，真的很像。
題目要求區間內出現次數為正偶數的數字的數量。
數據范圍1e5，可以分塊。
我們預處理出這么兩個數組。
一個是某個數字出現次數的分塊前綴和，這個很簡單。
一個是sum[ i ][ j ]代表從第i個分塊到第j個分塊出現次數為正偶數的數字的個數。
這個數組很好維護，只需要枚舉左端點分塊和右端點分塊然后統計數字出現次數即可。
這些代碼里有一些細節，可以結合注釋理解。
for(int i=1;i<=get_pos(n);i++){ int kin=0; for(int j=i;j<=get_pos(n);j++){ for(int k=(j-1)*len+1;k<=min(n,j*len);k++){//這里有一些細節 tmp[a[k]]++; if((tmp[a[k]]&1))//如果這個數加完之后變成了奇數 if(tmp[a[k]]>1)//如果加完之后出現次數大于一，那么這個數就作為正偶數被統計進答案了，要減掉 kin--; else//否則這個數在加一之前沒有被統計過，沒有必要更改，這里寫個else是因為防止與下面那個else產生沖突 kin+=0; else//加完之后如果變成了偶數那肯定從奇數變成了正偶數，對答案有貢獻 kin++; } sum[i][j]=kin; } for(int j=1;j<=c;j++)//清空輔助數組 tmp[j]=0; }接下來處理詢問。
對于詢問的l,r，算出其所在的分塊lb,rb 。
若l，r所在分塊相同或相鄰則暴力計算，時間復雜度n1/2 。
若l，r所在分塊之間相隔至少一個分塊，那么先將答案設成這兩個分塊之間的出現次數為正偶數的數字數量。
然后，計算兩邊散塊內數字對答案的貢獻。
情況較多，可結合注釋理解。
void get_q(){ ans=0; for(int i=l;i<=lb*len;i++){ tmp[a[i]]++; if(tmp[a[i]]&1)//如果這個數在散塊中出現次數為奇數 if((tim[rb-1][a[i]]-tim[lb][a[i]])&1)//如果它在中間塊中出現次數為奇數，那么它沒有被預先統計進答案里，且目前它對答案有貢獻 ans++; else//如果這個數在中間塊中出現次數為偶數 if(tim[rb-1][a[i]]-tim[lb][a[i]]>0)//如果這個數在中間塊中出現次數為正偶數，那么它已經作為答案被統計過了，現在不符合條件要減掉 ans--; else//這個數并沒有作為答案被統計過 if(tmp[a[i]]>1)//如果這個數在散塊中之前已經作為正偶數被統計了，要減掉 ans--; else//否則并沒有影響 ans-=0; else//這個數在散塊中出現次數為偶數 if(tim[rb-1][a[i]]-tim[lb][a[i]]&1)//如果這個數在中間塊中出現次數為奇數，那么這個數的出現次數被作為正偶數統計過，要減掉 ans--; else//否則這個數之前沒有算進答案里，要加進去 ans++; } for(int i=(rb-1)*len+1;i<=r;i++){//以下分類同上 tmp[a[i]]++; if(tmp[a[i]]&1) if((tim[rb-1][a[i]]-tim[lb][a[i]])&1) ans++; else if(tim[rb-1][a[i]]-tim[lb][a[i]]>0) ans--; else if(tmp[a[i]]>1) ans--; else ans-=0; else if(tim[rb-1][a[i]]-tim[lb][a[i]]&1) ans--; else ans++; } for(int i=l;i<=lb*len;i++)//清空輔助數組 tmp[a[i]]--; for(int i=(rb-1)*len+1;i<=r;i++) tmp[a[i]]--; ans+=sum[lb+1][rb-1];}

推薦閱讀

上一篇：帶權bitset?/bitset優化莫隊模板洛谷P4135 Ynoi2016 掉進兔子洞題解

下一篇：洛谷P4168 蒲公英分塊處理區間眾數模板