D

思维

可以把长度a的连续1变成0，可以把长度a+1的连续0变成1，问最多能得到多少1？

只要有一段长度a的1，我们把他们变成0，然后和两侧的0，肯定可以构成一个长度至少a+1的连续0，然后我们可以把他们再变成1，重复这个操作可以把所有0都变成1

如果开始没有长度a的1，但是有长度a+1的0，可以类似的操作，还是能全变成1.

所以只要存在长度不小于a的连续1，或者长度不小于a+1的连续0，就可以全变成1。找最长连续1/0长度这是典，不谈

#include <bits/stdc++.h>
#define int long long


using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;


void solve() {
    int n,a;
    cin>>n>>a;

    string s;
    cin>>s;

    int len=0;
    bool f=0;
    int cnt=0;
    for(char c:s){
        if(c=='1'){
            len++;
            cnt++;
        }
        else{
            if(len>=a){
                f=1;
            }
            len=0;
        }
    }    
    if(len>=a){
        f=1;
    }
    len=0;

    for(char c:s){
        if(c=='0'){
            len++;
        }
        else{
            if(len>=a+1){
                f=1;
            }
            len=0;
        }
    }
    if(len>=a+1){
        f=1;
    }

    if(f){
        cout<<n<<'\n';
    }
    else{
        cout<<cnt<<'\n';
    }
}


signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T; cin >> T;
    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}

E

每次可以选两个数同时除公因子，或者同时乘上任意数字。

问能否变成全部相同？

从质因子的角度考虑，可以看成这个质因子的指数序列，我们每次操作等价于选两个指数同时加减，问能否把指数序列变成全相同。注意到不同质因子互不干扰，我们可以分开考虑。

又注意到只要数组长度不小于3，我们每次加减两个位置的话，实际上是可以把每个位置上的数移动到任意位置，，比如可以

[3,0,1]
[3,1,2]
[2,1,1]

这就相当于利用第三个1这个陪跑的，把第一个位置的1转移到第二个位置了

可以随意转移，那么我们就只用关注元素和了，而不用关心值的分布。注意到我们每次操作对元素和的影响都是加减一个偶数，所以最后想要变成全都一样，不妨设变成k，需要的变化量必须也是偶数，为元素和,是任意整数。

那么如果n为奇数，可以是奇数也可以是偶数，所以不管是奇数还是偶数，都可以是偶数，也就是必有解。

如果为偶数，只能是偶数，那还想要是偶数，必须也是偶数。

长度小于3直接特判即可。

实现时对于每种质因子，记录指数和的奇偶性即可

最后注意，分解质因子不能，必须线性筛预处理，然后分解。

#include <bits/stdc++.h>
#define int long long


using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 2E5 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;

vector<int> minp, primes;
void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    for (int i = 2; i <= n; i++) {
        if (!minp[i]) primes.emplace_back(minp[i] = i);
        for (auto p : primes) {
            if (i * p > n or p > minp[i]) break;
            minp[i * p] = p;
        }
    }
}

void solve() {
    int n;
    cin>>n;
    vector<int>a(n+1);

    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    if(n==1){
        cout<<"YES\n";
    }
    else if(n==2){
        if(a[1]==a[2]){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }
    else if(n%2){
        cout<<"YES\n";
    }
    else{
        unordered_map<int,int>p;
        for(int i=1;i<=n;i++){
            int x=a[i];
            unordered_map<int,int>mp;
            while(x!=1){
                mp[minp[x]]++;
                x/=minp[x];
            }
            for(auto &[k,v]:mp){
                p[k]+=v;
            }
        }
        bool f=1;
        for(auto &[k,v]:p){
            if(v%2){
                f=0;
                break;
            }
        }
        if(f)cout<<"YES\n";
        else cout<<"NO\n";
    }
}


signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T; cin >> T;
    sieve(6e6);
    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}

H

树剖+倍增/暴力+倍增

树剖+倍增

每个时间区间有一个目标，从1出发，如果当前和目标在一个连通块，就往目标移动一步。可以永久断开一些边。问最早能到达一个目标的时间点？

能断边，那么实际上我们就可以控制每个目标出现时，是否往这个目标方向走，所以可以标记上所有可能到达的点，如果哪一个目标点是可能到达的点，就是直接得到答案。

