【2018 Multi-University Training Contest 2 1007】Naive Operations

给你两个数组a,b; b数组是1..n的一个排列。现在给你两种操作: add l,r将a[l..r]都加上1 query l,r 询问$∑^r_lfrac{ai}{bi} $ 其中a[i]/b[i]是下取整。 n<=10^5

【题解】

很优秀的题我们可以在线段树1中维护所有a[i]/b[i]的值想一下何时我们才要让线段树1中的值改变? 必然是我们一直加a的值,让a[i]的值超过了b[i] 设让线段树中的值改变操作为操作x 那么操作x最多湖执行多少次呢? a最多变成10^5 那么就是 ∑10^5/b[i] ,又b是一个排列那么原式即$10^5*(1/1+1/2+1/3+...+1/n)$ 其中右边那个式子是logn级别的。那么总共要进行的操作x的次数就约等于n*logn 那么我们可以这么做。另外开一个线段树2. 这个线段树一开始每个位置上的值为b[i] 我们可以维护一下区间最小值。然后每次add(l,r)对应地把线段树2中相应位置递减1. 直到发现某个位置变成0了(最小值变成0就说明有些位置变成0了那么就把线段树1中对应的a[i]/b[i]的值递增1. 然后再把那个位置重置为对应的b[i]就可以了。根据上面的分析，这个递增操作次数最多n*logn次。 query操作直接就是线段树1的区间求和问题了。很轻松就能解决。

【代码】

#include <bits/stdc++.h>
#define LL long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define rep1(i,a,b) for (int i = a;i<= b;i++)
using namespace std;

const double pi = acos(-1);
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};
const int N = 1e5;

int a[N+10],b[N+10],mi[N*4+10],tag[N*4+10],sum2[N*4+10];
int n,q;
char s[8];

void _updata2(int l,int r,int rt,int pos){
    if (l==r){
        sum2[rt]++;
        return;
    }
    int mid = (l+r)>>1;
    if (pos<=mid) _updata2(lson,pos);
    else _updata2(rson,pos);
    sum2[rt] = sum2[rt<<1]+sum2[rt<<1|1];
}

void push_down(int rt){
    if (tag[rt]>0){
        tag[rt<<1]+=tag[rt];tag[rt<<1|1]+=tag[rt];
        mi[rt<<1]-=tag[rt];mi[rt<<1|1]-=tag[rt];
        tag[rt] = 0;
    }
}

void _find0(int l,int r,int rt){
    if (l==r){
        _updata2(1,n,1,l);
        mi[rt] = b[l];
        return;
    }
    push_down(rt);
    int mid = (l+r)>>1;
    if (mi[rt<<1]==0) _find0(lson);
    if (mi[rt<<1|1]==0)_find0(rson);
    mi[rt]= min(mi[rt<<1],mi[rt<<1|1]);
}

void _updata1(int l,int r,int rt,int L,int R){
    if (L<=l && r<=R){
        mi[rt]--;
        tag[rt]++;
        if (mi[rt]==0){
            _find0(l,r,rt);
        }
        return;
    }
    push_down(rt);
    int mid = (l+r)>>1;
    if (L<=mid) _updata1(lson,L,R);
    if (mid<R) _updata1(rson,L,R);
    mi[rt] = min(mi[rt<<1],mi[rt<<1|1]);
}

long long get_ans2(int l,int r,int rt,int L,int R){
    if (L<=l && r <= R) return sum2[rt];
    int mid = (l+r)>>1;
    long long temp1 = 0,temp2 = 0;
    if (L<=mid) temp1 = get_ans2(lson,L,R);
    if (mid<R) temp2 = get_ans2(rson,L,R);
    return temp1+temp2;
}

void build1(int l,int r,int rt){
    tag[rt] = 0;
    int mid = (l+r)>>1;
    if (l==r){
        mi[rt] = b[l];
        return;
    }
    if (l<=mid) build1(lson);
    if (mid<r) build1(rson);
    mi[rt] = min(mi[rt<<1],mi[rt<<1|1]);
}

int main(){
    #ifdef LOCAL_DEFINE
        freopen("rush_in.txt", "r", stdin);
    #endif
    ios::sync_with_stdio(0),cin.tie(0);
    while (cin >> n >> q)
    {
        memset(a,0,sizeof a);
        memset(sum2,0,sizeof sum2);
        rep1(i,1,n) cin >> b[i];
        build1(1,n,1);
        while (q--)
        {
            int ll,rr;
            cin >> s >> ll >> rr;
            if (s[0]=='a')
                _updata1(1,n,1,ll,rr);
            else
                cout<<get_ans2(1,n,1,ll,rr)<<endl;

        }
    }
    return 0;
}