昆山市建设局网站,途途外贸企业网站管理系统,免费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;
}
