CF 920F（2000分）

给一个长度为$3·10^5$的数组$(a_i\le 10^6)$，有$3·10^5$次查询，每次查询给出一个区间$[l,r]$，有以下两种操作：

• 1 l r：将$[l,r]$区间内的所有数换成它的约数个数
• 2 l r：求$[l,r]$区间和

分析：

势能线段树，一个数能够用很少的次数将其变为2，那么只需要在线段树的每个区间，标记一下是否全为2或1，如果是就直接跳过

注意特判1的情况

CF 1296E2（2000分）

给一个字符串（长度$\le 3·10^5$），现在对每个字符进行染色，现在要求只有不同颜色的字符可以交换位置，求一种染色方案，使得原串可以通过字符间交换，最终字典序升序

分析：

从前往后来考虑，一个字符只有要跟另一个字符交换，才要不同的颜色

这样只用考虑每个字符和它之前的字符交换就可以了。枚举，找到前面比自己大的字符的颜色最大值，然后加一就是当前这个字符的颜色

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200005;

int n;
int f[N], maxn[26];
char s[N];

int main()
{
    scanf("%d", &n);
    cin >> s + 1;
    int cnt = 0;
    for(int i = 1; i <= n; i ++ )
    {
        int maxco = 0;
        for(int j = s[i] - 'a' + 1; j < 26; j ++ )
        {
            maxco = max(maxco, maxn[j]);
        }
        f[i] = maxco + 1;
        maxn[s[i] - 'a'] = maxco + 1;
        cnt = max(cnt, f[i]);
    }
    cout << cnt << endl;
    for(int i = 1; i <= n; i ++ ) cout << f[i] << " ";
    return 0;
}

牛客练习赛90-D

开始有 $n$ 个可重集合，开始时每一个集合中都有一个数，有 $m$ 个操作。

• ​ $\text{Quant l r x}$：往编号在 $l\sim r$ 的每个集合中加入一个数 $x$。
• ​ $\text{Ask l r}$：询问能否从 $l\sim r$ 的集合中取出三个数使得他们能作为边长组成一个三角形（即最小两个和要大于最大的）。

输入描述:

第一行两个整数 $n,m$$(1\leq n,m\leq 10^5)$。
接下来一行 $n$ 个数表示每个集合中初始的一个数 $a_i$ 。
接下来 $m$ 行每行表示一个操作。
保证操作加入的数字和最开始的数字均为正整数且不超过 $10^9$ 且询问区间合法 $(1\leq l\leq r\leq n)$ 。

输出描述:

对于每个 Ask 操作，输出一行表示答案，能则输出 YES ，否则输出 NO。

分析：

结论：当数列中所有数都是斐波那契数的时候，任意三个数不能组成三角形

打表可知，$10^9$之内的斐波那契数不超过$45$

线段树维护区间每个位置有多少个数，开$n$个vector记录每个位置的所有数。区间查询的时候先在线段树查$[l,r]$有多少个数，如果超过45个直接返回yes，如果少于3个返回No，否则就暴力地在l,r的vector中枚举查找

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

using namespace std;

const int N = 100005;

struct Node
{
    int l, r;
    int sum, add;
}tr[N * 4];

int n, m, a[N];
vector<int> v[N];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u)
{
    auto& root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if(root.add)
    {
        left.add += root.add, right.add += root.add;
        left.sum += (left.r - left.l + 1) * root.add;
        right.sum += (right.r - right.l + 1) * root.add;
        root.add = 0;
    }
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if(l == r)
    {
        tr[u].sum = 1;
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int x)
{
    if(tr[u].sum/(tr[u].r-tr[u].l+1)>=46) return;
    if(tr[u].l==tr[u].r) {
        v[r].push_back(x);
        tr[u].sum++;
        return ;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(r<=mid) modify(2*u,l,r,x);
    else if(l>mid) modify(2*u+1,l,r,x);
    else {
        modify(2*u,l,mid,x);
        modify(2*u+1,mid+1,r,x);
    }
    pushup(u);
}

int query(int u, int l, int r)
{
    if(l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int res = 0;
    if(l <= mid) res += query(u << 1, l, r);
    if(r > mid) res += query(u << 1 | 1, l, r);
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) 
    {
        scanf("%d", &a[i]);
        v[i].push_back(a[i]);
    }
    build(1, 1, n);
    char op[10];
    while (m -- )
    {
        int l, r, x;
        scanf("%s%d%d", op, &l, &r);
        if(*op == 'Q')
        {
            scanf("%d", &x);
            modify(1, l, r, x);
        }
        else
        {
            int sum = query(1, l, r);
            if(sum > 45) puts("YES");
            else if(sum <= 2) puts("NO");
            else
            {
                bool flag = false;    
                vector<int> tmp;
                for(int i = l; i <= r; i ++ ) 
                    for(auto tt :v[i]) tmp.push_back(tt);
                int oo = tmp.size();
                sort(tmp.begin(), tmp.end());
                for(int i = 0; i + 2< oo; i ++ )
                {
                    if(tmp[i] + tmp[i + 1] > tmp[i + 2]) 
                    {
                        flag = true;
                        break;
                    }
                }
                if(flag) puts("YES");
                else puts("NO");
            }
        }
    }

    return 0;
}

2020牛客暑期多校训练营（第二场）-C

原题链接：C.Cover the Tree

给你一棵无根树，请你用最少的链覆盖这棵树，使得树上每条边都被至少覆盖一次

$1\le n \le 2e5$

分析：

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

using namespace std;

const int N = 200005, M = 2 * N;

int n;
int h[N], e[M], ne[M], idx, depth[N];
vector<int> v;
vector<int> dep_point[N];
int max_dep;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs1(int u, int fa, int dep)
{
    max_dep = max(max_dep, dep);
    depth[u] = dep;
    dep_point[dep].push_back(u);

    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        dfs1(j, u, dep + 1);
    }
}

void dfs2(int u, int fa)
{
    bool flag = true;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa) continue;
        flag = false;
        dfs2(j, u);
    }
    if(flag) v.push_back(u);

}

int count_root_son(int root)
{
    int cnt = 0;
    for(int i = h[root]; ~i; i = ne[i])
    {
        cnt ++;
    }
    return cnt;
}

int main()
{
    scanf("%d", &n);

    if(n == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    else if(n == 2)
    {
        cout << 1 << endl;
    }

    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i ++ )
    {
        int u, v;
        scanf("%d%d", &u, &v);
        if(n == 2)
        {
            cout << u << " " << v << endl;
            return 0;
        }
        add(u, v), add(v, u);
    }

    dfs1(1, -1, 1);    
    int root = dep_point[max_dep][0];

    dfs2(root, -1);
    v.push_back(root);
    // for(auto t : v) cout << t << " ";
    // return 0;
//     if(count_root_son(root) == 1)
//     {
//         cout << v.size() << endl;
//         cout << v[0] << " " << root << endl;
//     }
    int sz = v.size();
    if(sz % 2 == 0)
    {
        cout << sz / 2 << endl;
        int mid = (0 + sz - 1) >> 1;
        for(int i = 0, j = mid + 1; i <= mid; i ++, j ++ )
        {
            cout << v[i] << " " << v[j] << endl;
        }
    }
    else
    {
        cout << sz / 2 + 1 << endl;
        int mid = (0 + sz - 1) >> 1;
        for(int i = 0, j = mid + 1; i < mid; i ++ , j ++ )
        {
            cout << v[i] << " " << v[j] << endl;
        }
        cout << v[mid] << " " << v[sz - 1] << endl;
    }


    return 0;
}