商丘哪里教做网站的,合肥百度推广公司哪家好,网站建站金融模板,中国建筑设计研究院官网解析
比较神奇的一道题。
考虑一个常规套路#xff1a;把询问离线#xff0c;移动右端点#xff0c;维护左端点答案。 考虑暴力维护#xff0c;对于当前的 aixa_ixaix#xff0c;左侧如图所示的这两条线上的点都可以产生新的可能答案。 容易构造使得单次产生的新点是…解析
比较神奇的一道题。
考虑一个常规套路把询问离线移动右端点维护左端点答案。 考虑暴力维护对于当前的 aixa_ixaix左侧如图所示的这两条线上的点都可以产生新的可能答案。 容易构造使得单次产生的新点是 O(n)O(n)O(n) 的无法接受。
如何优化 一个较为显然的结论是左端点答案单调不降。但这个“单调不降”也可以这么理解每次询问的是 minilransi\min_{il}^rans_iminilransi。 那么进而又有一个比较直观的“剪枝“如果在pos产生的答案不是其右侧的最小值那么它就一点用的没有。 考虑上线段树每个节点维护区间答案和区间的所有点先修改右侧并顺便记录这个右侧的最小值加上上面的剪枝。 然后它的复杂度就对了。
为什么 考虑一条线上同时被更新的两个点 a这个间隔是之前就已经存在的答案但左侧的点依然被更新了说明 bababa。 那么不难发现每次更新一个点单侧的距离至少减少一半所以至多只会更新 O(logV)O(\log V)O(logV) 个点。 总复杂度 O(nlognlogV)O(n\log n\log V)O(nlognlogV)。
代码
//luogu
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N4e5100;
//const int mod998244353;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m;
int a[N];#define mid ((lr)1)
#define ls (k1)
#define rs (k1|1)
int mn;
struct node{int ans;vectorintv;
}tr[N2];
void build(int k,int l,int r){for(int il;ir;i) tr[k].v.push_back(a[i]);sort(tr[k].v.begin(),tr[k].v.end());tr[k].ans2e9;if(lr) return;build(ls,l,mid);build(rs,mid1,r);return;
}
void update(int k,int l,int r,int p,int w){if(rp){int siztr[k].v.size()-1;//sort(tr[k].v.begin(),tr[k].v.end());int posupper_bound(tr[k].v.begin(),tr[k].v.end(),w)-tr[k].v.begin();if(possiz) tr[k].ansmin(tr[k].ans,tr[k].v[pos]-w);pos--;if(tr[k].v[pos]wrp) pos--;if(pos0) tr[k].ansmin(tr[k].ans,w-tr[k].v[pos]);if(lr) mnmin(tr[k].ans,mn); if(tr[k].ansmn) return; }if(pmid) update(rs,mid1,r,p,w);update(ls,l,mid,p,w);tr[k].ansmin(tr[ls].ans,tr[rs].ans); return;
}
int ask(int k,int l,int r,int x,int y){if(xlry) return tr[k].ans;int res2e9;if(xmid) resmin(res,ask(ls,l,mid,x,y));if(ymid) resmin(res,ask(rs,mid1,r,x,y));return res;
}
#undef mid
#undef ls
#undef rsstruct query{int l,id;
};
int ans[N];
vectorqueryq[N];
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();for(int i1;in;i) a[i]read();mread();for(int i1;im;i){int lread(),rread();q[r].push_back((query){l,i});}build(1,1,n);for(int i1;in;i){mn2e9;update(1,1,n,i,a[i]); for(query o:q[i]){ans[o.id]ask(1,1,n,o.l,i);}}for(int i1;im;i) printf(%d\n,ans[i]);return 0;
}
/**/
