CF1707E Replace

· · 个人记录

*3500。把我吓到了，其实这题比较水，已经快做出来了。
顺便一提 CF 怎么这么喜欢出 ST 表。

二元组不好看，换成 f: \text{Interval} \to \text{Interval}（

首先对于同一个 l，区间随右端点增大单调不减。但是这个好像没什么用。

然后观察可以发现这个 f([l,r]) = f([l,x_1]) \bigcup f([x_1+1,x_2])\bigcup \dotsb \bigcup f([x_k+1,r])，其中 x_i \lt x_{i+1},x_i \in [l,r]。

也就是随便戳若干断点，分割出的区间的函数并就是整个区间的函数。

其实这是一个更强的结论：若干区间并的函数值等于这些区间函数值的并。
（这里有个条件的，就是这些区间相邻的两个 x,y 要有交或者 r_x = l_y-1）

考虑这个有什么用，可以写 ST 表做到 O(n \log n) \sim O(1) 查询一个区间的 f，然后好像不太会了 /ng。

妈的，差一点就想出来了 /fn /fn /fn
应该给自己留更多思考时间的。现在浑身难受。

现在我们抓着 ST 表继续搞。那么我们使用以上结论，设 ST 表划分的区间是 [l,k_1] 和 [k_2,r]，则 f([l,r]) = f([l,k_1]) \bigcup f([k_2,r])。

考虑证明 f^2([l,r]) = f^2([l,k_1]) \bigcup f^2([k_2,r])。

证明：f^2([l,r]) = f(f([l,k_1]) \bigcup f([k_2,r]))，再次使用结论，\text{RHS} = f(f([l,k_1])) \bigcup f(f([k_2,r])) = f^2([l,k_1]) \bigcup f^2([k_2,r])，得证。

Upd：关于这里可以再次使用结论有一个条件就是 f([l,k_1]) \bigcap f([k_2,r]) 不为空，由于是 ST 表所以 l \lt k_2 \le k_1 \lt r，那么这两个区间有交，两个区间的函数值也一定有交（包含相同元素，这些相同元素一定被包括在函数值这个区间里）。

归纳可知 f^k([l,r]) = f^k([l,k_1]) \bigcup f^k([k_2,r])。

那么就可以魔改一下 ST 表了，我们在前面再加一维 k 表示这个 ST 表存的是 f^{2^k}([l,r])，然后每次直接做就行了。时间复杂度 O(n \log^2 n + q \log n)，空间复杂度 O(n \log^2 n)，由于这是 CF，而且给了 1G，所以你就 Happy New Year 了。

启发性大概在于这种不好搞的函数尝试分拆、组合来观察可并性，或者找单调性，然后利用这些性质套上数据结构维护；还有就是做若干次给定变换可以考虑倍增。

Upd：Happy New Year 了。 

#include <bits/stdc++.h>
using namespace std;

#define ri register int
#define ll long long
#define Tp template<class T>
namespace SlowIO{
    const int End=1e6; static char outp[End],buf[End],*p1=buf,*p2=buf; inline char gchar(){ return p1==p2&&(p2=(p1=buf)+fread(buf,1,End,stdin),p1==p2)?EOF:*p1++; }
    Tp inline void rd(T &x,char i=gchar(),bool f=0){ x=0; while(i<48||i>57) f|=i=='-',i=gchar(); while(i>=48&&i<=57) x=(x<<3)+(x<<1)+(i^48),i=gchar(); f&&(x=-x); } Tp inline void op(T x,int out=0){ if(!x){ putchar(48); return; } x<0&&(x=-x,putchar('-')); while(x) outp[++out]=(x%10)^48,x/=10; while(out) putchar(outp[out--]); } Tp inline void writeln(T x){ op(x),putchar('\n'); } Tp inline void writesp(T x){ op(x),putchar(' '); } Tp inline void write(T x,char c=0){ op(x); c&&putchar(c); }
}; using namespace SlowIO;

const int N = 100003;
int n,q,a[N],Log2[N];
struct Data{ int l,r; inline Data operator +(const Data &a){ return {min(l,a.l),max(r,a.r)}; } }st[18][18][N];
auto Chk = [](Data x){ return x.l==1&&x.r==n; };
auto Qry = [](int i,int l,int r){ int k = Log2[r-l+1]; return st[i][k][l]+st[i][k][r-(1<<k)+1]; };

main(){
    rd(n),rd(q); bool f1=0,f2=0;
    for(int i=1;i<=n;++i) rd(a[i]),st[0][0][i]={a[i],a[i]},f1|=a[i]==1,f2|=a[i]==n;
    for(int i=2;i<=n;++i) Log2[i]=Log2[i>>1]+1;
    for(int i=n;i>=1;--i)
        for(int j=1;i+(1<<j)-1<=n;++j)
            st[0][j][i]=st[0][j-1][i]+st[0][j-1][i+(1<<j-1)];
    for(int k=1;k<18;++k)
        for(int i=n;i>=1;--i)
            for(int j=1;i+(1<<j)-1<=n;++j)
                st[k][j][i]=Qry(k-1,st[k-1][j][i].l,st[k-1][j][i].r);
    int l,r; while(q--){
        rd(l),rd(r); int res=0; Data now = {l,r};
        if(Chk(now)){ puts("0"); continue; }
        if(!f1||!f2){ puts("-1"); continue; }
        for(int i=17;i>=0;--i){
            Data t = Qry(i,now.l,now.r); if(!Chk(t)) now=t,res|=1<<i;
        } ++res,now=Qry(0,now.l,now.r),writeln(Chk(now)?res:-1);
    }
}