那么对于一个时间段和目标，我们要检查上方距离最近的被标记的祖先，然后从这个祖先往走步，走过的点都标记上可能到达。如果走这么多步已经到了，就可以到达这个了。否则看下一个

这里标记一条链，开始没多想，直接上树剖了。然后确定最近的被标记的祖先，顺势用了树剖，查一下路径的和，就能知道被最近的标记祖先的深度，就能知道这个祖先是的第几级祖先，然后倍增查祖先即可。

式子搞得很麻烦，树剖开始还写错了

#include <bits/stdc++.h>
#define int long long

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 1E6 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;

struct tree {
#define ls u << 1
#define rs u << 1 | 1

    struct node {
        int l, r;
        int sum, add;
    } t[N << 2];

    void pushup(int u) { t[u].sum = t[ls].sum + t[rs].sum; }

    void pushdown(int u) {
        if (t[u].add) {
            t[ls].sum = t[u].add * (t[ls].r - t[ls].l + 1);
            t[rs].sum = t[u].add * (t[rs].r - t[rs].l + 1);
            t[ls].add = t[u].add;
            t[rs].add = t[u].add;
            t[u].add = 0;
        }
    }

    void build(int u, int l, int r) {
        t[u] = {l, r, 0, 0};
        if (l == r) {
            return;
        }
        int m = (l + r) >> 1;
        build(ls, l, m);
        build(rs, m + 1, r);
        pushup(u);
    }

    void modify(int u, int l, int r, int v) {
        if (t[u].l >= l && t[u].r <= r) {
            t[u].sum = v * (t[u].r - t[u].l + 1);
            t[u].add = v;
            return;
        }

        else {
            int mid = (t[u].l + t[u].r) >> 1;
            pushdown(u);
            if (mid >= l) {
                modify(ls, l, r, v);
            } 
            if (r>mid){
                modify(rs, l, r, v);
            }
            pushup(u);
        }
    }

    int query(int u, int l, int r) {
        if (l <= t[u].l && t[u].r <= r) {
            return t[u].sum;
        }
        pushdown(u);
        int mid = (t[u].l + t[u].r) >> 1;
        if (r <= mid) {
            return query(ls, l, r);
        }
        if (l > mid) {
            return query(rs, l, r);
        }
        return query(ls, l, r) + query(rs, l, r);
    }
} t;
void solve() {
    int n, k;
    cin >> n >> k;
    t.build(1, 1, n);
    ugraph g(n + 1);
    for (int i = 2; i <= n; i++) {
        int f;
        cin >> f;
        g[f].push_back(i);
    }

    vector<int> dep(n + 1), sz(n + 1, 1), son(n + 1), fa(n + 1);
    auto dfs1 = [&](auto &&dfs1, int u, int f) -> void {
        int mx = 0, mxson = 0;
        for (int v : g[u]) {
            if (v == f) continue;
            dep[v] = dep[u] + 1;
            fa[v] = u;
            dfs1(dfs1, v, u);
            sz[u] += sz[v];
            if (sz[v] > mx) {
                mx = sz[v];
                mxson = v;
            }
        }
        son[u] = mxson;
    };
    dfs1(dfs1, 1, 0);
    int cnt = 0;
    vector<int> top(n + 1), dfn(n + 1);
    auto &&dfs2 = [&](auto &&dfs2, int u, int topf) -> void {
        dfn[u] = ++cnt;
        top[u] = topf;
        if (!son[u]) {
            return;
        }
        dfs2(dfs2, son[u], topf);
        for (int v : g[u]) {
            if (v == fa[u] || v == son[u]) {
                continue;
            }
            dfs2(dfs2, v, v);
        }
    };
    dfs2(dfs2, 1, 1);
    auto update_chain = [&](int x, int y, int v) -> void {
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) {
                swap(x, y);
            }
            t.modify(1, dfn[top[x]], dfn[x], v);
            x = fa[top[x]];
        }
        if (dep[x] > dep[y]) {
            swap(x, y);
        }
        t.modify(1, dfn[x], dfn[y], v);
    };
    auto ask_chain = [&](int x, int y) -> int {
        int res = 0;
        while (top[x] != top[y]) {
            if (dep[top[x]] < dep[top[y]]) {
                swap(x, y);
            }
            res += t.query(1, dfn[top[x]], dfn[x]);
            x = fa[top[x]];
        }
        if (dep[x] > dep[y]) {
            swap(x, y);
        }
        res += t.query(1, dfn[x], dfn[y]);
        return res;
    };

    vector<int> lg(n + 1);
    for (int i = 2; i <= n; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    vector<vector<int>> f(n + 1, vector<int>(30));
    vector<int> d(n + 1);

    auto &&dfs = [&](auto &&dfs, int u, int fa) -> void {
        f[u][0] = fa;
        for (int i = 1; i <= lg[d[u]]; i++) {
            f[u][i] = f[f[u][i - 1]][i - 1];
        }
        for (int v : g[u]) {
            if (v == fa) continue;
            d[v] = d[u] + 1;
            dfs(dfs, v, u);
        }
    };
    dfs(dfs, 1, 0);

    auto get_fa = [&](int u, int k) -> int {
        while (k) {
            int low = k & -k;
            u = f[u][__lg(low)];
            k -= low;
        }
        return u;
    };



    t.modify(1,dfn[1],dfn[1],1);
    for(int i=1;i<=k;i++){
        int u,l,r;
        cin>>u>>l>>r;
        int sum=ask_chain(1,u)-1;
        int len=r-l+1;

        // cerr<<d[u]<<' '<<sum<<' '<<len<<' '<<'\n';
        if(d[u]-sum==0){
            cout<<l<<'\n';
            return;
        }
        if(d[u]-sum<=len){
            cout<<l-1+(d[u]-sum)<<'\n';
            return;
        }
        int fa=get_fa(u,d[u]-(sum+len));
        update_chain(1,fa,1);
    }
    cout<<-1<<'\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1;
    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}

