题目

题目描述

天下最欢乐的事情就是大家在做题的时候moreD送分给大家。现在就让大家欢乐一下
首先大家排排坐，坐成一排
moreD会给大家送分，他会时而选择区间，从左到右依次用魔法给大家送分，最左边的孩子送$1$分，第二个送$2$分……以此类推
有时moreD会询问一个孩子到底已经被送了多少分
只要你能每次都迅速而正确地回答出moreD的问题，你就可以得到出题人送的分了，两天总得分最高的孩子可以得到神秘礼物

输入格式

第一行两个正整数$N,M$，表示有$N$个孩子，出题人有$M$次操作
接下来$M$行，每行代表一个操作
第一个字符为$c_i$,若$c_i=$C则此次操作为送分操作，接下来会有两个整数$L_i,R_i$，表示此次送分的区间
若$c_i=$Q，则此次操作为询问操作，接下来一个整数$x_i$，表示询问第$x_i$个孩子的当前得分数

输出格式

对于每组询问输出一行，仅包含一个整数，表示答案对$1000000007$取$mod$的结果

样例

样例输入

样例输出

1
2

2
3

数据范围与提示

对于$30\%$的数据$N,M\leqslant 1000$
对于$100\%$的数据$N,M\leqslant 100000$

题解

树状数组好题
看到这个形式，很容易让人想起树状数组的区间修改和区间求和（POJ3468）
但是增加的值是一个等差数列啊
那么，我们可以来化简一下这个式子
假设我们要查询第$x$个，答案为$ans_x$，那么，我们假设所有修改中，满足$L\leqslant x$且$R\geqslant x$的为$(L_1,R_1),(L_2,R_2),\cdots\cdots (L_{len},R_{len})$
那么，$ans_x=\sum\limits_{i=1}^{len}(x-L_i+1)=len\times (x+1)-\sum\limits_{i=1}^{len}L_i$
所以，我们只需要知道$len$和$\sum\limits_{i=1}^{len}L_i$就可以了
这两个量非常好求，开两个树状数组，对于每个$(L_i,R_i)$，第一个树状数组的$L_i$处$+1$，$R_i+1$处$-1$，第二个树状数组的$L_i$处$+L_i$，$R_i+1$处$-L_i$就可以了
附上代码：

#include<algorithm>
#include<cstdio>
using namespace std;
pair<long long,long long> ans;
int n,m;
long long x,y,MOD=1e9+7,c1[100010],c2[100010];
char op[2];
void add(long long x,long long X,int flag)
{
    for(;x<=n;x+=(x&(-x))) c1[x]+=flag*X,c2[x]+=flag;
}
pair<long long,long long> ask(long long x)
{
    long long s1=0,s2=0;
    for(;x;x-=(x&(-x))) s1+=c1[x],s2+=c2[x];
    return make_pair(s1,s2);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf(" %s%lld",op,&x);
        if(op[0]=='Q') ans=ask(x),printf("%lld\n",(((x+1)*ans.second%MOD-ans.first)%MOD+MOD)%MOD);
        if(op[0]=='C') scanf("%lld",&y),add(x,x,1),add(y+1,x,-1);
    }
}