BZOJ-4636: 蒟蒻的数列

Description

DCrusher有一个数列，初始值均为0，他进行N次操作，每次将数列[a,b)这个区间中所有比k小的数改为k，他想知道N次操作后数列中所有元素的和。他还要玩其他游戏，所以这个问题留给你解决。N<=40000 , a、b、k<=10^9

第一眼，分块裸题。。。然后就GG了。
既然区间那么大，操作那么少，那把操作按区间的顺序差分排序就好了吧，找每一段区间的k的最大值。维护两个堆，一个为最大值，另一个为删除堆。然后在a的时候加k，b的时候删k就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
long long ans;
struct node
{
    int id,w;
}a[81000];
bool cmp(node x,node y){return x.id<y.id;}
priority_queue<int>q1,q2;
int main()
{
    int n,i,x,y,k,tot=0;
    scanf("%d",&n); 
    while(n--)
    {
        scanf("%d%d%d",&x,&y,&k);
        a[++tot].id=x; a[tot].w=k;
        a[++tot].id=y; a[tot].w=-k;
    }
    sort(a+1,a+tot+1,cmp);
    int now=0;
    while(now<tot)
    {
        do
        {
            now++;
            if(a[now].w>0) q1.push(a[now].w);
            else if(a[now].w<0) q2.push(-a[now].w);
        }while(now<tot&&a[now].id==a[now+1].id);
        while(q1.size()&&q2.size()&&q1.top()==q2.top()) q1.pop(),q2.pop();
        if(now<tot&&q1.size()) ans+=1ll*(a[now+1].id-a[now].id)*q1.top();
    }
    printf("%lld",ans);
    return 0;
}