题解：P6580 [Ynoi2019] 美好的每一天~ 不连续的存在

· · 题解

模拟赛喜欢卡常，交这里一下就过了。下面交互次数和时间复杂度是一个东西。

首先大概观察一下容易想到回滚莫队和启发式合并两个东西。

使用并查集维护连通块，不难做到加点和撤销的同时维护 S，这里可以使用启发式合并。

回滚莫队，l,r 同块暴力。对于每一块 [L,R] 加入 [R,r=R\sim n]，并在过程中对询问加入 [l,R) 回答再撤销。

此时左侧和暴力的复杂度是不对的。不过我们知道往 [l+1,r] 中启发式加入 l 的代价一定不超过往 [l+1,n] 中启发式加入 l 的代价，而后者的总和是 O(n\log n) 的。

因此可以将后者算出来带权分块，即每当 \sum>B 时截断。那么有 O(\frac{n\log n}{B}) 块，时间复杂度 O(\frac{n^2\log^2n}{B}+qB)。

取 B=O(\sqrt n\log n)，时间复杂度 O((n+q)\sqrt n\log n)。

:::success[点击查看参考代码]

#include<bits/stdc++.h>
#define TIME chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()
#define rep(i,l,r) for(int qwp=(r),i=(l);i<=qwp;i++)
#define per(i,r,l) for(int qwp=(l),i=(r);i>=qwp;i--)
#define pb push_back
#define pob pop_back
#define SZ(x) (int)((x).size())
#define fir first
#define sec second
using namespace std;
typedef vector<int> arr;typedef pair<int,int> pii;typedef vector<pii> prr;
void Answer(int);void push(int,int);void pop(int);
constexpr int N=1e5+5;arr g[N];
namespace BRUTE{
bool vis[N];arr clog;
void dfs(int u,int l,int r,int to){
    if(u<l||r<u||vis[u])return ;push(to,u),clog.pb(to);
    vis[u]=1;for(auto v:g[u])dfs(v,l,r,to);
}
void work(int id,int l,int r){
    rep(i,l,r)if(!vis[i])dfs(i,l,r,i-1);Answer(id);
    rep(i,l,r)vis[i]=0;for(auto u:clog)pop(u);clog={};
}
};
struct DSU{
    struct node{int fa,sz;arr S;}a[N];
    void Init(int n){rep(i,1,n)a[i]={i,1,{i}};}
    int find(int x){return a[x].fa==x?x:find(a[x].fa);}
    stack<pii>stk;int meg(int x,int y){
        if((x=find(x))==(y=find(y)))return 0;if(a[x].sz<a[y].sz)swap(x,y);
        stk.push({x,y});a[y].fa=x,a[x].sz+=a[y].sz;
        for(auto u:a[y].S)a[x].S.pb(u),pop(y-1),push(x-1,u);return a[y].sz;
    }
    void rest(int _){while(_--){
        int x=stk.top().fir,y=stk.top().sec;stk.pop();
        a[y].fa=y,a[x].sz-=a[y].sz;
        for(auto u:a[y].S)a[x].S.pob(),pop(x-1),push(y-1,u);
    }}
}dsu;
int cost[N],lim,blk,bl[N],br[N],col[N];arr qS[N],QS[N];bool vis[N];
int add(int u){int t=0;vis[u]=1,push(u-1,u);for(auto v:g[u])if(vis[v])t++,dsu.meg(u,v);return t;}
void solve(int n,int q,prr es,prr qs){
    rep(i,1,n)g[i]={};for(auto e:es)g[e.fir].pb(e.sec),g[e.sec].pb(e.fir);
    dsu.Init(n);per(i,n,1){
        cost[i]=SZ(g[i]),push(i-1,i);
        for(auto j:g[i])if(j>i)cost[i]+=dsu.meg(i,j);
    }dsu.rest(n-1);rep(i,1,n)pop(i-1);
    lim=sqrt(n)*__lg(n)/2;for(blk=0;br[blk]!=n;){
        blk++,bl[blk]=br[blk-1]+1;int R=bl[blk],s=cost[R];
        while(R<n&&s<=lim)s+=cost[++R];rep(i,bl[blk],br[blk]=R)col[i]=blk;
    }
    rep(i,1,blk)qS[i]={};rep(i,0,q-1)
    if(col[qs[i].fir]<col[qs[i].sec])qS[col[qs[i].fir]].pb(i);
    else BRUTE::work(i,qs[i].fir,qs[i].sec);
    rep(_,1,blk)if(SZ(qS[_])){
        int mx=0,t=br[_],mg=0;vis[t]=1,push(t-1,t);
        for(auto j:qS[_])QS[qs[j].sec].pb(j),mx=max(mx,qs[j].sec);
        rep(i,t+1,mx){
            mg+=add(i);for(auto j:QS[i]){
                int gm=0;per(k,t-1,qs[j].fir)gm+=add(k);
                Answer(j);dsu.rest(gm);per(k,t-1,qs[j].fir)vis[k]=0,pop(k-1);
            }QS[i]={};
        }dsu.rest(mg);rep(i,t,mx)vis[i]=0,pop(i-1);
    }
}
/*
ulimit -s 1048576
g++ -O2 -std=c++17 -static A.cpp grader.cpp -o %;size %;./% < A.in > A.out
*/

:::

尬黑了，模拟赛题解指出可以做到单根号，但是我不会。