http://codeforces.com/problemset/problem/765/F?(題目鏈接)

題意

　　給出$n$個數的序列，$m$次詢問，每次查詢區間$[l,r]$之間相差最小的兩個數的差。

Solution

　　迷，右轉題解→_→：jump

　　奇怪的線段樹

細節

　　不造

代碼

// codeforces 765F #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<vector> #include<cmath> #include<ctime> #define LL long long #define inf 2147483640 #define Pi acos(-1.0) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout) using namespace std;const int maxn=300010; int n,Q,ans,a[maxn],res[maxn]; struct data {int l,r,id;}q[maxn]; struct node {int l,r,s;vector<int> v;}tr[maxn<<2];bool cmp(data a,data b) {return a.r<b.r;} void build(int k,int s,int t) {tr[k].l=s;tr[k].r=t;tr[k].s=inf;if (s==t) {tr[k].v.push_back(a[s]);return;}int mid=(s+t)>>1;build(k<<1,s,mid);build(k<<1|1,mid+1,t);int i=0,j=0,ll=tr[k<<1].v.size(),rr=tr[k<<1|1].v.size();while (i<ll || j<rr) {if ((i<ll && tr[k<<1].v[i]<tr[k<<1|1].v[j]) || j==rr)tr[k].v.push_back(tr[k<<1].v[i++]);else tr[k].v.push_back(tr[k<<1|1].v[j++]);}for (int i=1;i<=t-s;i++) tr[k].s=min(tr[k].s,tr[k].v[i]-tr[k].v[i-1]); } int query(int k,int s,int t) {int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;if (l==s && r==t) return tr[k].s;if (t<=mid) return query(k<<1,s,t);else if (s>mid) return query(k<<1|1,s,t);else return min(query(k<<1,s,mid),query(k<<1|1,mid+1,t)); } void modify(int k,int p,int val) {int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;if (l==r) {tr[k].s=min(tr[k].s,abs(val-tr[k].v[0]));ans=min(ans,tr[k].s);return;}vector<int>::iterator t=lower_bound(tr[k].v.begin(),tr[k].v.end(),val);if (t==tr[k].v.end() || *t-val>=ans)if (t==tr[k].v.begin() || val-*--t>=ans) {ans=min(ans,tr[k].s);return;}if (p<=mid) modify(k<<1,p,val);else modify(k<<1|1,p,val),modify(k<<1,p,val);tr[k].s=min(tr[k].s,min(tr[k<<1].s,tr[k<<1|1].s)); } int main() {scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);scanf("%d",&Q);for (int i=1;i<=Q;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;sort(q+1,q+1+Q,cmp);build(1,1,n);int p=1;for (int i=1;i<=Q;i++) {while (p<q[i].r) ans=inf,modify(1,p,a[p+1]),p++;res[q[i].id]=query(1,q[i].l,q[i].r);}for (int i=1;i<=Q;i++) printf("%d\n",res[i]);return 0; }

?

轉載于:https://www.cnblogs.com/MashiroSky/p/6476643.html

總結

以上是生活随笔為你收集整理的【codeforces 765F】 Souvenirs的全部內容，希望文章能夠幫你解決所遇到的問題。

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