题意：

有一个长度为n的序列a和一个相同长度的序列b，a初始都为0，b初始为乱序的全排列。现在有两种操作，共操作q次：

add l r：对于$a_l,a_{l+1}...a_r$加一；

query l r：询问$\sum_{i=l}^r\lfloor \frac{a_i}{b_i}\rfloor$。

其中$1 \leq n,q \leq 100000$，$1 \leq l \leq r \leq n$。

思路：

在经过q次操作之后，$\sum_{i=1}^n\frac{a_i}{b_i}$最大为$\sum_{i=1}^n\lfloor \frac{q}{b_i}\rfloor$，因为b为全排列，有调和级数$\sum_{i=1}^n \frac{q}{b_i}<=qlogn$。

建立两棵线段树，一棵树A维护序列a的最小值，另一棵树B维护$\lfloor \frac{a_i}{b_i}\rfloor$的和。

对于add操作，将A的$[l,r]$区间减1，时间复杂度为$O(logn)$。当发现该区间的最小值等于0，就向下dfs，找到那个最小值为0的叶子，对这个叶子对应的$\lfloor \frac{a_i}{b_i}\rfloor$进行修改，复杂度上面证明了应该为$O(qlogn)$。

所以总的复杂度为$O(q*qlogn)$。

比赛的时候就是卡在要如何知道哪个点要对$\lfloor \frac{a_i}{b_i}\rfloor$进行修改，也没想到这个全排列居然是这么用的，有勇气的时候还是要暴力一发啊…不要怕写之后要调很久（虽然补题的时候的确调了很久…懒标记下放的地方没有累加啊…

写线段树的时候也仔细一点吧。

代码：

typedef long long ll;
ll tot;
ll ori[100010];
int num;
struct node1
{
    int l,r;
    ll mmin,f1;
    ll sum;
    int pos;
}b[100010<<2];
void build(int L,int R,int id)
{
    b[id].l=L;b[id].r=R;
    b[id].f1=0;
    b[id].sum=0;
    if(L==R)
    {
        b[id].mmin=ori[++num];
        b[id].pos=num;
        return;
    }
    int m=(L+R)>>1;
    build(L,m,id<<1);
    build(m+1,R,id<<1|1);
    b[id].mmin=min(b[id<<1].mmin,b[id<<1|1].mmin);
}
void pushdown1(int id)
{
    ll c=b[id].f1;
    b[id<<1].mmin-=c;b[id<<1|1].mmin-=c;
    b[id<<1].f1+=b[id].f1;b[id<<1|1].f1+=b[id].f1;
    b[id].f1=0;
}
void update2(int loc,int id)
{
    int l=b[id].l,r=b[id].r;
    if(l==r)
    {
        b[id].sum++;
        return;
    }
    int m=(l+r)>>1;
    if(loc<=m)update2(loc,id<<1);
    if(loc>m)update2(loc,id<<1|1);
    b[id].sum=b[id<<1].sum+b[id<<1|1].sum;
}
void update(int loc,ll c,int id)
{
    int l=b[id].l,r=b[id].r;
    if(l==r)
    {
        b[id].mmin=c;
        return;
    }
    int m=(l+r)>>1;
    if(loc<=m)update(loc,c,id<<1);
    if(loc>m)update(loc,c,id<<1|1);
    b[id].mmin=min(b[id<<1].mmin,b[id<<1|1].mmin);
}
void dfs(int id)
{
    int l=b[id].l,r=b[id].r;
    if(l==r)
    {
        if(b[id].mmin==0)
        {
            update(b[id].pos,ori[b[id].pos],1);
            update2(b[id].pos,1);
        }
        return;
    }
    if(b[id].f1!=0)pushdown1(id);
    if(b[id<<1].mmin==0)dfs(id<<1);
    if(b[id<<1|1].mmin==0)dfs(id<<1|1);
    b[id].mmin=min(b[id<<1].mmin,b[id<<1|1].mmin);
}
void update1(int L,int R,int id)
{
    int l=b[id].l,r=b[id].r;
    if(l>=L&&r<=R)
    {
        b[id].mmin--;
        b[id].f1++;
        if(b[id].mmin==0)
            dfs(id);
        return;
    }
    if(b[id].f1!=0)pushdown1(id);
    int m=(l+r)>>1;
    if(L<=m)update1(L,R,id<<1);
    if(R>m)update1(L,R,id<<1|1);
    b[id].mmin=min(b[id<<1].mmin,b[id<<1|1].mmin);
}
void query(int L,int R,int id)
{
    int l=b[id].l,r=b[id].r;
    if(l>=L&&r<=R)
    {
        tot+=b[id].sum;
        return;
    }
    int m=(l+r)>>1;
    if(L<=m)query(L,R,id<<1);
    if(R>m)query(L,R,id<<1|1);
}
int main()
{
    int n,q,x,y;
    char s[10];
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%lld",&ori[i]);
        num=0;
        build(1,n,1);
        while(q--)
        {
            scanf("%s",s);
            scanf("%d%d",&x,&y);
            if(s[0]=='a')
                update1(x,y,1);
            else if(s[0]=='q')
            {
                tot=0;
                query(x,y,1);
                printf("%lld\n",tot);
            }
        }
    }
    return 0;
}