Choosing Ads

問題提出

• 給出長度為$n$的序列$A$,以及數$p$($20\le p\le 100$)
• $Q$次操作,兩種類型
  • $(1,l,r)$,區間賦值為$v$
  • $(2,l,r)$,區間出現頻率$\ge p\%$的數
• $n,Q\le 10^5$

問題解答

非常巧妙的一道題,用到了主元素的思想.

我們先考慮一個簡單的問題,如何在一個序列中找主元素(出現頻次$>50\%$的元素),要求$O(n)$的時間復雜度和$O(1)$的空間復雜度.

這是一個很經典的問題,我們用到的思想就是分組,主元素一組,其他元素一組,然后各組之間每次同時抵消掉$1$個元素,那么最后剩下的一組一定是主元素.

編程實現如下:

//算法1 int rec = a[0],cnt = 1; for(int i = 1;i < n;++i) {if(a[i] == rec) ++cnt;else if(--cnt == 0) rec = a[i],cnt = 1; }

如果有主元素的話,最后$rec$表示的一定是主元素.我們把變量$n$叫做主元素$rec$的平衡度.對于任一序列$A$,可以證明最壞情況下主元素的平衡度都至少為$1$.

我們再考慮一個問題.

將分別求出序列$A,B$的主元素$re{c}_A$和$re{c}_B$,以及它們的平衡度$cn{t}_A$和$cn{t}_B$.

將$A,B$拼成一個新的序列,那么主元素也一定是$re{c}_A$和$re{c}_B$中的其中一個.這是很顯然的,證明略去.

現在我們要判定主元素到底是$re{c}_A$還是$re{c}_B$,我們只需要將他們相互抵消即可,換句話說看誰的$cnt$大,誰就是.

你可以理解為這就相當于直接在$AB$序列上跑$算法1$,只不過序列的順序有所改變.

這樣的話,我們有了$2$個子序列的主元素以及平衡度,我們就可以得到該序列的主元素以及平衡度.

假設$cn{t}_A>cn{t}_B$主元素就是$re{c}_{AB}=re{c}_A$,平衡度就是$cn{t}_{AB}=cn{t}_A?cn{t}_B$

這樣我們就可以得到一個分治的算法,即算法2.

至此,基礎知識就說完了,我們回到這道題中.

這道題要求的是$\ge p\%$的是一定要輸出,因此主元素有好多個至多$k=?\frac{100}{p}?$個.

我們可以根據一個序列的有$k$個主元素分為$k+1$組,其中每個主元素自己一組,然后其他元素一組.

用$k$個變量記錄該序列的$k$個主元素,用$k$個變量記錄每個元素的平衡度,每遇到一個元素,判斷$k$個位置中有沒有出現過,出現過就該位置平衡度+1,否則判斷有沒有空位,有的話就作為一個新的主元素,平衡度設置為1.再否則的話就令所有$k$個位置的平衡度-1(相當于抵消操作),如果平衡度為0就將這個元素拿走.

剛才說的是線性掃的做法,這道題要用線段樹維護,就要該進程類似算法2的做法.

這道題用平衡樹來維護上述信息,然后用算法2的精髓來實現線段合并操作.

代碼

By csfxjtu96, contest: VK Cup 2016 - Round 3, problem: (G) Choosing Ads, Accepted, ##include <iostream> #include <unordered_map> #include <cstring> #include <algorithm>#define pr(x) std::cout << #x <<" : " << x << std::endl #define rep(i,a,b) for(int i = a;i <= b;++i) #define clr(x) memset(x,0,sizeof(x))typedef std::pair<int,int> pii;const int N = 150001; struct node {int len;pii ps[5];node(){len = 0;clr(ps);} }seg[N<<2];int tag[N<<2]; int num[N]; int n,m,p,L;pii ps[10]; int mp[N],vis[N]; inline node maintain(node &lch,node &rch) {node res = node();res.len = lch.len + rch.len;rep(i,0,L-1) {mp[lch.ps[i].first] += lch.ps[i].second;mp[rch.ps[i].first] += rch.ps[i].second;}int pc = 0;memset(ps,0,sizeof(ps));rep(i,0,L-1) {if(!vis[lch.ps[i].first]) {ps[pc++] = (pii){lch.ps[i].first,mp[lch.ps[i].first]};vis[lch.ps[i].first] = 1;}if(!vis[rch.ps[i].first]) {ps[pc++] = (pii){rch.ps[i].first,mp[rch.ps[i].first]};vis[rch.ps[i].first] = 1;}}rep(i,0,L-1) {vis[rch.ps[i].first] = vis[lch.ps[i].first] = mp[lch.ps[i].first] = mp[rch.ps[i].first] = 0;}std::sort(ps,ps+pc,[](pii &p1,pii &p2){return p1.second > p2.second;});int cc = ps[L].second;rep(i,0,L-1) {ps[i].second -= cc;res.ps[i] = ps[i];}return res; }inline void pushdown(int o) {if(tag[o]) {tag[o<<1] = tag[o<<1|1] = tag[o];clr(seg[o<<1].ps);clr(seg[o<<1|1].ps);seg[o<<1].ps[0] = std::make_pair(tag[o],seg[o<<1].len);seg[o<<1|1].ps[0] = std::make_pair(tag[o],seg[o<<1|1].len);tag[o] = 0;} }inline void change(int o,int l,int r,int cl,int cr,int val) {if(cl <= l && r <= cr) {tag[o] = val;clr(seg[o].ps);seg[o].ps[0] = (pii){val,r-l+1};return ;}if(r < cl || cr < l) return ;int mid = (l + r) >> 1;pushdown(o);change(o<<1,l,mid,cl,cr,val);change(o<<1|1,mid+1,r,cl,cr,val);seg[o] = maintain(seg[o<<1],seg[o<<1|1]); }inline node query(int o,int l,int r,int ql,int qr) {if(ql <= l && r <= qr)return seg[o];if(r < ql || qr < l) return node();int mid = (l + r) >> 1;pushdown(o);node lch = query(o<<1,l,mid,ql,qr);node rch = query(o<<1|1,mid+1,r,ql,qr);node res = maintain(lch,rch);return res; }inline void build(int o,int l,int r) {if(l == r) {seg[o] = node();seg[o].len = 1;seg[o].ps[0] = (pii){num[l],1};return ;}int mid = (l + r) >> 1;build(o<<1,l,mid);build(o<<1|1,mid+1,r);seg[o] = maintain(seg[o<<1],seg[o<<1|1]); }int main() {std::ios::sync_with_stdio(false);std::cin >> n >> m >> p;L = 100 / p;rep(i,1,n) std::cin >> num[i];build(1,1,n);while(m--) {int tp,l,r,x;std::cin >> tp;if(tp == 1) {std::cin >> l >> r >> x;change(1,1,n,l,r,x);}else if(tp == 2) {std::cin >> l >> r;node res = query(1,1,n,l,r);int cnt = 0;rep(i,0,L-1) {if(res.ps[i].second) cnt++;}std::cout << cnt;rep(i,0,L-1) {if(res.ps[i].second) std::cout << " " << res.ps[i].first;}std::cout << std::endl;}}return 0; }

總結

以上是生活随笔為你收集整理的线段树-Chossing Ads-分治,主元素思想,神题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。