HDU6464 免费送气球

Description

  又到了GDUT一年一度的程序设计竞赛校赛的时间啦。同学们只要参加校赛，并且每解出一道题目就可以免费获得由ACM协会和集训队送出的气球一个。听到这个消息，JMC也想参加免费拿气球。可是，由于JMC太菜了而被禁止参赛，于是他找到你想让你帮忙参加比赛，可以通过执行下面的C++程序解决问题后获得气球并送给他。JMC保证了下面的程序一定能获得正确的结果。

void solve(int Q, int type[], long long first[], long long second[]) {
    vector<long long> vec;
    for (int i = 0; i < Q; ++i) {
        if (type[i] == 1) {
            long long k = first[i], val = second[i];
            while (k--) {
                vec.push_back(val);
            }
        }
        else if (type[i] == 2) {
            sort(vec.begin(), vec.end());
            long long l = first[i] - 1, r = second[i], res = 0;
            while (l < r) {
                res = (res + vec[l++]) % 1000000007;
            }
            printf("%lld\n", res);
        }
    }
}

为防止你被JMC的代码搞到头晕目眩，JMC特意给出了问题的文字描述。已知一开始有一个空序列，接下来有Q次操作，每次操作给出type、first和second三个值。当type为1时，意味着该操作属于第一种操作：往序列尾部添加first个second数。当type为2时，意味着该操作属于第二种操作：查询序列中第first小至第second小的数值之和（一共有(second - first + 1)个数被累加），并将结果对1000000007取模后输出。
Input 单组数据 第一行一个Q（1 <= Q <= 1e5），代表Q次操作。 接下来有Q行，每行包含三个整数type、first和second；其中1 <= type <= 2。当type等于1时，0 <= first,second < 1e9。当type等于2时，1 <= first <= second，且first和second均不大于目前已添加进序列的数的数量。

Output

对于每次操作二，将结果对1000000007取模后输出。

Sample Input

6
1 5 1
1 6 3
2 2 5
2 4 8
1 2 2
2 4 8

Sample Output

4
11
9

思路：
可以当成权值线段树的模板的题。关键在于query的处理。
全在左直接算左儿子，全在右要减去左儿子再算右儿子。两边都有要le到左儿子右端点+右儿子左端点到ri.

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxm=1e9+7;
typedef long long ll;

struct func{
    int type;
    ll fir,sec;
}q[maxn];
ll a[maxn],t;
ll tree[4*maxn],sum[4*maxn];

void pushup(int now)
{
    tree[now]=tree[now<<1]+tree[now<<1|1];
    sum[now]=(sum[now<<1]+sum[now<<1|1])%maxm;
}

void insert(int now,int pos,int le,int ri,int num)
{
    if(le==ri)
    {
        tree[now]+=num;
        sum[now]=tree[now]%maxm*a[le]%maxm;
        return;
    }
    int mid=(le+ri)>>1;
    if(pos<=mid) insert(now<<1,pos,le,mid,num);
    else insert(now<<1|1,pos,mid+1,ri,num);
    pushup(now);
}

ll query(int now,int le,int ri,ll fir,ll sec)//WA了两发的地方。没注意到fir和sec可以爆int
{
    ll sums=0;
    if(fir==1&&tree[now]==sec) return sum[now]%maxm;
    if(le==ri) return (sec-fir+1)%maxm*a[le]%maxm;
    int mid=(le+ri)>>1;
    if(sec<=tree[now<<1]) sums=query(now<<1,le,mid,fir,sec)%maxm;//关键步骤！！！
    else if(fir>tree[now<<1]) sums=query(now<<1|1,mid+1,ri,fir-tree[now<<1],sec-tree[now<<1])%maxm;
    else
    {
        sums=(query(now<<1,le,mid,fir,tree[now<<1])+query(now<<1|1,mid+1,ri,1,sec-tree[now<<1]))%maxm;
    }
    return sums;
}

void run()
{
    int Q;
    cin>>Q;
    for(int i=1;i<=Q;i++)
    {
        scanf("%d%lld%lld",&q[i].type,&q[i].fir,&q[i].sec);
        if(q[i].type==1) a[++t]=q[i].sec;
    }
    sort(a+1,a+t+1);
    t=unique(a+1,a+t+1)-(a+1);//WA了一发的地方。权值线段树必须要排序后去重。unique返回值的意思是剩余长度
    for(int i=1;i<=Q;i++)
    {
        if(q[i].type==1)
        {
            insert(1,lower_bound(a+1,a+t+1,q[i].sec)-a,1,t,q[i].fir);
        }
        else
        {
            cout<<query(1,1,t,q[i].fir,q[i].sec)<<endl;
        }
    }
}

int main()
{
    run();
    return 0;
}