HDU 6315 Naive Operations(线段树)

HDU 6315 Naive Operations

n个数，q个询问

起始a、b数组都是n个元素，a数组全是0，b是1~n的全排列

add l r ：a中【l，r】都加1

query l r ：询问∑floor(ai/bi) (i : l~r)

思路：

区间更新的线段树，维护区间最小值min（bi-ai%bi） 当min=0时sum++。

具体看代码注释

#include <bits/stdc++.h>
#define MAXN 100010
#define inf 0x3f3f3f3f

using namespace std;

struct node{
    long long l,r;//区间[l,r]
    long long add;//区间的延时标记
    long long sum;//区间和
    long long mn; //区间最小值
    long long bi; //对应bi
}tree[MAXN<<2];//一定要开到4倍多的空间

void pushup(int index)
{
    tree[index].sum = tree[index<<1].sum+tree[index<<1|1].sum;
    tree[index].mn = min(tree[index<<1].mn,tree[index<<1|1].mn);
}
void pushdown(int index)
{
    //说明该区间之前更新过
    //要想更新该区间下面的子区间，就要把上次更新该区间的值向下更新
    if(tree[index].add)
    {
        tree[index<<1].mn -= tree[index].add;
        tree[index<<1|1].mn -= tree[index].add;
        tree[index<<1].add += tree[index].add;
        tree[index<<1|1].add += tree[index].add;
        tree[index].add = 0;
    }
}
void print(int l,int r,int index) //测试数据 输出具体
{
    printf("l:%d r:%d bi:%lld min:%lld sum:%lld lazy:%d\n",l,r,tree[index].bi,tree[index].mn,tree[index].sum,tree[index].add);
    if(tree[index].l==tree[index].r)
    {
         return;
    }
    int mid=(l+r)>>1;
    print(l,mid,index<<1);
    print(mid+1,r,index<<1|1);
}
void build(int l,int r,int index)
{
    tree[index].l = l;
    tree[index].r = r;
    tree[index].add = 0;//刚开始一定要清0
    tree[index].sum=0;
    if(l == r)
    {
        scanf("%lld",&tree[index].bi);
        tree[index].mn = tree[index].bi;
        tree[index].sum=0;
        return ;
    }
    int mid = (l+r)>>1;
    build(l,mid,index<<1);
    build(mid+1,r,index<<1|1);
    pushup(index);
}
void updata(int l,int r,int index)
{
    if(l<=tree[index].l&&r>=tree[index].r&&tree[index].mn>1) 
    {
        tree[index].mn--;
        tree[index].add++;
        return ;
    }
    if(tree[index].l==tree[index].r)
    {
        tree[index].mn--;
        tree[index].add++;
        if(tree[index].mn<=0)
        {
            tree[index].sum++;
            tree[index].mn=tree[index].bi;
        }
        return ;
    }
    pushdown(index);
    int mid = (tree[index].l+tree[index].r)>>1;

    if (r <= mid) updata(l,r,index<<1);
    else if (l>mid) updata(l,r,index<<1|1);
    else {
        updata(l,mid,index<<1);
        updata(mid+1,r,index<<1|1);
    }

    pushup(index);
}
long long query(int l,int r,int index)
{
    if(l == tree[index].l && r == tree[index].r)
        return tree[index].sum;

    pushdown(index);
    int mid = (tree[index].l+tree[index].r)>>1;
    long long ans = 0;
    if(r<=mid) ans = query(l,r,index<<1);
    else if(l>mid) ans = query(l,r,index<<1|1);
    else{
        return ans = query(l,mid,index<<1)+query(mid+1,r,index<<1|1);
    }
    pushup(index);
    return ans;
}
int main()
{
    int n,m,q,x,y,z;
    char s[100];
    while(~scanf("%d%d",&n,&m)){
    build(1,n,1);
    while(m--)
    {
        scanf("%s%d%d",s,&x,&y);
        if(s[0] =='q' )
            printf("%lld\n",query(x,y,1));
        else
            updata(x,y,1);
    //    print(1,n,1);
     //   printf("m:%d\n",m);
    }
    }
    return 0;
}
/*
5 12
1 5 2 4 3
add 1 4
query 1 4
add 2 5
query 2 5
add 3 5
query 1 5
add 2 4
query 1 4
add 2 5
query 2 5
add 2 2
query 1 5
*/