CF2030F 解题报告

· · 题解

前言

离结束 50 min 时想到的正解，但是给毙了，最后 20 min 拉出来写没写完遗憾离场。

思路分析

主要讲讲这种题在场上怎么样才能想到，想出来。

首先看到这玩意是定义了一种区间，并且多次询问给定区间。

这个感觉上就非常 DS，思考的时候尝试往 DS 靠。

这个时候就可以分出来很多种大致的走向了。

  1. 区间询问，考虑使用线段树合并区间。

    这时我们需要考虑的就是区间两两之间能否快速合并，在这题看来是不太行的，直接毙了。

  2. 大力莫队，结合 3 秒实现大力做。

    注意到如果我们删掉了一个区间的一个数，要对后面的所有值相同的数都进行判定，显然爆了。

  3. 找性质。

那这题也没什么办法了只能找性质了。

其实我们可以发现一个显而易见的单调性。

就是对于区间 [l,r] 如果合法那么他的子区间 [l',r'] 肯定也是合法的。

为了证明这个东西，我们考虑怎么样的区间才是合法的。

其实也就是，对于每一种值 i 处理出他的第一次出现位置为 l_i，最后一次出现位置为 r_i，那么就会形成一个区间 [l_i,r_i]，只要满足这些区间都不交就行了。

证明很 ez，如果区间是包含那就可以把里面的区间删了让外面的并起来。

如果区间是相交的话那么不管删哪边都还会剩下一半，所以显然不行。

那如果我们把这些区间之间，看做是成对的带颜色的固定匹配的括号，那我从合法的括号序列中截取一段，显然也是合法的。

所以我们有了一个单调性，合法区间的子区间是合法区间。

这就启发我们去找到所有的极大合法子区间。

其中极大即为不可再扩展。

根据刚刚那个单调性，我们考虑一个双指针的扩展过程。

钦定右端点 r，我们考虑计算左端点的最左位置。

首先考虑从原本的答案直接拿过来是否可行，若不行那便暴力加一。

其实就是原本答案 [l,r-1] 合法的，r 的添加导致把一些原本的括号对嵌套起来相交了。

那么我们直接计算出 [l,lst_r] 这里区间最右右端点位置即可，如果越过了 lst_r 就是相交了暴力移动 l\leftarrow l+1。

这个过程直接用线段树实现即可。

其实如果场上想清楚一点 20 min 完全够写了。

代码

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (ls|1)
#define mid ((l+r)>>1)
#define int long long
using namespace std;
const int N=2e5+10,M=21,V=2e5,INF=1e18,mod=998244353;
int n,m,tot,a[N],L[N],lst[N],t[N<<2];
namespace Fast_IO
{
    static char buf[1000000],*paa=buf,*pd=buf,out[10000000];int length=0;
    #define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
    inline int read()
    {
        int x(0),t(1);char fc(getchar());
        while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
        while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
        return x*t;
    }
    inline void flush(){fwrite(out,1,length,stdout);length=0;}
    inline void put(char c){if(length==9999999) flush();out[length++]=c;}
    inline void put(string s){for(char c:s) put(c);}
    inline void print(int x)
    {
        if(x<0) put('-'),x=-x;
        if(x>9) print(x/10);
        put(x%10+'0');
    }
    inline bool chk(char c) { return !(c>='a'&&c<='z'||c>='A'&&c<='Z'||c>='0'&&c<='9'); }
    inline bool ck(char c) { return c!='\n'&&c!='\r'&&c!=-1&&c!=' '; }
    inline void rd(char s[],int&n)
    {
        s[++n]=getchar();
        while(chk(s[n])) s[n]=getchar();
        while(ck(s[n])) s[++n]=getchar();
        n--;
    }
}
using namespace Fast_IO;
inline void modify(int p,int l,int r,int x,int w)
{
    if(l==r) return t[p]=w,void();
    (mid>=x)?(modify(ls,l,mid,x,w)):(modify(rs,mid+1,r,x,w));
    t[p]=max(t[ls],t[rs]);
}
inline void clear(int p,int l,int r){t[p]=0;if(l==r) return;clear(ls,l,mid);clear(rs,mid+1,r);}
inline int query(int p,int l,int r,int s,int e)
{
    if(e<s) return 0;if(l>=s&&r<=e) return t[p];int res=0;
    if(mid>=s) res=query(ls,l,mid,s,e);
    if(mid<e) res=max(res,query(rs,mid+1,r,s,e));
    return res;
}
inline void solve()
{
    n=read();m=read();for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1,l=1;i<=n;i++)
    {
        int r=lst[a[i]];while(query(1,1,n,l,r)>r) l++;
        if(r) modify(1,1,n,r,i);L[i]=l;lst[a[i]]=i;
    }
    for(int i=1,l,r;i<=m;i++) l=read(),r=read(),put(L[r]<=l?"Yes\n":"No\n");
    for(int i=1;i<=n;i++) lst[a[i]]=0;clear(1,1,n);
}
signed main()
{
    int T=1;
    T=read();
    while(T--) solve();
    genshin:;flush();return 0;
}