CF765F Souvenirs

題意翻譯

給出\(n(2 \le n \le 10^5 )\) ，一個長為\(n\)的序列\(a（0 \le a_i \le 10^9 )\)。

給出\(m(1\le m \le 2*10^5 )\)，接下來\(m\)組詢問。

每組詢問給出一個\(l,r(1\le l < r\le n )\)，代表詢問最小的\(|a_i-a_j|\) 的值（\(l\le i <j\le r\) ，\(a_i\) 可以等于\(a_j\) ）

---

蒟蒻\(\tt{Dew}\)又雙叒叕花大幾個小時去弄懂這個題，而直到現在，我也只是明白了這個題為什么可以這么做，卻不是太明白這種題如何去想。

---

首先可以看出這個題說不定可以莫隊套平衡樹卡過去，沒什么別的想法還是寫寫吧，估計比暴力還是強一些的。

然后考慮一些思考的出發點，比如

• 值域？二分值域？劃分修改？
• 移動詢問的指針？
• 把詢問給線段樹分治掉？
• 單調性？

---

不妨先考慮一些簡單的暴力，比如說，我們把詢問按右指針排序，然后開始處理它們。

若當前處理到的位置為\(r\)，我們對\(r\)前面的位置\(i\)維護答案數組\(ans_i\)，代表區間\([i,r]\)的答案，每次移動右指針時，我們暴力更新每個位置的答案。

考慮修補這個暴力。

• 發現詢問\(ans_i\)也可以看做詢問\(\min_{i\le k <r} ans_k\)，這啟發我們去區間查詢，然后每次移動時不修改所有的值，選擇線段樹進行維護。
• 具體的，在線段樹上點代表的區間上，存下這個區間所有的\(a_i\)，然后在這個區間上二分就能夠更新這個區間的答案了。
• 然后發現復雜度更高了，按道理有些值是不需要修改的，哪些值呢？
• 發現\(ans_i\)數組是單調不升的。如果我們成功修改了位置靠右的某個值，并設當前的答案為\(mi\)(注意這個是包含原本節點的答案的最小值)，那么在一個某個在\(Ta\)左邊的節點上貢獻的答案不如\(mi\)時，我們就沒有必要進入這個節點的子節點了。
• 這樣做的復雜度單次操作是\(\log n \log Maxa_i\)的，原因其實很簡單，每次成功貢獻答案后答案必定減半。為什么？如果\(r\)對\(j\)的答案為\(mi_j\)，\(r\)對\(i\)的答案為\(mi_i\)，為了避免\(i\)直接把\(j\)給更新掉，一定有\(mi_i< \frac{mi_j}{2}\)

---

總結：積累做題經驗,多開腦洞..

---

Code:

#include <cstdio> #include <algorithm> #include <vector> const int N=1e5+10; struct node {int i,l,r;bool friend operator <(node n1,node n2){return n1.r<n2.r;} }q[N<<2]; int ans[N<<2],Ans[N<<2],n,m,a[N],mi; std::vector <int> seg[N<<2]; int min(int x,int y){return x<y?x:y;} #define ls id<<1 #define rs id<<1|1 const int inf=0x3f3f3f3f; void build(int id,int l,int r) {for(int i=l;i<=r;i++) seg[id].push_back(a[i]);std::sort(seg[id].begin(),seg[id].end());ans[id]=inf;if(l==r) return;int mid=l+r>>1;build(ls,l,mid),build(rs,mid+1,r); } void change(int id,int l,int r,int p,int x) {if(r<=p){std::vector <int>::iterator it=std::upper_bound(seg[id].begin(),seg[id].end(),x);if(it!=seg[id].end()) ans[id]=min(ans[id],*it-x);if(it!=seg[id].begin()) ans[id]=min(ans[id],x-*(it-1));if(mi<=ans[id]) return;//右邊已經有比Ta優秀的了if(l==r){mi=min(mi,ans[id]);return;}}int mid=l+r>>1;if(p>mid) change(rs,mid+1,r,p,x);//注意先走右邊change(ls,l,mid,p,x);ans[id]=min(ans[id],min(ans[ls],ans[rs]));mi=min(mi,ans[id]);//最后更新Ta } int query(int id,int L,int R,int l,int r) {if(L==l&&R==r) return ans[id];int Mid=L+R>>1;if(r<=Mid) return query(ls,L,Mid,l,r);else if(l>Mid) return query(rs,Mid+1,R,l,r);else return min(query(ls,L,Mid,l,Mid),query(rs,Mid+1,R,Mid+1,r)); } int main() {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",a+i);build(1,1,n);scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].i=i;}std::sort(q+1,q+1+m);for(int p=1,i=2;i<=n;i++){mi=inf;change(1,1,n,i-1,a[i]);for(;p<=m&&q[p].r<=i;++p)Ans[q[p].i]=query(1,1,n,q[p].l,i);}for(int i=1;i<=m;i++)printf("%d\n",Ans[i]);return 0; }

---

2018.11.29

轉載于:https://www.cnblogs.com/butterflydew/p/10040347.html

總結

以上是生活随笔為你收集整理的CF765F Souvenirs 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

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