题解 | #幼稚园的树#

A. 按照题意模拟即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,aa,b;
int a[3005];
int t;
void solve()
{
    cin>>n;
    for(int i = 1;i<=n;++i)
        cin>>a[i];
    cin>>aa>>k>>b>>m;
    for(int i = 1;i<m;++i)
        for(int j = 1;j<=n;++j)
        {
            a[j]+=aa;
            if(a[j]>k)
                a[j] = b;
        }
    for(int i = 1;i<=n;++i)
        cout<<a[i]<<" ";
    cout<<'\n';
}
signed main()
{
    cin>>t;
    while(t--)
        solve();
    return 0;
}

B. 发现结果不是 $00$ 就是 $11$，将 $00$ 的情况特判，就是 $({\sum }_{i=l}^{r}i)modx==0(\backslash sum\_\{i=l\}^ri)\backslash ;mod\backslash ;x==0$，其余的情况均为 $11$

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int l,r;
    cin>>l>>r;
    int m;
    cin>>m;
    long long now = 1ll*(l+r)*(r-l+1)/2;
    while(m--)
    {
        int x;
        cin>>x;
        if(now%x==0)
            cout<<0<<'\n';
        else
            cout<<1<<'\n';
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

C.做法：质因数分解

对于$a,ba,b$的任何元素$gcdgcd$均为1，即 $aa$ 序列中所有的质因子与 $bb$ 序列中的所有质因子均不相同。将所有元素质因数分解后判断即可

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005];
int b[100005];
int mp[1000005];
int main()
{
    cin>>n;
    for(int i = 1;i<=n;++i)
    {
        cin>>a[i];
        int x = a[i];
        for(int j = 2;j<=sqrt(x);++j)
            while(x%j==0)
            {
                mp[j]++;
                x/=j;
            }
        if(x>1)
            mp[x]++;
    }
    for(int i = 1;i<=n;++i)
    {
        cin>>b[i];
        int x = b[i];
        for(int j = 2;j<=sqrt(x);++j)
            while(x%j==0)
            {
                if(mp[j])
                {
                    cout<<"No\n";
                    return 0;
                }
                x/=j;
            }
        if(x>1)
        {
            if(mp[x])
            {
                    cout<<"No\n";
                    return 0;
            }    
        }
    }
    cout<<"Yes\n";
    return 0;
}

D.

容易发现，$xx$ 的所有子树，子树的所有子树，子树的所有子树的所有子树，均是一段连续的区间。

也就是当前处理到树的左端点为$ll$，右端点为 $rr$,那么这堆子树的所有子树的左端点则为 $l\ast k+1l*k+1$，右端点为 $r\ast k+kr*k+k$。

那么对于$11$叉树和 $00$ 叉树特判之后，每棵树最多有 $loglog$ 层。使用一个队列维护当前区间信息，暴力处理即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,m;
void solve()
{
    cin>>n>>k>>m;
    while(m--)
    {
        int x;
        cin>>x;
        if(k==0)
        {
            cout<<1<<'\n';
            continue;
        }
        if(k==1)
        {
            cout<<(n-x)<<'\n';
            continue;
        }
        int ans = 0;
        queue<pair<int,int>> q;
        q.push({x,x});
        while(!q.empty())
        {
            auto now = q.front();
            q.pop();
            ans+=now.second-now.first+1;
            int l = now.first*k+1;
            if(l>=n)
                continue;
            int r = min(n-1,now.second*k+k);
            q.push({l,r});
        }
        cout<<ans<<'\n';
    }
}
int t;
signed main()
{
    cin>>t;
    while(t--)
        solve();
    return 0;
}

E.

做法：树上差分

由于是个完全二叉树，最多有$loglog$层。对于操作 $11$，直接对 $xx$ 的子树增加1，对于操作 $22$,等价于对于整棵树增加 $11$，$xx$ 的子树减少 $11$。对于操作 $33$ 直接暴力往上跳直接对其权值增加 $11$，对于操作 $44$，暴力往上跳直接对其权值减少 $11$。然后对于整棵树增加 $11$。

操作 $1\mathrm{，}21，2$ 均通过树上差分实现即可。

