免费送气球

http://acm.hdu.edu.cn/showproblem.php?pid=6464

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 537 Accepted Submission(s): 117

Problem 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 ", 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

1 5 1

1 6 3

2 2 5

2 4 8

1 2 2

2 4 8

Sample Output

思路：用权值线段树找第n小的数，用线段树求和

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define lson l,mid,rt<<1
  4 #define rson mid+1,r,rt<<1|1
  5 #define sqr(x) ((x)*(x))
  6 #define pb push_back
  7 #define eb emplace_back
  8 #define maxn 100005
  9 #define eps 1e-8
 10 #define pi acos(-1.0)
 11 #define rep(k,i,j) for(int k=i;k<j;k++)
 12 typedef long long ll;
 13 typedef pair<int,int> pii;
 14 typedef pair<double,double>pdd;
 15 typedef pair<int,char> pic;
 16 typedef pair<pair<int,string>,pii> ppp;
 17 typedef unsigned long long ull;
 18 const long long MOD=1000000007;
 19 const double oula=0.57721566490153286060651209;
 20 using namespace std;
 21 
 22 struct sair{
 23     int type;
 24     ll x,y;
 25 }a[maxn];
 26 
 27 vector<ll>ve;
 28 
 29 ll num[maxn<<2],sum[maxn<<2];
 30 
 31 void push_up(int rt){
 32     num[rt]=num[rt<<1]+num[rt<<1|1];
 33     sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%MOD;
 34 }
 35 
 36 void update(int L,ll nu,ll v,int l,int r,int rt){
 37     if(l==r){
 38         num[rt]+=nu;
 39         sum[rt]=(sum[rt]+(v*nu)%MOD)%MOD;
 40         return;
 41     }
 42     int mid=l+r>>1;
 43     if(L<=mid) update(L,nu,v,lson);
 44     else update(L,nu,v,rson);
 45     push_up(rt);
 46 }
 47 
 48 ll querynum(ll L,int l,int r,int rt){///L忘了开LL,找了半天bug。。。。
 49     if(l==r) return r;
 50     int mid=l+r>>1;
 51     if(num[rt<<1]>=L) return querynum(L,lson);
 52     else return querynum(L-num[rt<<1],rson);
 53 }
 54 
 55 ll querynum(int L,int R,int l,int r,int rt){
 56     if(L<=l&&R>=r) return num[rt];
 57     int mid=l+r>>1;
 58     ll ans=0;
 59     if(L<=mid) ans+=querynum(L,R,lson);
 60     if(R>mid) ans+=querynum(L,R,rson);
 61     return ans;
 62 }
 63 
 64 ll querysum(int L,int R,int l,int r,int rt){
 65     if(L<=l&&R>=r) return sum[rt];
 66     int mid=l+r>>1;
 67     ll ans=0;
 68     if(L<=mid) ans=(ans+querysum(L,R,lson))%MOD;
 69     if(R>mid) ans=(ans+querysum(L,R,rson))%MOD;
 70     return ans;
 71 }
 72 
 73 
 74 int getid(ll x){
 75     return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+1;
 76 }
 77 
 78 int main(){
 79     std::ios::sync_with_stdio(false);
 80     int n;
 81     cin>>n;
 82     for(int i=1;i<=n;i++){
 83         cin>>a[i].type>>a[i].x>>a[i].y;
 84         if(a[i].type==1) ve.pb(a[i].y);
 85     }
 86     sort(ve.begin(),ve.end());
 87     ll pos,pos1,pos2,tmp1,tmp2;
 88     for(int i=1;i<=n;i++){
 89         if(a[i].type==1){
 90             pos=getid(a[i].y);
 91             update(pos,a[i].x,a[i].y,1,n,1);
 92         }
 93         else{
 94             ll ans=0;
 95             pos1=querynum(a[i].x,1,n,1);///ve[pos1-1]为值
 96             tmp1=querynum(1,pos1,1,n,1);
 97             pos2=querynum(a[i].y,1,n,1);
 98             if(pos2>1) tmp2=querynum(1,pos2-1,1,n,1);
 99             else tmp2=0;
100            // cout<<pos2<<endl;
101           //  cout<<pos2-1<<endl;
102            // tmp2=querynum(1,pos2-1,1,n,1);
103             /**
104                 1.x==y
105                 2.x与y在同一个区域
106                 3.x与y相邻
107             */
108             if(pos1==pos2){
109                 ans=((a[i].y-a[i].x+1)*ve[pos1-1])%MOD;
110             }
111             else if(pos2-pos1==1){
112                 ans=(((tmp1-a[i].x+1)*ve[pos1-1])%MOD+((a[i].y-tmp2)*ve[pos2-1])%MOD)%MOD;
113             }
114             else{
115                 ans=(((tmp1-a[i].x+1)*ve[pos1-1])%MOD+((a[i].y-tmp2)*ve[pos2-1])%MOD+querysum(pos1+1,pos2-1,1,n,1)%MOD)%MOD;
116             }
117 
118             cout<<ans<<endl;
119         }
120     }
121 }
122 /**
123 6
124 1 5 1000000000
125 1 6 3000000000
126 2 2 5
127 2 4 8
128 1 2 2000000000
129 2 4 8
130 */

View Code