洛谷P15676 [ICPC 2024 Jakarta R] Microwavable Subsequence题解

[ICPC 2024 Jakarta R] Microwavable Subsequence考虑如何求f ( x , y ) f(x,y)f(x,y)。我们可以把原序列中所有x xx元素和y yy元素提出来形成一个新的序列那么f ( x , y ) f(x,y)f(x,y)即为相邻的异色对数量。对于原序列的每个位置i ii我们可以求出l i l_ili​为i ii前面第一个与i ii颜色相同的位置那么[ l i 1 , i ] [l_i1,i][li​1,i]中出现的所有颜色都能够与i ii组成异色对。现在问题就转化为了如何求一个区间中出现了多少种颜色有两种做法莫队离线后就是板子题时间复杂度O ( N N ) O(N\sqrt N)O(NN​)。树状数组具体的将当前每个元素出现的最晚位置打上标记求出区间[ l i 1 , i ] [l_i1,i][li​1,i]中有多少标记即可时间复杂度O ( N log ⁡ N ) O(N\log N)O(NlogN)。#includebits/stdc.husingnamespacestd;constintN3e55;intn,m,a[N];inttong[N],l[N],r[N];structjs{intl,r,ll;}b[N1];intcnt0,B;boolcmp(js x,js y){if(x.lly.ll){if(x.ll%2)returnx.ry.r;returnx.ry.r;}returnx.lly.ll;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnm;Bsqrt(n);for(inti1;in;i)cina[i];longlongres0,ct0,ctt0;for(inti1;in;i){l[i]tong[a[i]];if(!l[i])resct;if(!tong[a[i]])ct;tong[a[i]]i;}memset(tong,0,sizeof(tong));for(intin;i1;i--){r[i]tong[a[i]];tong[a[i]]i;}ctctt0;for(inti1;im;i)if(tong[i])ct;elsectt;res1ll*ct*ctt;memset(tong,0,sizeof(tong));for(inti1;in;i)if(l[i]1i-1)b[cnt]{l[i]1,i-1};for(inti1;icnt;i)b[i].ll(b[i].lB-1)/B;sort(b1,b1cnt,cmp);intl1,r0;longlongnow0;for(inti1;icnt;i){while(rb[i].r)r,now(!tong[a[r]]),tong[a[r]];while(lb[i].l)l--,now(!tong[a[l]]),tong[a[l]];while(rb[i].r)now-(tong[a[r]]1),tong[a[r]]--,r--;while(lb[i].l)now-(tong[a[l]]1),tong[a[l]]--,l;resnow;}coutres;return0;}