#include<bits/stdc++.h>
using namespace std;
int cf[20000005];
int tag[20000005];
int ans[500005];
int n,m,op,x;
void dfs(int now,int f)
{
    if(now>n)
        return;
    int qz = 0;
    qz+=tag[now];
    qz+=cf[now];
    ans[qz]++;
    cf[2*now]+=cf[now];
    cf[2*now+1]+=cf[now];
    dfs(2*now,now);
    dfs(2*now+1,now);
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i<=m;++i) 
    {
        cin>>op>>x;
        if(op==1)
            cf[x]++;
        else if(op==2)
        {
            cf[1]++;
            cf[x]--;
        }
        else if(op==3)
        {
            while(x)
            {
                tag[x]++;
                x/=2;
            }
        }
        else if(op==4)
        {
            while(x)
            {
                tag[x]--;
                x/=2;
            }
            cf[1]++;
        }
    }
    dfs(1,0);
    for(int i = 0;i<=m;++i)
        cout<<ans[i]<<' ';
    return 0;
}

F.

预处理，前缀和。

预处理出所有前缀中字母 $aa$ 的奇偶性，字母 $cc$ 的奇偶性，以及子序列 $acac$ 的奇偶性。 子序列 $acac$ 的奇偶性可以通过字母 $cc$ 出现的时候，前缀中字母 $aa$ 出现的数量来修改，每当一个 $cc$ 出现的时候子序列 $acac$ 的数量就会增加前缀 $aa$ 的数量。

预处理之后枚举左端点，先找到右边第一次出现子序列 $acac$ 的位置 $xx$，右端点就一定都在 $[x,n][x,n]$ 之间，用map存[x,n]中所有二元对{$precprec$,$preacpreac$}的奇偶性($precprec$代表前缀中$cc$出现的数量，$preacpreac$代表前缀中子序列 $acac$ 出现的数量)

设 $ll$ 为左端点 $rr$ 为右端点。子区间 $[l,r][l,r]$ 中子序列 $acac$ 的数量即为 $prea{c}_r-prea{c}_{l-1}-pre{a}_{l-1}\times (pre{c}_r-pre{c}_{l-1})preac\_r-preac\_\{l-1\}-prea\_\{l-1\}\backslash times(prec\_r-prec\_\{l-1\})$。这个操作在 $mod2mod\backslash ;2$ 运算下同样成立。 所以直接$2\times 22\; \backslash times\; 2$ 枚举$0\mathrm{/}10/1$二元对。看后面有没有满足的奇偶性。

我说的可能不太清楚，具体的可以结合代码理解下qaq

#include<bits/stdc++.h>
using namespace std;
int prea[500005];
int prec[500005];
int preac[500005];
const int mod = 2;
string s;
map<pair<int,int>,int> mp;
int nxta[500005];
int nxtc[500005];
int nxtac[500005];

int main()
{
    cin>>s;
    int n = s.size();
    s = " "+s;
    for(int i = 1;i<=n;++i)
    {
        prea[i] = prea[i-1];
        prec[i] = prec[i-1];
        preac[i] = preac[i-1];
        if(s[i]=='a')
            prea[i]^=1;
        if(s[i]=='c')
        {
            prec[i]^=1;
            preac[i]^=prea[i-1];
        }
        mp[{prec[i],preac[i]}]++;
    }
    int na = n+1;
    int nc = n+1;
    nxtc[n+1] = n+1;
    nxta[n+1] = n+1;
    nxtac[n+1] = n+1;
    for(int i = n;i>=1;--i)
    {
    	if(s[i]=='a')
    		na = i;
    	if(s[i]=='c')
    		nc = i;
    	nxta[i] = na;
    	nxtc[i] = nc;
    	nxtac[i] = nxtc[na];
	}
    long long ans = 0;
    int z = 1;
    for(int i = 0;i<n;++i)
    {
    	while(z<nxtac[i+1])
    	{
    		mp[{prec[z],preac[z]}]--;
    		z++;
    	}
        int now = preac[i];
        int x = prea[i];
        for(int j = 0;j<=1;++j)
            for(int k = 0;k<=1;++k)
                if((((k-(j-prec[i])*x-now)%mod+mod)%mod)==0)
                    ans+=mp[{j,k}];
    }
    cout<<ans<<'\n';
    return 0;
}