4.29 线段树练习的一些提示

未分类

2. I Hate It

讲第一题的update修改一行即可

线段树功能:update:单点替换 query:区间最值

提供int main:

int main(){
    //freopen("in.txt", "r", stdin);
    int _, n, m, x, y; 
    for (;~scanf("%d%d", &n, &m);){        
        T.build(n);
        string st;
        for (;m--;){
            cin >>st;
            scanf("%d%d", &x, &y);
            if (st[0] == 'U'){
                T.update(x, y);
            }else{
                printf("%d\n", T.query(x, y));
            }
        }
    }
}

3. Minimum Inversion Number

数字插入按顺序插入对应的位置，然后看这个位置后面有多少个数就有多少逆序对

单点修改，区间求和

支持使用树状数组，若不熟练群里提出下节课复习一下

4. Billboard

注意：h = min(h, n);

单点查询区间最大值，查询修改一体

inline int query(int x, int rt){
    if (rt > M){
        val[rt] -= x;
        return rt - M;
    }
    int ans = (val[lc] >= x) ? query(x, lc) : query(x, rc);
    pushUp(rt);
    return ans;
}

5. Buy Tickets

单点查询修改

跟上题很像，查询修改一体

    inline void update(int pos, int jump, int rt){
        if (rt > M){
            val[rt]--;
            ans[rt-M] = jump;
            return;
        }
        if (val[lc] >= pos) update(pos, jump, lc);
        else update(pos-val[lc], jump, rc);
        pushUp(rt);
    }

提示：倒着操作就不存在插入的问题了

6. Who Gets the Most Candies

反素数 + 单点操作

题意：

n个熊孩子每个人有个数字a[i]，首先k号熊孩子出圈，然后第k+a[i]个熊孩子出圈，一个环，可以绕很多圈，如果a[i]为正则顺时针数，反之逆时针，相当于一个变体的约瑟夫游戏，第i个出圈的熊孩子，有f[i]的得分，f[i]为i的因子个数
反正没人看的讲解：

分为两个部分：线段树模拟约瑟夫游戏+寻找1到n范围内因数数量最多的那个ans，约瑟夫游戏只要做到第ans个人出圈就好了

区间和的线段树，每个叶子节点为1，代表一个熊孩子，出圈置为0，

百度关键字，反素数

提供一个反素数打表方案

const int prime[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
struct child{
    char name[11];
    int val;
    inline void read(){scanf("%s %d\n", name, &val);}
}arr[N];
LL maxNum, ansPos, n;
void dfs(int dep, LL tmp, int num){
    if (dep >= 16) return;
    if (num > maxNum){
        maxNum = num;
        ansPos = tmp;
    }
    if (num == maxNum && ansPos > tmp) ansPos = tmp;
    for (int i = 1; i < 63; i++){
        if (n / prime[dep] < tmp) break;
        dfs(dep+1, tmp *= prime[dep], num*(i+1));
    }
}