Naive Operations HDU6315 （杭电多校2G）

让ci = ai / bi, 求sum(ci)的值，因为每次 ai 都是加一的，那么我可以用一颗线段树来维护每个 i 位置的 ai 距离达到 bi 还需要的数的最小值，更新是每次都减一，如果我某一个区间的最小值等于 0，这就说明我这时候的ai已经满足了ai/bi==1的情况，那么对应的ci的位置就应该加一，所以我每次发现一个区间的最小值是0的话，我就 dfs 去找到为0的地方，把这里重新修改成bi，然后这个位置的答案+1就可以了

#include<map>

#include<set>

#include<ctime>

#include<cmath>

#include<stack>

#include<queue>

#include<string>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define first fi

#define second se

#define lowbit(x) (x & (-x))

typedef unsigned long long int ull;

typedef long long int ll;

const double pi = 4.0*atan(1.0);

const int inf = 0x3f3f3f3f;

const int maxn = ;

const int maxm = ;

const int mod = ;

using namespace std;

int n, m, tol, T;

int a[maxn];

int b[maxn];

int c[maxn << ];

int sum[maxn << ];

int lazy[maxn << ];

void init() {

    memset(a, , sizeof a);

    memset(b, , sizeof b);

    memset(c, , sizeof c);

    memset(sum, inf, sizeof sum);

    memset(lazy, , sizeof lazy);

}

void pushup(int root) {

    sum[root] = min(sum[root << ], sum[root <<  | ]);

    c[root] = c[root << ] + c[root <<  | ];

}

void pushdown(int root) {

    if(lazy[root] != ) {

        lazy[root << ] += lazy[root];

        lazy[root <<  | ] += lazy[root];

        sum[root << ] -= lazy[root];

        sum[root <<  | ] -= lazy[root];

        lazy[root] = ;

    }

    return ;

}

void build(int left, int right, int root) {

    if(left == right) {

        sum[root] = b[left];

        return ;

    }

    int mid = (left + right) >> ;

    build(left, mid, root << );

    build(mid+, right, root <<  | );

    pushup(root);

}

void dfs(int left, int right, int root) {

    if(left == right) {

        if(sum[root] == ) {

            sum[root] = b[left];

            c[root]++;

        }

        return ;

    }

    pushdown(root);

    int mid = (left + right) >> ;

    if(sum[root << ] == )

        dfs(left, mid, root << );

    if(sum[root <<  | ] == )

        dfs(mid+, right, root <<  | );

    pushup(root);

}

void update(int left, int right, int prel, int prer, int root) {

    if(prel <= left && right <= prer) {

        lazy[root]++;

        sum[root]--;

        while(sum[root] == )    dfs(left, right, root);

        return ;

    }

    pushdown(root);

    int mid = (left + right) >> ;

    if(prel <= mid)    update(left, mid, prel, prer, root << );

    if(prer > mid)    update(mid+, right, prel, prer, root <<  | );

    pushup(root);

}

int query(int left, int right, int prel, int prer, int root) {

    if(prel <= left && right <= prer) return c[root];

    int mid = (left + right) >> ;

    int ans = ;

    if(prel <= mid)    ans += query(left, mid, prel, prer, root << );

    if(prer > mid)    ans += query(mid+, right, prel, prer, root <<  | );

    return ans;

}

int main() {

    while(~scanf("%d%d", &n, &m)) {

        init();

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

        build(, n, );

        char str[];

        while(m--) {

            int l, r;

            scanf("%s%d%d", str, &l, &r);

            if(str[] == 'a') {

                update(, n, l, r, );

            } else if(str[] == 'q') {

                int ans = query(, n, l, r, );

                printf("%d\n", ans);

            }

        }

    }

    return ;

}

巴特西

Naive Operations HDU6315 （杭电多校2G）

最新文章

热门文章