#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int,int> PII;

const int N = 5e5 + 100;

int n,m,x,d;
int h[N];            // 每个城市的高度
int p[N], s[N];      // 并查集父节点和集合大小
int cnt = 0;         // 当前满足大小≥d的连通块个数
vector<int> adj[N];  // 邻接表
vector<int> H;       // 每天的水位


int find(int x) 
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 合并两个城市所在的集合，并更新cnt
void unite(int a, int b) 
{
    int ra = find(a), rb = find(b);
    if(ra == rb) return;

    //更新cnt：减去原来两个可能有的贡献
    if(s[ra] >= d) cnt--;
    if(s[rb] >= d) cnt--;
    
    // 按大小合并，保证ra是较大的集合
    if(s[ra] < s[rb]) swap(ra, rb);
    p[rb] = ra;
    s[ra] += s[rb];

    // 更新cnt：加上新集合可能的贡献
    if(s[ra] >= d) cnt++;
}

int main() 
{
    scanf("%d %d %d %d", &n, &m, &x, &d);
    for(int i = 1; i <= n; i++) scanf("%d", &h[i]);

    // 建图
    for(int i = 0; i < m; i++) 
    {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }


    for(int i = 0; i < x; i++) 
    {
        int tmp;
        scanf("%d", &tmp);
        H.push_back(tmp);
    }

    // 将城市按高度从大到小排序加
    vector<PII> c;  // (高度, 城市编号)
    for(int i = 1; i <= n; i++) 
        c.push_back(h[i], i);
    sort(c.begin(), c.end(), greater<PII>());  // 降序

    int idx = 0;          // 指向c中下一个待加入的城市
    int a[x + 1];         // 存储每天答案（下标0对应第1天）

    // 倒序遍历每一天
    for(int i = x - 1; i >= 0; i--) 
    {
        int now = H[i];   // 当前天的水位

        // 将所有高度 > now 的城市加入并查集（这些城市在这一天未被淹没）
        while(idx < n && c[idx].first > now) 
        {
            int u = c[idx].second;   // 城市编号
            p[u] = u;                // 初始化并查集
            s[u] = 1;
            if(d <= 1) cnt++;        // 如果d=1，每个单独城市就是一个合法连通块

            // 尝试与已经加入的邻居合并
            for(int v : adj[u]) 
            {
                if(p[v] != 0)        // 邻居v已经被加入
                    unite(u, v);
            }
            idx++;
        }
        a[i] = cnt;   // 这一天的答案
    }

    for(int i = 0; i < x; i++)
        printf("%d\n", a[i]);

    return 0;
}

G.  小L的散步

本题主要内容：小  面前有  个石块，每个石块长度为 ，从位置 0 开始依次排列，相邻石块间有缝隙（最后一个石块的右端点也视为缝隙）。
                         他从位置 0 出发，每一步跨过长度 ，脚掌长度为 ，脚后跟位置即为当前位置。
                         需要判断：在初始位置以及每一步走完后的位置，他的脚掌是否覆盖了任何一个缝隙（脚掌边缘恰好落在缝隙上不算踩中）。

本题大致思路：我么可以发现，对于石块的长度的前缀和，就是每个缝隙所在的位置。因此我们可以先计算的前缀和，

                         然后依次遍历每走一步，计算脚后跟  和脚尖 ,判断是否存在某一缝隙满足： 

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 2e5 + 100;

LL n, m, r;
LL s[N], y[N];             // s[i] 为前 i 个石块的总长度（即第 i 个石块的右端点位置），y[i] 为第 i 步步长

int main() 
{
    scanf("%lld %lld %lld", &n, &m, &r);
    
    // 读入每个石块长度并计算前缀和
    for (int i = 1; i <= n; i++) 
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }
    
    for (int i = 1; i <= m; i++) 
        scanf("%lld", &y[i]);
    
    LL l = 0;          // 当前脚后跟的位置，初始为 0
    LL cnt = 1;        // 指向当前可能踩到的第一个缝隙（即第 cnt 个石块的右端点）
    
    // 检查初始位置是否踩中缝隙
    if (s[cnt] > l && s[cnt] < r)   // 缝隙位于脚掌区间 (l, r) 内
    {
        printf("YES\n");
        return 0;
    }
    
    for (int i = 1; i <= m; i++)
    {
        l += y[i];      // 脚后跟向前移动 y[i]
        r += y[i];      // 脚掌右端点也相应移动（脚长不变，所以 r 是脚后跟 + 脚长）
        
        // 当脚后跟已经超过当前缝隙位置时，说明这个缝隙已经被跨过，需要检查下一个缝隙
        while (cnt <= n && l > s[cnt]) 
            cnt++;
        
        // 如果当前缝隙在脚掌区间内，则踩中
        if (cnt <= n && s[cnt] > l && s[cnt] < r) 
        {
            printf("YES\n");
            return 0;
        }
    }
    
    // 全程没有踩中缝隙
    printf("NO\n");
    
    return 0;
}

#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 3000;

int n;
int a[N], b[N];

int main() 
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) 
        scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) 
        scanf("%d", &b[i]);

    // 使用哈希集合存储当前所有可能的 x 值
    unordered_set<int> s;
    s.insert(0);          // 初始 x = 0

    // 依次进行 n 次操作
    for (int i = 0; i < n; i++) 
    {
        unordered_set<int> tmp;   // 临时集合，存放第 i 步后的所有可能值
        for (auto x : s) 
        {
            // 规则一：减去 a[i] 并保证非负
            tmp.insert(max(0, x - a[i]));
            // 规则二：与 b[i] 按位异或
            tmp.insert(x ^ b[i]);
        }
        // 将当前集合更新为临时集合
        s.swap(tmp);
    }

    // 找出所有可能结果中的最大值
    int res = -1e9;
    for (auto i : s) 
        res = max(res, i);
    
    printf("%d\n", res);
    return 0;
}