GroupBlog

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:

add l r: add one for al,al+1…ar
query l r: query ∑ri=l⌊ai/bi⌋
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.
Output
Output the answer for each ‘query’, each one line.
Sample Input
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
Sample Output
1
1
2
4
4
6

题意：
就是我们有一个初始为零的区间和一个静态的区间执行的操作有两种一种是对初始为零的区间进行修改一种是查询区间和但这个区间和并不是一般的区间和而是(ai/bi)的区间和

思路:
因为我们初始的两个区间大小相同所以我们可以直接用线段树去维护我们需要的答案如果不是维护一个答案而是用两棵线段树则无法在query操作得到我们想要的答案分析到这里我们需要爱update操作的时候对每一个叶子节点进行判断如果ai/bi大于1 则表示答案应该更新同时记得给bi加上一个相应的初始值为下一次更新做准备这样来得到我们最后的答案

AC代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100000+5;
int book[maxn];
char ch[10];
#define lson (q<<1)
#define rson (q<<1|1)
#define mid ((l+r)>>1)
int m,n;
int tmpa,tmpb;
struct node
{
    int Max,Min;
    int val;
    int flag;
};
struct node segt[maxn<<2];

void push_up(int q)
{
    segt[q].Max=max(segt[lson].Max,segt[rson].Max);
    segt[q].Min=min(segt[lson].Min,segt[rson].Min);
    segt[q].val=segt[lson].val+segt[rson].val;
}

void build_tree(int q,int l,int r)
{
    segt[q].flag=0;
    if(l==r)
    {
        segt[q].Max=0;
        segt[q].Min=book[l];
        segt[q].val=0;
        return; //第一遍忘记写了
    }
    int m=mid;
    build_tree(lson,l,m);
    build_tree(rson,m+1,r);
    push_up(q);
    return;
}

void push_down(int q)
{
    if(segt[q].flag)
    {
        segt[lson].flag+=segt[q].flag;
        segt[rson].flag+=segt[q].flag;
        segt[lson].Max+=segt[q].flag; 
        segt[rson].Max+=segt[q].flag;
        segt[q].flag=0;
    }
}

void update(int q,int l,int r,int a,int b)
{
    if(l>=a && r<=b)
    {
        segt[q].Max+=1;
        if(segt[q].Max<segt[q].Min)
        {
            segt[q].flag++;
            return;              //线段树中我们总要去对能优化的部分去做出优化 这可能就是ac与超时的距离
        }
        if(segt[q].Max>=segt[q].Min && l==r)
        {
            segt[q].val++;
            segt[q].Min+=book[l];//为下一次这个叶子节点上的值改变做准备
            return;
        }
    }
    push_down(q);
    int m=mid;
    if(a<=m) update(lson,l,m,a,b);
    if(b>m)  update(rson,m+1,r,a,b);
    push_up(q);
    return ;
}

int query(int q,int l,int r,int a,int b)
{
    if(l>=a && r<=b)
    {
        return segt[q].val;
    }
    push_down(q);
    int m=mid;
    int ans=0;
    if(a<=m) ans+=query(lson,l,m,a,b);
    if(b>m)  ans+=query(rson,m+1,r,a,b);
    return ans;
}

int main()
{
    while(~scanf("%d %d",&m,&n))
    {
        memset(segt,0,sizeof(segt));
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&book[i]);
        }
        build_tree(1,1,m);
        while(n--)
        {
            scanf("%s %d %d",ch,&tmpa,&tmpb);
            if(ch[0]=='a')
            {
                update(1,1,m,tmpa,tmpb);
            }
            else
            {
                printf("%d\n",query(1,1,m,tmpa,tmpb));
            }
        }
    }
    return 0;
}