題面 。
看到這道題 ， 我第一反應就是莫隊 。簡化題意：給一個序列，給一些詢問 ， 每個詢問包含三個區間代表序列的三個子序列，要求出這三個對應子序列去掉三個子序列都具有的公共數字后剩下的數字個數 。
我甚至也猜出了把所有詢問的三個區間壓到一起處理然后分別計算對應詢問答案 。
但是 ， 這么復雜的貢獻用什么東西存？難道要開一個數組 query_appear_time[ 100000 ][ 100000 ]?
于是我打消了這個念頭，最后還是看題解做的 。
令三個區間為a1,a2,a3 。
要求的答案就是a1數字個數-公共數字個數+a2數字個數-公共數字個數+a3數字個數-公共數字個數 。
即a1，a2，a3數字個數之和-公共數字個數*3 。
數字個數之和就是區間長度 ， 那么問題就轉化為了求三個區間的公共數字個數 。
對序列進行離散化，原本的1e9值域就變成了1e5值域 。
然后讀入所有的詢問區間按標準莫隊進行排序，處理每個區間并且將其所有的數字出現個數轉移到對應詢問中 。接下來合并 。
到這一步其實并不難想，關鍵在于怎么求公共數字個數 。
前面我提到顯然存不了一個query_appear_time[ 100000 ][ 100000 ]，但是有一個數據結構叫bitset 。
bitset的一位只占一個比特，相當于一個二進制數，可以進行位運算 。
我們可以用bitset一位代表一個數字存儲區間內值域，這在 洛谷3674小清新人渣的本愿 中十分有用 。
但是這題要存儲區間每個數字個數 。
做法：
我們令p[i]為整個序列內小于等于i的數字的個數，cnt[i]為數字i在 當前區間 中出現的次數 ， 建一個bitset<1e5>range 。
每當讀入一個數字x我們令range[p[x]-cnt[x]]為1并令cnt[x]++ ， 每當查詢完一個區間我們用這樣一個bitset記錄這個區間 。
代表兩個區間的bitset與（&）一下然后用range.count()求出新bitset的1個數，就是這兩個區間的公共數字個數 。
原理：
如下圖
對于一個區間，對于數字i，這個區間的bitset第p[ i ]位到第p[ i ]-cnt[ i ]位為1 ， 公共數字個數就是min(cnt[i])
那么對于兩個數的min(cnt[i]) ， p[i]~p[i]-min(cnt[i])+這個范圍肯定全是1.
取與之后，p[ i ]~p[i-1]+1位的1的數量就是公共的i的出現次數 。
文章插圖
至于計算每個區間的bitset，這么一大堆區間放在一起，顯然可以莫隊 。
然后分別計算每個區間的bitset ， 再對每個詢問，將其三個區間的bitset與起來求1的個數，就是這個詢問所要求的三個區間的公共元素數量 。
莫隊操作，tmp為當前區間狀態 。
for(int i=2;i<=m;i++){while(l>q[i].l)l--,tmp[p[a[l]]-tim[a[l]]]=1,tim[a[l]]++;while(r<q[i].r)r++,tmp[p[a[r]]-tim[a[r]]]=1,tim[a[r]]++;while(l<q[i].l)tim[a[l]]--,tmp[p[a[l]]-tim[a[l]]]=0,l++;while(r>q[i].r)tim[a[r]]--,tmp[p[a[r]]-tim[a[r]]]=0,r--;if(!vis[(q[i].pos-1)/3+1])res[(q[i].pos-1)/3+1]=tmp,vis[(q[i].pos-1)/3+1]=1;//神奇的O(1)復制elseres[(q[i].pos-1)/3+1]&=tmp;}合并答案
for(int i=1;i<=m;i++){int pub=res[i].count();printf("%d\n",cnt[i]-pub*3);}至此，我們已經得到了一個時間復雜度n3/2的莫隊算法 。
但是還有一個問題 。
bitset雖然小，但是一個bitset要開1e5位 。這樣的bitset開不了題目要求的1e5個（每個詢問要存三個區間） 。
那么就只開詢問數量的一部分（我開的1/4）的bitset，然后一次處理問題的一小部分就可以了 。
文章插圖
文章插圖
#include<bits/stdc++.h>using namespace std;const int h=100070;int n,m;int a[h],line[h];int p[h];map<int,int>rk;int ntot=0;bool vis[h/4+10];bitset<100010>res[h/4+10];bitset<100010>tmp;int len;int get_pos(int x){return (x-1)/len+1;}struct node{int l,r;int pos;}q[h];bool cmp(node x,node y){if(get_pos(x.l)==get_pos(y.l))return x.r<y.r;return x.l<y.l;}int tim[h];int ans;int part;int cnt[h];void solve(){if(!part)return;tmp.reset();for(int i=1;i<=part;i++)cnt[i]=0,res[i].reset(),vis[i]=0;len=sqrt(part);for(int i=1;i<=part*3;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].pos=i,cnt[(i-1)/3+1]+=q[i].r-q[i].l+1;sort(q+1,q+part*3,cmp);int l=q[1].l,r=q[1].r;for(int i=l;i<=r;i++)tmp[p[a[i]]-tim[a[i]]]=1,tim[a[i]]++;vis[(q[1].pos-1)/3+1]=1,res[(q[1].pos-1)/3+1]=tmp;for(int i=2;i<=part*3;i++){while(l>q[i].l)l--,tmp[p[a[l]]-tim[a[l]]]=1,tim[a[l]]++;while(r<q[i].r)r++,tmp[p[a[r]]-tim[a[r]]]=1,tim[a[r]]++;while(l<q[i].l)tim[a[l]]--,tmp[p[a[l]]-tim[a[l]]]=0,l++;while(r>q[i].r)tim[a[r]]--,tmp[p[a[r]]-tim[a[r]]]=0,r--;if(!vis[(q[i].pos-1)/3+1])res[(q[i].pos-1)/3+1]=tmp,vis[(q[i].pos-1)/3+1]=1;elseres[(q[i].pos-1)/3+1]&=tmp;}for(int i=1;i<=part;i++){int pub=res[i].count();printf("%d\n",cnt[i]-pub*3);}for(int i=1;i<=ntot;i++)tim[i]=0;}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]),line[i]=a[i];sort(line+1,line+1+n);for(int i=1;i<=n;i++)if(line[i]!=line[i-1])rk[line[i]]=++ntot,p[ntot-1]=i-1;p[ntot]=n;for(int i=1;i<=n;i++)a[i]=rk[a[i]];part=h/4;while(m)part=min(part,m),solve(),m-=part;return 0;}
推薦閱讀
- .NET性能優化-是時候換個序列化協議了
- 華為云 MRS 基于 Apache Hudi 極致查詢優化的探索實踐
- Sql Server性能排查和優化懶人攻略
- 附踩坑記錄 我用EasyExcel優化了公司的導出
- .NET性能優化-復用StringBuilder
- UE優化性能
- 前端性能優化——首屏時間&&白屏時間
- 「MySQL高級篇」explain分析SQL，索引失效&&常見優化場景
- 完全背包問題 —— 貪心優化 DP 范圍
- 項目案例使用有效 解決ffmpeg的播放攝像頭的延時優化問題