暴力+倍增

但其实根本不用树剖，注意到一个点根本不可能被标记两次，所以我们暴力标记即可。

每个，不断找上方最近的被标记的祖先，然后把他的儿子标记上，重复次，直到某次标记后也被标记上了，就得到答案。

虽然很大，但是每个点只会被标记一次，如果很大，很快所有点就都会被标记了，然后就得到答案，结束了。

当然这里找上方最近的被标记的祖先还是要倍增，从大到小枚举倍增跳数，如果未被标记就往上跳，如果已被标记就不跳，看更小跳数。这样枚举完所有跳数，一定是停在最近的被标记的祖先的儿子上，把这个点标记即可

需要注意的是可能会访问到0，因为没用上的倍增数组都是初始化成0，但是0是不能跳过去的，为了防止跳到0，初始把0也标记上，可以视为是1上方的所有点都是已标记

每一步跳完都要先检查是否标记上u了，开始跳之前也要检查u是否被标记

#include <bits/stdc++.h>
#define int long long

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using graph = vector<vector<pii>>;
using ugraph = vector<vector<int>>;
constexpr int N = 1E6 + 5;
constexpr double eps = 1E-8;
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 1E18;

void solve() {
    int n, k;
    cin >> n >> k;
    ugraph g(n + 1);
    for (int i = 2; i <= n; i++) {
        int f;
        cin >> f;
        g[f].push_back(i);
    }


    vector<int> lg(n + 1);
    for (int i = 2; i <= n; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    vector<vector<int>> f(n + 1, vector<int>(30));
    vector<int> d(n + 1);

    auto &&dfs = [&](auto &&dfs, int u, int fa) -> void {
        f[u][0] = fa;
        for (int i = 1; i <= lg[d[u]]; i++) {
            f[u][i] = f[f[u][i - 1]][i - 1];
        }
        for (int v : g[u]) {
            if (v == fa) continue;
            d[v] = d[u] + 1;
            dfs(dfs, v, u);
        }
    };
    dfs(dfs, 1, 0);

    vector<int>vis(n+1);
    vis[1]=1;
    vis[0]=1;
    for(int i=1;i<=k;i++){
        int u,l,r;
        cin>>u>>l>>r;
        if(vis[u]){
            cout<<l<<'\n';
            return;
        }
        for(int j=l;j<=r;j++){
            int t=u;
            for(int k=29;k>=0;k--){
                if(!vis[f[t][k]]){
                    t=f[t][k];
                }
            }
//             cout<<t<<'\n';
            vis[t]=1;
            if(vis[u]){
                cout<<j<<'\n';
                return;
            }
        }
    }
    cout<<-1<<'\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1;
    for (int ttt = 1; ttt <= T; ++ttt) {
        solve();
    }
    return 0;
}