【HDU 6315】Naive Operation / 题解

HDU 原题地址

Statement

In a galaxy far, far away, there are two integer sequence a and b of length n.
b is a static permutation of 1 to n. Initially a is filled with zeroes.
There are two kind of operations:
1. add l r: add one for $a_l,a_{l+1}…a_r$
2. query l r: query $\sum_{i=l}^r \lfloor a_i / b_i \rfloor$

Input

There are multiple test cases, please read till the end of input file.
For each test case, in the first line, two integers n,q, representing the length of a,b and the number of queries.
In the second line, n integers separated by spaces, representing permutation b.
In the following q lines, each line is either in the form ‘add l r’ or ‘query l r’, representing an operation.
$1≤n,q≤100000$, $1≤l≤r≤n$, there’re no more than 5 test cases.

Idea

这道题是简单数据结构的简单应用。

线段树维护区间内最大的 $a$,最小的 $b$,懒惰标记以及所求的答案 $sum$。区间更新的时候如果 $\max a > \min b$ 就一直暴力更新到 $sum$ 更改的点上,然后令 $\min b = \min b + b_i$。

Code

#include 
#define ls (p<<1)
#define rs (p<<1|1)
#define len (r-l+1)
#define mid ((l+r)>>1)
#define maxn 100100
using namespace std;
struct Node{
    int sum,maxa,minb,add;
}tree[maxn<<2];
int n,m,b[maxn];
void pushup(int p){
    tree[p].sum=tree[ls].sum+tree[rs].sum;
    tree[p].maxa=max(tree[ls].maxa,tree[rs].maxa);
    tree[p].minb=min(tree[ls].minb,tree[rs].minb);
}
void pushdown(int p){
    tree[ls].maxa+=tree[p].add;
    tree[rs].maxa+=tree[p].add;
    tree[ls].add+=tree[p].add;
    tree[rs].add+=tree[p].add;
    tree[p].add=0;
}
void build(int l,int r,int p){
    if (l==r){
        tree[p].minb=b[l];
        return;
    }
    build(l,mid,ls);
    build(mid+1,r,rs);
    pushup(p);
}
void update(int l,int r,int L,int R,int p){
    if (l>R||r=L&&r<=R){
        tree[p].maxa++;
        if (tree[p].maxaR||r=L&&r<=R) return tree[p].sum;
    if (tree[p].add) pushdown(p);
    return query(l,mid,L,R,ls)+query(mid+1,r,L,R,rs);
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        memset(tree,0,sizeof(tree));
        for (int i=1;i<=n;i++)
            cin>>b[i];
        build(1,n,1);
        while(m--){
            string op;int x,y;
            cin>>op>>x>>y;
            if (op=="add") update(1,n,x,y,1);
            else cout<