牛客：Gambling Monster（權值線段樹+離散化+離線）

題意：

作為一個賭徒，魏先生不僅擅長玩地主（紙牌遊戲），而且還擅長使用道具。在房東那裡，有一種道具叫雙卡，我更喜歡叫它DC。在一輪中，如果我們使用DC，我們的分數将加倍。當然，每個DC隻能使用一次，而且每輪最多隻能使用一個DC。

現在，魏先生想問你一個Q（1<=Q<=10萬）問題，每個問題給出兩個整數T（1<=T<=2）和X，T和X的意義如下。

T=1：你從魏先生那裡得到X（1<=X<=5）DC。

T=2：你進行一輪，得到X（| X |<=1000000000）分數（不含DC）。

對于每個問題，你應該給出一個整數S（你能得到的最高分數）。

道具的使用在每個問題是獨立的，道具将在你開始任何一輪之前給予。換言之，對于問題i，你也可以在問題k（k<j<i）中給出的循環中使用問題j中給出的DC。

題解：

//事先對所有插入的正數離散化
//然後開一顆權值線段樹
//每個節點維護區間内的數量之和和區間内的所有數的數量權值乘積和
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
typedef long long ll;
struct node {
    int l,r;
    ll sum;
    ll cnt;
}segTree[maxn<<2];
struct query {
    int op;
    ll w;
}q[maxn];
ll t[maxn];
int n;
int dc;
int tot=0;
ll ans=0;
void build (int i,int l,int r) {
    segTree[i].l=l;
    segTree[i].r=r;
    if (l==r) {
        segTree[i].sum=0;
        segTree[i].cnt=0;
        return;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum;
    segTree[i].cnt=segTree[i<<1].cnt+segTree[i<<1|1].cnt;
} 
void up (int i,int p,ll v) {
    if (segTree[i].l==p&&segTree[i].r==p) {
        segTree[i].cnt+=v;
        segTree[i].sum+=t[p]*v;
        return;
    }
    int mid=(segTree[i].l+segTree[i].r)>>1;
    if (p<=mid) up(i<<1,p,v);
    if (p>mid) up(i<<1|1,p,v);
    segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum;
    segTree[i].cnt=segTree[i<<1].cnt+segTree[i<<1|1].cnt;
}
ll query_cnt (int i,int l,int r) {
    if (segTree[i].l>=l&&segTree[i].r<=r) {    
        return segTree[i].cnt;
    }
    int mid=(segTree[i].l+segTree[i].r)>>1;
    ll ans=0;
    if (l<=mid)
        ans+=query_cnt(i<<1,l,r);
    if (r>mid)
        ans+=query_cnt(i<<1|1,l,r);
    return ans;
}
ll query_sum (int i,int l,int r) {
    if (segTree[i].l>=l&&segTree[i].r<=r) {    
        return segTree[i].sum;
    }
    int mid=(segTree[i].l+segTree[i].r)>>1;
    ll ans=0;
    if (l<=mid)
        ans+=query_sum(i<<1,l,r);
    if (r>mid)
        ans+=query_sum(i<<1|1,l,r);
    return ans;
}

int main () {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%d%lld",&q[i].op,&q[i].w);
        if (q[i].op==2) t[++tot]=q[i].w;
    } 
    sort(t+1,t+tot+1);
    int m=unique(t+1,t+tot+1)-t-1;
    build(1,1,m);
    for (int i=1;i<=n;i++) {
        int op=q[i].op;
        ll w=q[i].w;
        int u=-1;
        if (op==1) {
            dc+=w;
            int k=min((ll)dc,query_cnt(1,1,m));
            int l=1,r=m;
            while (l<=r) {
                int mid=(l+r)>>1;
                if (query_cnt(1,mid,m)>=k) {
                    u=mid;
                    l=mid+1;
                }
                else {
                    r=mid-1;
                }
            }
            ll tt=query_cnt(1,u+1,m);
            printf("%lld\n",ans+query_sum(1,u+1,m)+t[u]*(k-tt));
        }
        else {
            ans+=w;
            if (w>0) {
                int p=upper_bound(t+1,t+m+1,w)-t-1;
                up(1,p,1);
            }
            int k=min((ll)dc,query_cnt(1,1,m));
            int l=1,r=m;
            while (l<=r) {
                int mid=(l+r)>>1;
                if (query_cnt(1,mid,m)>=k) {
                    u=mid;
                    l=mid+1;
                }
                else {
                    r=mid-1;
                }
            }
            ll tt=query_cnt(1,u+1,m);
            printf("%lld\n",ans+query_sum(1,u+1,m)+t[u]*(k-tt));
        }
    }
}