题目链接：CF 或者 洛谷
简单来说就是求 \([l,r]\) 这些点都存在的情况下，连通块的数量，看到七秒时限，而且每个点相连的边数很少，可以想到离线下来使用莫队类的算法解决
连通块问题，一般可以考虑使用并查集解决。对于并查集来说，它的增加是非常简单的，但删除是困难的，可持久化并查集时空常数都较大，我们可以考虑一类比较轻松的并查集就是：可撤销并查集。这里可以参考我的这篇 题解 的回滚思想，就知道为啥用可撤销并查集了。所以自然而然地想到了回滚莫队，那么难度就在代码上了。
1.对于常规的回滚莫队而言，有 \(l\) 与 \(r\) 同块内暴力，不同块采用回滚策略。所以我们需要准备两份并查集，分别维护暴力版本和回滚版本。我们可以考虑把两个并查集的函数合在一起写的，传个参数即可
参考这种并查集我的写法
constexpr int N = 1e5 + 10;
int fa[N], siz[N];
//x,y,fa[x],siz[y]
stack<tuple<int, int, int, int>> st;
int tmpFa[N]; //暴力用的并查集
inline int find(const int x, int* f, const bool isT = false) //是否是暴力版本并查集
{
if (isT)return f[x] == x ? x : f[x] = find(f[x], f, true);
return f[x] == x ? x : find(f[x], f);
}
inline bool merge(int x, int y, int* f, const bool isT = false, const bool isNeed = false) //是否需要回顾记录,是否是暴力版本并查集
{
x = find(x, f, isT), y = find(y, f, isT);
if (x == y)return false;
if (isT)
{
f[x] = y;
return true;
}
if (siz[x] > siz[y])swap(x, y);
if (isNeed)st.emplace(x, y, f[x], siz[y]);
f[x] = y, siz[y] += siz[x];
return true;
}
剩下的就简单了，我们维护只加不减并查集，对于 \(r\) 来说放在当前查询块的最右边的前一位代表没有任何后面的点，对于 \(l\) 来说，放在右侧，用于增加块内的点，然后增加以后利用可撤销并查集撤销回去就行。这个过程和 \(l\) 自己的临时加边是互逆的。初识的，我们将每个点当做一个连通块，每 merge 成功一次，我们 \(-1\)。
细节
对于增加的过程在原有的需要判断当前点的邻边点 \(v_curr\) 是否有 $ L \le v_{curr} \le R$ 前提下，还得注意一个易错点。如果当前的 \(v_{curr} \le R_{查询块}\)，即所连的点在 \(l\) 需要回滚的块中，这时候 \(r\) 并不能和它 merge，否则在 \(l\) 增加到了这个点时，由于已经 merge 过了，并不会在栈中存储回滚信息，导致无法回滚回到 \([R_{查询块},r]\) 这个初始回滚状态，在后续这个不存在的 \(v_{curr}\) 会继续造成贡献。所以在 \(r\) 的 add 过程中，这类点需要先跳过，在 \(l\) 增加时会自然加上再自然地回滚。
最终复杂度显然为：
\[ O(k \times n\sqrt{n}\log{n})
\]
参考代码
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops")
// #define isPbdsFile
#ifdef isPbdsFile
#include <bits/extc++.h>
#else
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/rope>
#endif
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;
typedef tuple<ll, ll, ll> tll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef __int128 i128;
#define hash1 unordered_map
#define hash2 gp_hash_table
#define hash3 cc_hash_table
#define stdHeap std::priority_queue
#define pbdsHeap __gnu_pbds::priority_queue
#define sortArr(a, n) sort(a+1,a+n+1)
#define all(v) v.begin(),v.end()
#define yes cout<<"YES"
#define no cout<<"NO"
#define Spider ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define MyFile freopen("..\\input.txt", "r", stdin),freopen("..\\output.txt", "w", stdout);
#define forn(i, a, b) for(int i = a; i <= b; i++)
#define forv(i, a, b) for(int i=a;i>=b;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define endl '\n'
//用于Miller-Rabin
[[maybe_unused]] static int Prime_Number[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
template <typename T>
int disc(T* a, int n)
{
return unique(a + 1, a + n + 1) - (a + 1);
}
template <typename T>
T lowBit(T x)
{
return x & -x;
}
template <typename T>
T Rand(T l, T r)
{
static mt19937 Rand(time(nullptr));
uniform_int_distribution<T> dis(l, r);
return dis(Rand);
}
template <typename T1, typename T2>
T1 modt(T1 a, T2 b)
{
return (a % b + b) % b;
}
template <typename T1, typename T2, typename T3>
T1 qPow(T1 a, T2 b, T3 c)
{
a %= c;
T1 ans = 1;
for (; b; b >>= 1, (a *= a) %= c)if (b & 1)(ans *= a) %= c;
return modt(ans, c);
}
char ch;
template <typename T>
void read(T& x)
{
x = 0;
T sign = 1;
ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')sign = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
x *= sign;
}
template <typename T>
void write(T x)
{
if (x < 0)x = -x, putchar('-');
if (x > 9)write(x / 10);
putchar(x % 10 ^ 48);
}
template <typename T11, typename T22, typename T33>
struct T3
{
T11 one;
T22 tow;
T33 three;
bool operator<(const T3 other) const
{
if (one == other.one)
{
if (tow == other.tow)return three < other.three;
return tow < other.tow;
}
return one < other.one;
}
T3() { one = tow = three = 0; }
T3(T11 one, T22 tow, T33 three) : one(one), tow(tow), three(three)
{
}
};
template <typename T1, typename T2>
void uMax(T1& x, T2 y)
{
if (x < y)x = y;
}
template <typename T1, typename T2>
void uMin(T1& x, T2 y)
{
if (x > y)x = y;
}
constexpr int N = 1e5 + 10;
int fa[N], siz[N];
//x,y,fa[x],siz[y]
stack<tuple<int, int, int, int>> st;
int tmpFa[N]; //暴力用的并查集
inline int find(const int x, int* f, const bool isT = false) //是否是暴力版本并查集
{
if (isT)return f[x] == x ? x : f[x] = find(f[x], f, true);
return f[x] == x ? x : find(f[x], f);
}
inline bool merge(int x, int y, int* f, const bool isT = false, const bool isNeed = false) //是否需要回顾记录,是否是暴力版本并查集
{
x = find(x, f, isT), y = find(y, f, isT);
if (x == y)return false;
if (isT)
{
f[x] = y;
return true;
}
if (siz[x] > siz[y])swap(x, y);
if (isNeed)st.emplace(x, y, f[x], siz[y]);
f[x] = y, siz[y] += siz[x];
return true;
}
int pos[N];
struct Mo
{
int l, r, id;
//只加不减回滚莫队
bool operator<(const Mo& other) const
{
return pos[l] != pos[other.l] ? pos[l] < pos[other.l] : r < other.r;
}
} node[N];
inline void del()
{
while (!st.empty())
{
auto [x,y,faX,sizY] = st.top();
st.pop();
fa[x] = faX, siz[y] = sizY;
}
}
int ans[N];
int n, m, q;
int curr, last;
int e[N];
vector<int> child[N];
inline void solve()
{
cin >> n >> m >> m;
forn(i, 1, n)fa[i] = tmpFa[i] = i, siz[i] = 1;
forn(i, 1, m)
{
int u, v;
cin >> u >> v;
if (u > v)swap(u, v);
child[u].push_back(v);
child[v].push_back(u);
}
cin >> q;
forn(i, 1, q)cin >> node[i].l >> node[i].r, node[i].id = i;
const int blockSize = ceil(sqrt(n));
const int cnt = (n + blockSize - 1) / blockSize;
forn(i, 1, n)pos[i] = (i - 1) / blockSize + 1;
forn(i, 1, cnt)e[i] = i * blockSize;
e[cnt] = n;
sortArr(node, q);
int l = 1, r = 0;
forn(i, 1, q)
{
const auto [L,R,id] = node[i];
if (pos[L] == pos[R])
{
int tmp = R - L + 1;
forn(i, L, R)
{
for (const auto j : child[i])
{
if (j < L or R < j)continue;;
tmp -= merge(i, j, tmpFa, true);
}
}
ans[id] = tmp;
forn(i, L, R)tmpFa[i] = i;
continue;
}
if (pos[L] != last)
{
forn(i, 1, n)fa[i] = i, siz[i] = 1;
l = e[pos[L]] + 1, r = l - 1;
curr = 0;
last = pos[L];
}
while (r < R)
{
++r, ++curr;
for (const int pr : child[r])
{
if (pr < L or R < pr or pr < l)continue;;
curr -= merge(r, pr, fa);
}
}
int tmp = curr;
int tmpL = l;
while (tmpL > L)
{
tmpL--, tmp++;
for (const auto pl : child[tmpL])
{
if (pl < L or R < pl)continue;
tmp -= merge(tmpL, pl, fa, false, true);
}
}
ans[id] = tmp;
del();
}
forn(i, 1, q)cout << ans[i] << endl;
}
signed int main()
{
// MyFile
Spider
//------------------------------------------------------
int test = 1;
// read(test);
// cin >> test;
forn(i, 1, test)solve();
// while (cin >> n, n)solve();
// while (cin >> test)solve();
}