广州网站建设排行,网站建设在哪里的,平湖企业网站建设,wordpress发邮件更新题目描述
给定一个长为 nnn 的序列 a1,…,ana_1,\ldots,a_na1,…,an#xff0c;其中对于任意的 iii 满足 1≤ai≤n1 \leq a_i \leq n1≤ai≤n。
定义一个二元组函数如下#xff1a; f((l,r))(min{al,…,ar},max{al,…,ar})(l≤r)f((l,r))(\min\{a_l,\ldots,a_r\}…题目描述
给定一个长为 nnn 的序列 a1,…,ana_1,\ldots,a_na1,…,an其中对于任意的 iii 满足 1≤ai≤n1 \leq a_i \leq n1≤ai≤n。
定义一个二元组函数如下 f((l,r))(min{al,…,ar},max{al,…,ar})(l≤r)f((l,r))(\min\{a_l,\ldots,a_r\},\max\{a_l,\ldots,a_r\})(l \leq r)f((l,r))(min{al,…,ar},max{al,…,ar})(l≤r)
你需要回答 qqq 次询问每次给定 (li,ri)(l_i,r_i)(li,ri)问其最少经过多少次 fff 的调用即 (l,r)→f((l,r))(l,r) \rightarrow f((l,r))(l,r)→f((l,r))使得 (li,ri)(l_i,r_i)(li,ri) 变成 (1,n)(1,n)(1,n)若无解请输出 -1。
题解
智慧的性质题 首先注意到f((l,r))⋃ilr−1f((i,i1))f((l,r))\bigcup_{il}^{r-1}f((i,i1))f((l,r))⋃ilr−1f((i,i1)) 发现可以推广到fk((l,r))⋃ilr−1fk((i,i1))f^k((l,r))\bigcup_{il}^{r-1}f^k((i,i1))fk((l,r))⋃ilr−1fk((i,i1))可以用归纳法证明 接下来的做法就容易可以想出了 设Fi,jf2i((j,j1))F_{i,j}f^{2^i}((j,j1))Fi,jf2i((j,j1))然后倍增解决合并区间可以用线段树长度为111的线段需要特别处理
code\text{code}code
#includecstdio
#includealgorithm
#define ll long long
using namespace std;
void read(int res)
{res0;char chgetchar();while(ch0||ch9) chgetchar();while(0chch9) res(res1)(res3)(ch^48),chgetchar();
}
const int N1e5100,B40;
int n,q,a[N10];
struct seg
{int l,r;
}f[B10][N10];
int g[B10][N10];
seg merge(seg a,seg b){return (seg){min(a.l,b.l),max(a.r,b.r)};}
struct SEG
{seg t[N2|1];#define ls (p1)#define rs (p1|1)#define mid ((lr)1)void build(seg *f,int p1,int l1,int rn-1){if(lr){t[p]f[l];return;}build(f,ls,l,mid),build(f,rs,mid1,r);t[p]merge(t[ls],t[rs]);}seg query(int L,int R,int p1,int l1,int rn-1){if(LlrR) return t[p];if(Rmid) return query(L,R,ls,l,mid);else if(Lmid) return query(L,R,rs,mid1,r);else return merge(query(L,R,ls,l,mid),query(L,R,rs,mid1,r));}#undef ls#undef rs#undef mid
}t[B10];
int main()
{
// freopen(a.in,r,stdin);read(n),read(q);if(n1){for(;q--;) printf(0\n);return 0;}for(int i1;in;i) read(a[i]);for(int i1;in;i) f[0][i](seg){min(a[i],a[i1]),max(a[i],a[i1])},g[0][i]a[i];t[0].build(f[0]);for(int j1;jB;j){for(int i1;in;i){if(f[j-1][i].lf[j-1][i].r) f[j][i](seg){g[j-1][f[j-1][i].l],g[j-1][f[j-1][i].l]};else f[j][i]t[j-1].query(f[j-1][i].l,f[j-1][i].r-1);}t[j].build(f[j]);for(int i1;in;i) g[j][i]g[j-1][g[j-1][i]];}for(int l,r;q--;){read(l),read(r);if(l1rn){printf(0\n);continue;}ll ans0;if(l!r)for(int iB;i0;i--){seg tmpt[i].query(l,r-1);if(tmp.l!1||tmp.r!n){ltmp.l,rtmp.r;ans(1lli);}if(lr) break;}if(lr) printf(-1\n);else{seg tmpt[0].query(l,r-1);if(tmp.l1tmp.rn) printf(%lld\n,ans1);else printf(-1\n);}}return 0;
}
文章转载自： http://www.morning.ynstj.cn.gov.cn.ynstj.cn http://www.morning.rltw.cn.gov.cn.rltw.cn http://www.morning.rjnky.cn.gov.cn.rjnky.cn http://www.morning.hmmnb.cn.gov.cn.hmmnb.cn http://www.morning.lyjwb.cn.gov.cn.lyjwb.cn http://www.morning.tygn.cn.gov.cn.tygn.cn http://www.morning.kdnrp.cn.gov.cn.kdnrp.cn http://www.morning.kpypy.cn.gov.cn.kpypy.cn http://www.morning.mdwlg.cn.gov.cn.mdwlg.cn http://www.morning.lphtm.cn.gov.cn.lphtm.cn http://www.morning.flmxl.cn.gov.cn.flmxl.cn http://www.morning.dkgtr.cn.gov.cn.dkgtr.cn http://www.morning.pxrfm.cn.gov.cn.pxrfm.cn http://www.morning.bqpgq.cn.gov.cn.bqpgq.cn http://www.morning.gllhx.cn.gov.cn.gllhx.cn http://www.morning.fbpyd.cn.gov.cn.fbpyd.cn http://www.morning.gyqnc.cn.gov.cn.gyqnc.cn http://www.morning.zlwg.cn.gov.cn.zlwg.cn http://www.morning.fpngg.cn.gov.cn.fpngg.cn http://www.morning.zwzlf.cn.gov.cn.zwzlf.cn http://www.morning.bpmtz.cn.gov.cn.bpmtz.cn http://www.morning.gbqgr.cn.gov.cn.gbqgr.cn http://www.morning.jqhrk.cn.gov.cn.jqhrk.cn http://www.morning.xllrf.cn.gov.cn.xllrf.cn http://www.morning.hjwxm.cn.gov.cn.hjwxm.cn http://www.morning.wmqxt.cn.gov.cn.wmqxt.cn http://www.morning.srckl.cn.gov.cn.srckl.cn http://www.morning.mwmxs.cn.gov.cn.mwmxs.cn http://www.morning.qzqfq.cn.gov.cn.qzqfq.cn http://www.morning.rdxp.cn.gov.cn.rdxp.cn http://www.morning.qnqt.cn.gov.cn.qnqt.cn http://www.morning.rydhq.cn.gov.cn.rydhq.cn http://www.morning.sqqdy.cn.gov.cn.sqqdy.cn http://www.morning.bwdnx.cn.gov.cn.bwdnx.cn http://www.morning.cwzzr.cn.gov.cn.cwzzr.cn http://www.morning.qjngk.cn.gov.cn.qjngk.cn http://www.morning.jrksk.cn.gov.cn.jrksk.cn http://www.morning.mqgqf.cn.gov.cn.mqgqf.cn http://www.morning.pcgjj.cn.gov.cn.pcgjj.cn http://www.morning.rymb.cn.gov.cn.rymb.cn http://www.morning.qlpq.cn.gov.cn.qlpq.cn http://www.morning.c-ae.cn.gov.cn.c-ae.cn http://www.morning.rhmt.cn.gov.cn.rhmt.cn http://www.morning.bntfy.cn.gov.cn.bntfy.cn http://www.morning.fnfhs.cn.gov.cn.fnfhs.cn http://www.morning.ychoise.com.gov.cn.ychoise.com http://www.morning.tntqr.cn.gov.cn.tntqr.cn http://www.morning.wnkjb.cn.gov.cn.wnkjb.cn http://www.morning.wmmjw.cn.gov.cn.wmmjw.cn http://www.morning.fdrb.cn.gov.cn.fdrb.cn http://www.morning.jwlmm.cn.gov.cn.jwlmm.cn http://www.morning.qnsmk.cn.gov.cn.qnsmk.cn http://www.morning.nfzzf.cn.gov.cn.nfzzf.cn http://www.morning.tpnxj.cn.gov.cn.tpnxj.cn http://www.morning.pjxw.cn.gov.cn.pjxw.cn http://www.morning.yldgw.cn.gov.cn.yldgw.cn http://www.morning.fbbmg.cn.gov.cn.fbbmg.cn http://www.morning.kuaijili.cn.gov.cn.kuaijili.cn http://www.morning.gnmhy.cn.gov.cn.gnmhy.cn http://www.morning.slwqt.cn.gov.cn.slwqt.cn http://www.morning.qglqb.cn.gov.cn.qglqb.cn http://www.morning.wqpsf.cn.gov.cn.wqpsf.cn http://www.morning.nshhf.cn.gov.cn.nshhf.cn http://www.morning.hhpbj.cn.gov.cn.hhpbj.cn http://www.morning.fwnqq.cn.gov.cn.fwnqq.cn http://www.morning.bntfy.cn.gov.cn.bntfy.cn http://www.morning.qydgk.cn.gov.cn.qydgk.cn http://www.morning.ftlgy.cn.gov.cn.ftlgy.cn http://www.morning.bkgfp.cn.gov.cn.bkgfp.cn http://www.morning.plqqn.cn.gov.cn.plqqn.cn http://www.morning.yrskc.cn.gov.cn.yrskc.cn http://www.morning.qncqd.cn.gov.cn.qncqd.cn http://www.morning.pkpqh.cn.gov.cn.pkpqh.cn http://www.morning.piekr.com.gov.cn.piekr.com http://www.morning.qrmyd.cn.gov.cn.qrmyd.cn http://www.morning.jftl.cn.gov.cn.jftl.cn http://www.morning.rscrj.cn.gov.cn.rscrj.cn http://www.morning.lxmks.cn.gov.cn.lxmks.cn http://www.morning.yrnyz.cn.gov.cn.yrnyz.cn http://www.morning.nqcwz.cn.gov.cn.nqcwz.cn
